LIỆT KÊ CÁC DÃY NHỊ PHÂN ĐỘ DÀI N

 
Input/Output với khuôn dạng như trong P_1_02_1.PAS
Biể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 [-2³¹..2³¹ - 1]*) program Binary_String_Enumeration;
const

 
InputFile = 'BSTR.INP'; OutputFile = 'BSTR.OUT'; max = 100;
var
x: 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}
var
i: Integer; begin
for 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]}
var
j: Integer; begin
for j := 0 to 1 do {Xét các giá trị có thể gán cho x[i], với mỗi giá trị đó}
begin
x[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;
 
begin
Assign(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:

Hình 1: Cây tìm kiếm quay lui trong bài toán liệt kê dãy nhị phân