LIỆT KÊ CÁC HOÁN VỊ - Tài Liệu Text - 123doc

1. Trang chủ >
2. Giáo án - Bài giảng >
3. Tư liệu khác >

LIỆT KÊ CÁC HOÁN VỊ

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (16.43 MB, 334 trang )

Bài toán liệt kê9đủ lớn nên ta sẽ tìm biểu diễn nhỏ nhất của 4 số này gán cho x[3], x[4], x[5], x[6] tức là 〈1, 2,5, 6〉. Vậy hoán vị mới sẽ là 〈3, 4, 1, 2, 5, 6〉.Ta có nhận xét gì qua ví dụ này: Đoạn cuối của hoán vị hiện tại được xếp giảm dần, số x[5] =4 là số nhỏ nhất trong đoạn cuối giảm dần thoả mãn điều kiện lớn hơn x[2] = 2. Nếu đổi chỗx[5] cho x[2] thì ta sẽ được x[2] = 4 và đoạn cuối vẫn được sắp xếp giảm dần. Khi đó muốnbiểu diễn nhỏ nhất cho các giá trị trong đoạn cuối thì ta chỉ cần đảo ngược đoạn cuối.Trong trường hợp hoán vị hiện tại là 〈2, 1, 3, 4〉 thì hoán vị kế tiếp sẽ là 〈2, 1, 4, 3〉. Ta cũngcó thể coi hoán vị 〈2, 1, 3, 4〉 có đoạn cuối giảm dần, đoạn cuối này chỉ gồm 1 phần tử (4)Vậy kỹ thuật sinh hoán vị kế tiếp từ hoán vị hiện tại có thể xây dựng như sau:Xác định đoạn cuối giảm dần dài nhất, tìm chỉ số i của phần tử x[i] đứng liền trước đoạn cuốiđó. Điều này đồng nghĩa với việc tìm từ vị trí sát cuối dãy lên đầu, gặp chỉ số i đầu tiên thỏamãn x[i] < x[i+1].Nếu tìm thấy chỉ số i như trênTrong đoạn cuối giảm dần, tìm phần tử x[k] nhỏ nhất thoả mãn điều kiện x[k] > x[i]. Dođoạn cuối giảm dần, điều này thực hiện bằng cách tìm từ cuối dãy lên đầu gặp chỉ số kđầu tiên thoả mãn x[k] > x[i] (có thể dùng tìm kiếm nhị phân).Đảo giá trị x[k] và x[i]Lật ngược thứ tự đoạn cuối giảm dần (từ x[i+1] đến x[k]) trở thành tăng dần.Nếu không tìm thấy tức là toàn dãy đã sắp giảm dần, đây là cấu hình cuối cùngInput: file văn bản PERMUTE.INP chứa số nguyên dương n ≤ 100Output: file văn bản PERMUTE.OUT các hoán vị của dãy (1, 2, …, n)PERMUTE.INP3PERMUTE.OUT123132213231312321P_1_02_3.PAS * Thuật toán sinh liệt kê hoán vị{$MODE DELPHI} (*This program uses 32-bit Integer [-231..231 - 1]*)program Permutation;constInputFile = 'PERMUTE.INP';OutputFile = 'PERMUTE.OUT';max = 100;varn, i, k, a, b: Integer;x: array[1..max] of Integer;f: Text;procedure Swap(var X, Y: Integer); {Thủ tục đảo giá trị hai tham biến X, Y}varTemp: Integer;beginTemp := X; X := Y; Y := Temp;end;Lê Minh Hoàng10Chuyên đềbeginAssign(f, InputFile); Reset(f);ReadLn(f, n);Close(f);Assign(f, OutputFile); Rewrite(f);for i := 1 to n do x[i] := i; {Khởi tạo cấu hình đầu: x[1] := 1; x[2] := 2; …, x[n] := n}repeatfor i := 1 to n do Write(f, x[i], ' '); {In ra cấu hình hoán vị hiện tại}WriteLn(f);i := n - 1;while (i > 0) and (x[i] > x[i + 1]) do Dec(i);if i > 0 then {Chưa gặp phải hoán vị cuối (n, n-1, …, 1)}begink := n; {x[k] là phần tử cuối dãy}while x[k] < x[i] do Dec(k); {Lùi dần k để tìm gặp x[k] đầu tiên lớn hơn x[i]}Swap(x[k], x[i]); {Đổi chỗ x[k] và x[i]}a := i + 1; b := n; {Lật ngược đoạn cuối giảm dần, a: đầu đoạn, b: cuối đoạn}while a < b dobeginSwap(x[a], x[b]); {Đảo giá trị x[a] và x[b]}Inc(a); {Tiến a và lùi b, tiếp tục cho tới khi a, b chạm nhau}Dec(b);end;end;until i = 0; {Toàn dãy là dãy giảm dần - không sinh tiếp được - hết cấu hình}Close(f);end.Bài tập:Bài 1Các chương trình trên xử lý không tốt trong trường hợp tầm thường, đó là trường hợp n = 0đối với chương trình liệt kê dãy nhị phân cũng như trong chương trình liệt kê hoán vị, trườnghợp k = 0 đối với chương trình liệt kê tổ hợp, hãy khắc phục điều đó.Bài 2Liệt kê các dãy nhị phân độ dài n có thể coi là liệt kê các chỉnh hợp lặp chập n của tập 2 phầntử {0, 1}. Hãy lập chương trình:Nhập vào hai số n và k, liệt kê các chỉnh hợp lặp chập k của {0, 1, …, n -1}.Hướng dẫn: thay hệ cơ số 2 bằng hệ cơ số n.Bài 3Hãy liệt kê các dãy nhị phân độ dài n mà trong đó cụm chữ số “01” xuất hiện đúng 2 lần.Bài 4.Nhập vào một danh sách n tên người. Liệt kê tất cả các cách chọn ra đúng k người trong số nngười đó.Bài 5Liệt kê tất cả các tập con của tập {1, 2, …, n}. Có thể dùng phương pháp liệt kê tập con nhưtrên hoặc dùng phương pháp liệt kê tất cả các dãy nhị phân. Mỗi số 1 trong dãy nhị phântương ứng với một phần tử được chọn trong tập. Ví dụ với tập {1, 2, 3, 4} thì dãy nhị phânĐHSPHN 1999-2004Bài toán liệt kê111010 sẽ tương ứng với tập con {1, 3}. Hãy lập chương trình in ra tất cả các tập con của {1,2, …, n} theo hai phương pháp.Bài 6Nhập vào danh sách tên n người, in ra tất cả các cách xếp n người đó vào một bànBài 7Nhập vào danh sách n bạn nam và n bạn nữ, in ra tất cả các cách xếp 2n người đó vào một bàntròn, mỗi bạn nam tiếp đến một bạn nữ.Bài 8Người ta có thể dùng phương pháp sinh để liệt kê các chỉnh hợp không lặp chập k. Tuy nhiêncó một cách khác là liệt kê tất cả các tập con k phần tử của tập hợp, sau đó in ra đủ k! hoán vịcủa nó. Hãy viết chương trình liệt kê các chỉnh hợp không lặp chập k của {1, 2, …, n} theo cảhai cách.Bài 9Liệt kê tất cả các hoán vị chữ cái trong từ MISSISSIPPI theo thứ tự từ điển.Bài 10Liệt kê tất cả các cách phân tích số nguyên dương n thành tổng các số nguyên dương, hai cáchphân tích là hoán vị của nhau chỉ tính là một cách.Cuối cùng, ta có nhận xét, mỗi phương pháp liệt kê đều có ưu, nhược điểm riêng và phươngpháp sinh cũng không nằm ngoài nhận xét đó. Phương pháp sinh không thể sinh ra được cấuhình thứ p nếu như chưa có cấu hình thứ p - 1, chứng tỏ rằng phương pháp sinh tỏ ra ưu điểmtrong trường hợp liệt kê toàn bộ một số lượng nhỏ cấu hình trong một bộ dữ liệu lớn thì lại cónhược điểm và ít tính phổ dụng trong những thuật toán duyệt hạn chế. Hơn thế nữa, khôngphải cấu hình ban đầu lúc nào cũng dễ tìm được, không phải kỹ thuật sinh cấu hình kế tiếpcho mọi bài toán đều đơn giản như trên (Sinh các chỉnh hợp không lặp chập k theo thứ tự từđiển chẳng hạn). Ta sang một chuyên mục sau nói đến một phương pháp liệt kê có tính phổdụng cao hơn, để giải các bài toán liệt kê phức tạp hơn đó là: Thuật toán quay lui (Backtracking).Lê Minh Hoàng12Chuyên đề§3. THUẬT TOÁN QUAY LUIThuật toán quay lui dùng để giải bài toán liệt kê các cấu hình. Mỗi cấu hình được xây dựngbằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.Giả sử cấu hình cần liệt kê có dạng x[1..n], khi đó thuật toán quay lui thực hiện qua các bước:1) Xét tất cả các giá trị x[1] có thể nhận, thử cho x[1] nhận lần lượt các giá trị đó. Với mỗigiá trị thử gán cho x[1] ta sẽ:2) Xét tất cả các giá trị x[2] có thể nhận, lại thử cho x[2] nhận lần lượt các giá trị đó. Với mỗigiá trị thử gán cho x[2] lại xét tiếp các khả năng chọn x[3] … cứ tiếp tục như vậy đếnbước:…n) Xét tất cả các giá trị x[n] có thể nhận, thử cho x[n] nhận lần lượt các giá trị đó, thông báocấu hình tìm được 〈x[1], x[2], …, x[n]〉.Trên phương diện quy nạp, có thể nói rằng thuật toán quay lui liệt kê các cấu hình n phần tửdạng x[1..n] bằng cách thử cho x[1] nhận lần lượt các giá trị có thể. Với mỗi giá trị thử gáncho x[1] bài toán trở thành liệt kê tiếp cấu hình n - 1 phần tử x[2..n].Mô hình của thuật toán quay lui có thể mô tả như sau:{Thủ tục này thử cho x[i] nhận lần lượt các giá trị mà nó có thể nhận}procedure Attempt(i);beginfor 〈mọi giá trị V có thể gán cho x[i]〉 dobegin〈Thử cho x[i] := V〉;if 〈x[i] là phần tử cuối cùng trong cấu hình〉 then〈Thông báo cấu hình tìm được〉elsebegin〈Ghi nhận việc cho x[i] nhận giá trị V (nếu cần)〉;Attempt(i + 1); {Gọi đệ quy để chọn tiếp x[i+1]}〈Nếu cần, bỏ ghi nhận việc thử x[i] := V để thử giá trị khác〉;end;end;end;Thuật toán quay lui sẽ bắt đầu bằng lời gọi Attempt(1)3.1. LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI NInput/Output với khuôn dạng như trong P_1_02_1.PASBiểu diễn dãy nhị phân độ dài N dưới dạng x[1..n]. Ta sẽ liệt kê các dãy này bằng cách thửdùng các giá trị {0, 1} gán cho x[i]. Với mỗi giá trị thử gán cho x[i] lại thử các giá trị có thểgán cho x[i+1].Chương trình liệt kê bằng thuật toán quay lui có thể viết:P_1_03_1.PAS * Thuật toán quay lui liệt kê các dãy nhị phân độ dài n{$MODE DELPHI} (*This program uses 32-bit Integer [-231..231 - 1]*)program BinaryStrings;constĐHSPHN 1999-2004Bài toán liệt kê13InputFile = 'BSTR.INP';OutputFile = 'BSTR.OUT';max = 100;varx: array[1..max] of Integer;n: Integer;f: Text;procedure PrintResult; {In cấu hình tìm được, do thủ tục tìm đệ quy Attempt gọi khi tìm ra một cấu hình}vari: Integer;beginfor i := 1 to n do Write(f, x[i]);WriteLn(f);end;procedure Attempt(i: Integer); {Thử các cách chọn x[i]}varj: Integer;beginfor j := 0 to 1 do {Xét các giá trị có thể gán cho x[i], với mỗi giá trị đó}beginx[i] := j; {Thử đặt x[i]}if i = n then PrintResult {Nếu i = n thì in kết quả}else Attempt(i + 1); {Nếu i chưa phải là phần tử cuối thì tìm tiếp x[i+1]}end;end;beginAssign(f, InputFile); Reset(f);ReadLn(f, n); {Nhập dữ liệu}Close(f);Assign(f, OutputFile); Rewrite(f);Attempt(1); {Thử các cách chọn giá trị x[1]}Close(f);end.Ví dụ: Khi n = 3, cây tìm kiếm quay lui như sau:Try(1)X1=0Try(2)X2=0X3=0Try(3)000X1=1Try(2)X2=1X2=0Try(3)X3=1001X3=0010X2=1Try(3)X3=1011X3=0Try(3)X3=1100Hình 1: Cây tìm kiếm quay lui trong bài toán liệt kê dãy nhị phân3.2. LIỆT KÊ CÁC TẬP CON K PHẦN TỬInput/Output có khuôn dạng như trong P_1_02_2.PASLê Minh Hoàng101X3=0110X3=1111Result

Xem Thêm

Tài liệu liên quan

• Giải thuật và lập trình
  • 334
  • 4,808
  • 91
• Chuyen chuc phan su den Tan Vien
  • 16
  • 1
  • 5
• TIET 19
  • 3
  • 171
  • 0
• Hướng dẫn Repair Windows XP.doc
  • 2
  • 716
  • 0
• TIET 20.
  • 2
  • 174
  • 0
• TIET 21
  • 4
  • 172
  • 0
• Tập đọc : Hơn một nghìn ngày vòng quanh trái đất
  • 6
  • 8
  • 16
• TIET 22.
  • 2
  • 171
  • 0
• Bài 17- Một số chức năng khác
  • 29
  • 497
  • 2
• TIET 24.
  • 2
  • 132
  • 0
• Bài 18-Các công cụ trợ giúp soạn thảo
  • 8
  • 441
  • 1

Tải bản đầy đủ (.pdf) (334 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(16.43 MB) - Giải thuật và lập trình-334 (trang) Tải bản đầy đủ ngay ×