Phương pháp sinh trong bài toán liệt kê

 PHƢƠNG PHÁP SINH 
I. Khái niệm 
 Phương pháp sinh được sử dụng trong bài toán liệt kê, ví dụ như người ta 
cần liệt kê tổ hợp chập k của n phần tử hay hoán vị của một tập số, hay khi 
người cần làm một bài toán mà không thể áp dụng các phương pháp thông minh 
như quy hoạch động, chia để trị thì phương pháp liệt kê để xét vét cạn là sự lựa 
chọn cuối cùng. Phương pháp sinh là phương pháp từ cấu hình đầu tiên ta sinh 
ra các cấu hình tiếp theo. Không phải bài nào cũng có thể làm theo phương pháp 
sinh, yêu cầu của bài toán để có thể làm theo phương pháp sinh là: 
 - Thứ nhất phải xác định được cấu hình đầu và cấu hình cuối 
 - Thứ hai phải xác định được cấu hình tiếp theo bằng 1 công thức nhất 
 định 
Việc xác định cấu hình đầu tiên và cấu hình cuối cùng là do yêu cầu đặt ra của 
từng bài toán và do cách xác định của từng người lập trình. 
Yêu cầu quan trọng hơn khi sử dụng phương pháp sinh là làm sao từ cấu hình 
đang có ta có thể đưa ra được cấu hình tiếp theo hoặc là khẳng định đó là cấu 
hình cuối cùng. Ta tạm gọi bài toán từ cấu hình ban đầu sinh ra cấu hình tiếp 
theo có thủ tục là sinh_kế_tiếp. Khi đó bài toán sử dụng phương pháp sinh được 
viết như sau: 
 Procedure Generate; Begin 
 ; Stop := False; 
 While not Stop Do Begin 
 ; sinh_kế_tiếp; 
 End; 
 End; 
 Trong thủ tục sinh_kế_tiếp, nếu cấu hình đang có là cuối cùng thì thủ tục 
này cần gán cho biến Stop giá trị True, ngược lại thủ tục này sẽ xây dựng cấu 
hình kế tiếp của cấu hình đang có trong thứ tự đã xác định. 
II. Áp dụng phƣơng pháp sinh vào giải một số bài toán. 
1. Bài toán liệt kê tất cả các dãy nhị phân có độ dài N. 
Bài toán có thể được phát biểu như sau: Cho N là một số nguyên dương, hãy chỉ 
ra tất cả các dãy b1, b2, , bN với bi €{0; 1}, (1 ≤ i ≤ N). 
Ví dụ với N = 3 ta có các dãy đó là: Procedure init; 
 var i: integer; 
 Begin 
 Write('Do dai day nhi phan = '); readln(n); 
 for i := 1 to n do b[i] := 0; 
 stop := false; count := 0; 
 End; 
 Procedure Next_Bit_String; 
 Var i: integer; 
 Begin 
 i:=n; 
 while (i>=1) and (b[i]=1) do 
 Begin 
 b[i] := 0; 
 i := i-1; 
 End; 
 if i < 1 then stop := True Else b[i] := 1; 
 End; 
 BEGIN 
 init; 
 While not (top) do 
 Begin 
 Count := count + 1; 
 Write(Count:5); 
 For i := 1 to n do Write(b[i]:2); writeln; 
 Next_Bit_String; 
 End; 
 Write('Bam phim Enter de thoat khoi Chuong trinh '); Readln; 
 END. 
2. Bài toán liệt kê các tập con m phần tử của tập n phần tử. 
Bài toán có thể phát biểu như sau: Cho tập hợp Cho X = {1, 2, 3, .. , n}. Hãy liệt 
kê các tập con có m phần tử của X. Ví dụ: X= {1, 2, 3, 4, 5}, m= 3. Các tập con 
3 phần tử của X là: 
 1. {1, 2, 3} 2. {1, 2, 4} 3. {1, 2, 5} 4. {1, 3, 4} 5. {1, 3, 5} 
 6. {1, 4, 5} 7. {2, 3, 4} 8. {2, 3, 5} 9. {2, 4, 5} 10. {3, 4, 5} 
Phân tích bài toán: 
Mỗi tập con m phần tử của X có thể biểu diễn bởi bộ có thứ tự gồm m thành 
phần a = {a1, a2, .., am 1 < a2 <  am n. Var i, j: integer; 
Begin 
 i := m; 
 while (i>0) and (a[i] = n-m+i) do i := i-1; 
 if i = 0 then stop := True 
 else 
 begin 
 a[i] := a[i]+1; 
 for j := i+1 to m do a[j] := a[i]+j-i; 
 end; 
End; 
BEGIN 
 init; 
 while not stop do 
 begin 
 count := count+1; 
 Write(count:5); 
 for i := 1 to m do write(a[i]:3); writeln; 
 Next_Combination; 
 end; 
Write('Bam Enter de ket thuc '); Readln 
End. 
3. Bài toán liệt kê các hoán vị của tập n phần tử. 
Bài toán có thể phát biểu như sau: Cho X = {1, 2, 3, .. , n}. Hãy liệt kê các hoán 
vị từ n phần tử của X. Ví dụ với n = 3 thì các hoán vị của nó là: 
 1. (1, 2, 3) 4. (2, 3, 1) 
 2. (1, 3, 2) 5. (3, 1, 2) 
 3. (2, 1, 3) 6. (3, 2, 1) 
Phân tích bài toán: 
Ta thấy ngay theo thứ tự trên thì cầu hình đầu tiên là: (1, 2, 3, . . n) và cấu hình 
cuối cùng là (n, n-1, ..., 2, 1). 
Cần xây dựng thuật toán để từ cấu hình đang có là (a1, a2, , an) ta tìm được cấu 
hình tiếp theo. Từ cấu hình đang có {a1, a2, , an} ta xây dựng cấu hình tiếp 
theo bằng qui tắc: 
 - Tìm j đầu tiên thoả mãn aj<aj+1 (j giảm từ n, n-1, , 1); 
 - Tìm ak là số nhỏ nhất và ak>aj trong các số aj+1, aj+2, , an; 
 - Đỗi chỗ aj với ak; tg := a[l]; 
 a[l] := a[m]; 
 a[m] := tg; 
 dec(l); 
 inc(m); 
end; 
 end; 
end; 
BEGIN 
 init; 
 while not stop do 
 begin 
 inc(count); write(count,'. '); 
 For i := 1 to N do write(a[i]:3); writeln; 
 next_permution; 
 end; 
 Write('Bam Enter de ket thuc '); Readln; 
END. 
4. Bài toán phân tích số nguyên dƣơng N thành tổng các số nguyên không âm. 
Bài toán được phát biểu như sau: Cho một số nguyên dương N. Hãy liệt kê các 
cách phân tích N thành tổng các số nguyên không âm. Ví dụ với N = 4, ta có thể 
phân tích thành: 
 1. 4 
 2. 3 + 1 
 3. 2 + 2 
 4. 2 + 1 + 1 
 5. 1 + 1 + 1 + 1 
Phân tích bài toán: 
Ta có thể thấy ngay cấu hình đầu tiên là: N và cấu hình cuối cùng là 1 1 1  1 
(N chữ số 1). 
Cần xây dựng thuật toán để từ cấu hình ta tìm được cấu hình tiếp theo. Từ cấu 
hình a1, a2, , ak ta có thể xây dựng cấu hình tiếp theo với quy tắc sau: 
 - Tìm i đầu tiên sao cho ai 1 (i giảm từ k, k-1,  1) 
 - Thay ai = ai -1 
 - Phân tích (k-i+1) thành các số như sư: 
 + Gán aj :=ai với j từ i+1 đến i + [(i+ k-i+1) div ai ]; 
 + Gán aj+1 := [(k-i+1) mod ai] nếu [(k-i+1) mod ai] 0 End; 
Procedure Next_Division; 
Var i, j, r, s, d : integer; 
Begin 
 i := k; 
 while (i>0) and (c[i] =1) do dec(i); 
 if i>0 then 
 begin 
 c[i] := c[i]-1; 
 d := k-i+1; 
 r := d div c[i]; 
 s := d mod c[i]; 
 k := i; 
 if r>0 then 
 begin 
 for j := i+1 to i+R do c[j]:=c[i]; 
 k := k+r; 
 end; 
 if s>0 then 
 begin 
 k := k+1; 
 c[k] := s; 
 end; 
 end else stop := True; 
End; 
Procedure Division; 
Var i: integer; 
Begin 
 While not stop do 
 begin 
 result; 
 next_division; 
 end; 
 Write('Bam Enter de ket thuc '); Readln 
End; 
BEGIN 
 init; 
 division; 
END.