Giáo án bồi dưỡng 12
CHUYÊN ĐỀ: THUẬT TOÁN ĐỆ QUI
I/ NỘI DUNG
1/ MÔ HÌNH CỦA THUẬT TOÁN QUAY LUI
Thuậ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ựng bằ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ả thiết cấu hình cần liệt kê có dạng (x
1
,x
2
,……,x
n
). khi đó thuật toán quay lui thực hiện
qua các bước sau:
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ỗi giá trò thử gán chon 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ỗi giá trò thử gán cho x
2
lại xét tiếp các khả năng chọn x
3

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 Try(i:Integer);
Begin
For (mọi giá trò V có thể gán cho x
i
) do
Begin
<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>
Else Begin
<Ghi nhận việc cho x
i
nhận giá trò V (nếu cần) >;
Try(i+1);(Gọi đệ qui để 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;

Const
Max=30;
input='BSTR.INP';
output='BSTR.OUT';
Var x: Array[1..max] of integer;
n:Integer; f,g:text;
Procedure PrintResult ;
Var I:Integer;
Begin
For i:=1 to n do write(g,x[i]);
writeln(g);
End;
Procedure Try(i:integer);
Var J:integer;
Begin
For j:=0 to 1 do
Begin
x[i]:=j;
if i=n then PrintResult
else Try(i+1);
End;
End;
BEGIN
Clrscr;
Assign(F,Input);
Assign(g,output);Rewrite(g);
Reset(f);
Read(f,n);
Try(1);
Close(f);

• …………
• x
i
≤n-k+i
Trang 2
Try(1
)
Try(2
)
Try(2
)
Try(3
)
Try(3
)
Try(3
)
Try(3
)
Hình 1: Cây tìm kiếm quay lui
Giáo án bồi dưỡng 12
• ………...
• x
1
≤n-k+1.
Từ đó suy ra x
i-1
+1 ≤ x
i
≤ n-k+i (1 ≤ i ≤ k) ở đây ta giả thiết có thêm một số x

Var J:integer;
Begin
For j:=x[i-1]+1 to n-k+i do
Begin
x[i]:=j;
if i=k then PrintResult
else Try(i+1);
End;
End;
BEGIN
Clrscr;
Assign(F,Input);
Reset(f); Assign(g,output);
Rewrite(g);
Read(f,n,k); x[0]:=0; Try(1);
Close(f); Close(g);
Readln;
END.
Nếu để ý chương trình trên và chương trình liệt kê dãy nhò phân độ dài n, ta thấy về
cơ bản chúng chỉ khác nhau ở thủ tục try(i) – chọn thử các giá trò cho x
i
, ở chương trình liệt
kê dãy nhò phân ta thử chọn các giá trò 0 hoặc 1 còn ở chương trình liệt kê các tập con k
phần tử ta thử chọn x
i
là một trong các giá trò nguyên x
i-1
+1 đến n-k+i. Qua đó ta có thể
thấy tính phổ dụng của thuật toán quay lui: Mô hình cài đặt có thể thích hợp cho nhiều bài
toán, khác với phương pháp sinh tuần tự, với mỗi bài toán lại phải có một thuật toán sinh

là các phần tử từ 1 đến n đều tự do.
• Tại bước chọn các giá trò có thể của x
i
ta chỉ xét những giá trò j có c
j
=TRUE có
nghóa là chỉ chọn những giá trò tự do.
Trang 3
Giáo án bồi dưỡng 12
• Trước khi gọi đệ quy tìm x
i+1
ta đặt giá trò j vừa gán cho x
i
là đã bò chọn có nghóa là
đặt c
j
:=FALSE để các thủ tục Try(i+1), Try(i+2)….. gọi sau này không chọn phải giá
trò j đó nữa.
• Sau khi gọi đệ quy tìm x
i+1
: có nghóa là sắp tới ta sẽ thử gán một giá trò khác cho x
i
thì ta sẽ đặt giá trò j vừa thử đó thành tự do (c
j
:=TRUE), bởi khi x
i
đã nhận một giá
trò khác rồi thì các phần tử đứng sau: x
i+1
,x

Begin
Assign(f,input);reset(f);
Assign(g,output);rewrite(g);
Readln(f,n,k);
Fillchar(c,sizeof(c),true);
End;
Procedure printresult;
Var i:integer;
Begin
for i:=1 to k do write(g,x[i],' ');
writeln(g);
End;
Procedure try(i:integer);
Var j:integer;
Begin
for j:=1 to n do
if c[j] then
Begin
x[i]:=j;
if i=k then PrintResult
else
Begin
c[j]:=false;
Try(i+1);
c[j]:=true;
End;
End;
End;
BEGIN
Clrscr;

i
.
3. Vì số phần tử thực sự của mảng x là không cố đònh nên thủ tục PrintResult dùng
để in ra 1 cách phân tích phải có thêm tham số cho biết sẽ in ra bao nhiêu phần
tử.
4. Thủ tục đệ quy Try(i) sẽ thử các giá trò có thể nhận của x
i
(x
i
≥x
i-1
)
5. Khi nào thì in kết quả và khi nào thì gọi đệ quy tìm tiếp?
Lưu ý rằng t
i-1
là tổng của tất cả các phần tử từ x
1
đến x
i-1
do đó
• Khi t
i
=n tức là (x
i
=n-t
i-1
) thì in kết quả
• Khi tìm tiếp, x
i+1
sẽ phải lớn hơn hoặc bằng x

i-1
)/2. Ví dụ đơn giản khi n =0 thì chọn x
1
=6,7,8,9 là việc làm vô nghóa vì như vậy
cũng không ra nghiệm mà cũng không chọn tiếp x
2
được nữa.
Một cách dễ hiểu ta gọi đệ quy tìm tiếp khi giá trò x
i
được chọn còn cho phép chọn
thêm một phần tử khác lớn hơn hoặc bằng nó mà không làm vượt quá n. còn ta in kết quả
chỉ khi x
i
mang giá trò đúng bằng số thiết hụt của tổng i-1 phần tử đầu so với n.
6. Vậy thủ tục Try(i) thử các giá trò cho x
i
có thể mô tả như sau: (Để tổng quát cho
i=1, ta đặt x
0
=1 và t
0
=0)
• Xét các giá trò của x
i
và x
i-1
đến (n-t
i-1
) div2, cập nhật t
i

Trang 5
Giáo án bồi dưỡng 12
Const
Max=30;
Input='analyses.inp';
Output='analyses.out';
Var
n:integer;
f,g:text;
x,t:array[0..max] of integer;
Procedure Init;
Begin
readln(f,n);
x[0]:=1;
t[0]:=0;
End;
Procedure printresult(k:integer);
Var i:integer;
Begin
Write(g,n,'=');
For i:=1 to k-1 do write(g,x[i],'+');
Writeln(g,x[k]);
End;
Procedure Try(i:integer);
Var j:integer;
Begin
For j:=x[i-1] to (n-t[i-1])div 2 do
Begin
x[i]:=j; t[i]:=t[i-1]+j; try(i+1);
End;