ÔN TẬP KTLT 2
Thuật toán sinh và quay lui

1


Dàn bài
1.

Thuật toán sinh và bài tập

2.

Thuật toán quay lui và bài tập

2


Bài toán sinh
1.
2.
3.
(1)

Định nghĩa: Tạo ra dữ liệu.
Phương pháp sinh: Từ dữ liệu ban đầu, sinh ra dữ
liệu kế tiếp cho đến khi kết thúc.
Điều kiện của thuật toán sinh:
Có thể xác định 1 thứ tự tập các cấu hình của tổ hợp
(thứ tự của các phép gán trị, thường dùng thứ tự từ
điển).

a
b
b
b
b
b
b
c
c
c
c
c
c

y
d
d
d
e
e
e
d
d
d
e
e
e
d
d
d

adm < adn

4


Thuật toán sinh tổng quát.
Generate()
{
c = InitialConfigure(); //cấu hình ban đầu
Process (c);
// xử lý cấu hình đang có
if (c=LastConfigure()) Stop=true
else stop = false;
while (not stop)
{
//Sinh cấu hình kế tiếp từ cấu hình đang có

c=getNextConfigure(c);
Process (c); // xử lý cấu hình này
if c= LastConfigure then stop = true;

}
End;

5


Bài toán liệt kê các tập con của 1 tập



0001
0010
0011
0100
0101
0110
0111

p(b)
0
1
2
3
4
5
6
7

bits
1000
1001
1010
1011
1100
1101
1110
1111

p(b)
8


0100

0111

1000

• Gọi i : vị trí bit 0 đầu tiên từ
bên phải.
• Cho các bit 1 bên phải vị trí i
thành 0
•Cho bit i mang trị 1
i= n-1;
while (i>=0 && bits[i]==1) bits[i--] = 0;
bits[i] = 1;
8


Viết chương trình liệt kê
p(b)
void InitConfigure(char bits[], int n) bits
0123_____
{ for (int i=0; i

bits
p(b)
0123_____
1111

15
9


Viết chương trình liệt kê
void Output(char bits[], int n, int count)
{ printf( ‘’\nTap con thu %d\t’’,count);
for (int i=0; i

11


Bài toán tập con k-phần tử : Tìm hiều
Liệt kê các tập con k phần tử của tập n phần tử.
 Ví dụ: Các tập con 3 phần tử của tập 5 phần tử
{ 1,2,3,4,5 } là:
C53 = 5!/ (3! * (5-3)!)
{ 1,2,3 } { 2,3,4 }
= 5! / (3! * 2!)
{ 1,2,4 } { 2,3,5 }
= 4*5/2 = 10
{ 1,2,5 } { 2,4,5 }
{ 1,3,4 } { 3,4,5 }
{ 1,3,5 }
Tổ hợp n chập k
{ 1,4,5 }


12


Bài toán tập con k-phần tử: Đặc tả



Ánh xạ tập hợp bất kỳ n phần tử vào tập X={ 1,2...n }
Một tập con k phần tử của X là một bộ có thứ tự a 1
a2 a3 ..... ak với 1≤ a1< a2 < a3

14

Tìm vị trí
đầu tiên
khác với
nhóm trị ở
cuối tập
cha theo
thứ tự


Viết chương trình bài toán tập con k- phần tử (1)
void Init (int result[], int k)
{ for (int i=1; i0)
{ result[i]++;
for (int j=i+1; j
Bài tập


Tạo tập tin văn bản có tên Tapcon.in chứa nội dung : 10 4



Ý nghĩa: số đầu: số phần tử của tập, số kế tiếp là số phần tử
của tập con.



Dùng kỹ thuật sinh, viết chương trình ghi các tập con của tập
này lên file Tapcon.out

17


Bài toán hoán vị tập n phần tử
Cho tập X = { 1,2,3,..., n}. Hãy liệt kê tất cả các hoán vị
của tập này.
 Một hoán vị của X là một bộ A = (a1, a2,..., an ) với ai ≠
aj nếu i ≠ j
 Định nghĩa 1 thứ tự:
A = (a1, a2,...,ak-1, ak, ... an ) là hoán vị trước của
A’= (a’1, a’2,...,a’k-1, a’k, ... a’n ) nếu tìm được vị trí k sao
cho ak < a’k
 Ví dụ : 1234567 là hoán vị trước của
1234657
 Đây chính là thứ tự từ điển.

{1,4,3,2}
{2,1,3,4}
{2,1,4,3}
{2,3,1,4}
{2,3,4,1}
{2,4,1,3}
{2,4,3,1}

j=1
{3,1,2,4}
{3,4,2,1}
{3,1,4,2}
k=2
{3,2,1,4}
{3,4,2,1}
{3,2,4,1}
{3,4,1,2}
hoán vị
{4,3,2,1}
a[j], a[k]
{3,4,2,1}
{4,1,2,3}
{4,1,2,3}
Đảo mảng
{4,1,3,2}
con từ
{4,2,1,3}
a[j+1] đến
a[n]
{4,2,3,1}

//Tìm vị trí đầu tiên k đi ngược từ cuối tập trị với a[k] > a[j]
while(k>0 && result[j] > result[k]) k--;
// Hoán vị a[j], a[k]
int t= result[j];
result[j]= result[k];
result[k]= t;
//Đảo ngược nhóm trị a[j+1],... a[n]
int left=j+1, right=n;
while (left < right)
{ t = result[left];
result[left]= result[right];
result[right]=t;
left++; right--;
}
}
22


Viết chương trình hoán vị (3)
void Generate(char result[], int n)
{ Init(result, n); //cấu hình ban đầu
int count=1;
Output(result,n,count) // xuat cấu hình đang
có
int stop = LastConfigure(result,n);
while (!stop)
{
//Sinh cấu hình kế tiếp từ cấu hình đang có
c=NextConfigure(result, n);
count++;

25