Đề tài Tìm hiểu về đệ quy

7 5 
2 7 3 6 8 5 1 4 
2 7 5 8 1 4 6 3 
2 8 6 1 3 5 7 4 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 27 
8.3. Bài toán Mã đi tuần 
 Đề bài: Mã đi tuần (hành trình của quân mã) là bài toán về việc di chuyển một 
quân mã trên bàn cờ vua (8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống nó 
phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần. 
Hãy viết chương trình đặt quân mã vào một vị trí bất kỳ trên bàn cờ. Tìm chu trình 
của quân mã để ghé thăm một lần duy nhất tất cả các ô còn lại 
- Quy tắc di chuyển của quân mã trên bàn cờ vua: quân mã đi theo hình chữ L 
 Phân tích bài toán: 
Có rất nhiều lời giải cho bài toán này, chính xác là 26.534.728.821.064 lời giải 
trong đó quân mã có thể kết thúc tại chính ô mà nó khởi đầu. Một hành trình như vật 
được gọi là hành trình đóng. 
 Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ (kể 
cả ô xuất phát), thì từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một 
nước đi. Những hành trình như vậy được gọi là hành trình mở. 
Hai trong số nhiều hành trình đóng trên bàn cờ 8 x 8. 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 28 
Đối với bài toán mã đi tuần ta nhận thấy rằng, ban đầu tọa độ của quân mã là (i,j) 
bất kỳ trên bàn cờ. Tại vị trí này theo quy luật di chuyển của quân mã trên bàn cờ thì 
quân mã có tối đa 8 hướng đi tiếp theo. Rõ ràng để đi đến các lời giải ta phải thử tất 
cả các trường hợp quân mã có thể đi đến ở bước 1. Với mỗi vị trí thử như vậy ta lại 
thử tất cả các các trường hợp của quân mã có thể đi đến ở bước 2,… Cứ tiếp tục như 
vây cho đến khi quân mã đi qua tất cả các ô tên bàn cờ vua thì dừng lại. Như vậy, tính 
chất đệ quy của bài toán đó thể hiện trong các phép thử hướng đi cua quân mã ở trên. 
Kết quả ta tìm được nhiều chu trình đi khác nhau nhưng số bước đi đều là 63. 
Sử dụng giải thuật đệ quy quay lui cho bài toán mã đi tuần, ta có: 
- Try(k,i,j): Chọn thực hiện bước đi thứ k, với ô xuất phát là (i,j); 
- Các phương án chọn: Có 8 phương án (tương ứng với 8 trường hợp có thể đi 
đến của quân mã): 
+ Kí hiệu phương án: m = 1, 2, …, 8. 
+ Thiết lập hai mảng một chiều d,c lưu trữ tọa độ tương ứng 8 khả năng di 
chuyển của quân mã: 
-2 -2 -1 1 2 2 1 -1 
chỉ số m 1 2 3 4 5 6 7 8 
-1 1 2 2 1 -1 -2 -2 
chỉ số m 1 2 3 4 5 6 7 8 
Khi đó: phương án m là di chuyển mã đến ô (i+d[m], j+c[m]). 
- Chọn được: nếu như ô (i+d[m], j+c[m]) quân mã chưa đi qua và 1<= i+d[m]<= 
8 và 1<= j+c[m]<= 8. 
- Thực hiện bước đi thứ k: 
+ Tổ chức lưu trữ: Dùng mảng 2 chiều A có kích thước 8x8: A[1..8, 1..8] 
A[i,j] = 0 : nếu quân mã chưa đi qua ô (i,j) 
 k : nếu quân mã đã đi qua ô (i,j) ở bước thứ k 
+ Lưu vết: A([i+d[m], j+c[m]):=k. 
- Thành công: k=64 (hoặc k>63). 
- Thông báo kết quả: In mảng A. 
- Lời gọi đệ quy tiếp theo: Try(k+1, i+d[m], j+c[m]). 
- Hủy bước đi thứ k: A([i+d[m], j+c[m]):=0. 
d 
c 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 29 
* Thủ tục đệ quy quay lui cho nài toán này được viết như sau: 
Procedure Try(k,i,j); 
Begin 
for m:=1 to 8 do 
If (A(i+d[m], j+c[m]) = 0) and ((i+d[m]) in S) and 
((j+c[m]) in S) Then 
Begin 
A(i+d[m], j+c[m]) = k; 
If k=64 Then Xuat Else Try(k+1, i+d[m], j+c[m]); 
A(i+d[m], j+c[m]) = 0; 
End; 
End; 
 Cài đặt chương trình: 
Program Ma_di_tuan; 
Const 
d:array[1..8] of integer=(-2,-2,-1,1,2,2,1,-1); 
c:array[1..8] of integer=(-1,1,2,2,1,-1,-2,-2); 
Var 
A:array[1..8,1..8] of integer; 
S:set of 1..8; 
i, j: integer; 
{-----------------------------------------------------} 
Procedure Nhap; 
Begin 
fillchar(A,sizeof(A),0); 
writeln('Cho biet toa do ban dau cua ma: '); 
readln(i,j); 
A[i,j]:=1; 
S:=[1,2,3,4,5,6,7,8]; 
End; 
{-----------------------------------------------------} 
Procedure xuat; 
var x, y:integer; 
Begin 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 30 
for x:=1 to 8 do 
begin 
for y:=1 to 8 do write(A[x,y]:5); 
writeln; 
end; 
End; 
{-----------------------------------------------------} 
Procedure Try(k,i,j); 
var m:byte; 
Begin 
for m:=1 to 8 do 
If (A(i+d[m], j+c[m]) = 0) and ((i+d[m]) in S) and 
((j+c[m]) in S) Then 
Begin 
A(i+d[m], j+c[m]) = k; 
If k=64 Then Xuat Else Try(k+1, i+d[m], j+c[m]); 
A(i+d[m], j+c[m]) = 0; 
End; 
End; 
{-----------------------------------------------------} 
BEGIN 
Nhap; 
Try(2, i, j); 
Readln; 
END. 
 Chạy thử chương trình: Dưới đây là một đường đi của quân mã: 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 31 
PHẦN III: PHẦN KẾT LUẬN 
---------------------- 
Có thể nói rằng đệ quy là quả tim trong các nghiên cứu lý thuyết, cũng như thực 
hành tính toán đã thể hiện rất nhiều sức mạnh và có ưu điểm trong nhiều bài toán. 
Căn cứ vào mục đích và nhiệm vụ của đề tài, chúng em đã đạt được những kết quả 
sau: 
- Tìm hiểu và trình bày khái niệm đệ quy, giải thuật đệ quy, chương trình con 
đệ quy, đệ quy quay lui 
- Tìm hiểu cấu trúc chung của chương trình con đệ quy 
- Tìm hiêủ về nguyên tắc hoạt động của giải thuật đệ quy 
- Xây dựng chương trình cài đặt 8 bài toán về đệ quy nói chung và 3 bài toán 
điển hình về đệ quy quay lui 
Như vậy, đề tài cơ bản đã hoàn thành, đảm bảo các nhiệm vụ và mục đích nghiên 
cứu đã đề ra. 
Mặc dù đã có nhiều thời gian tìm hiểu về đề tài, tuy nhiên do ảnh hưởng của công 
việc học tập, thi cử và nhiều công việc khác, bên cạnh đó do khả năng trình độ của 
bản thân chúng em có hạn nên việc thực hiện đề tài còn có một số hạn chế sau: 
- Chưa trình bày kỹ lý thuyết về đệ quy quay lui 
- Hệ thống các bài toán và lời giải chưa đa dạng và phong phú 
- Chưa cài đặt các bài toán trên với lời giải không đệ quy để thấy rõ ưu điểm 
và hạn chế của đệ quy. 
Chúng em hi vọng những hạn chế này sẽ là bài học kinh nghiệm, là những nội 
dung chúng em cần phấn đấu xây dựng trong thời gian tới. 
Chúng em mong các thầy cô đóng góp ý kiến để đề tài được hoàn thiện hơn. 
Xin chân thành cảm ơn! 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 32 
tµi liÖu tham kh¶o 
---------------------- 
[1] Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, Nhà xuất bản khoa học và kỹ thuật. 
[2] Trần Đức Huyên, Một số bài toán chọn lọc trong Tin học, Nhà xuất bản giáo dục. 
[3] Trần Đức Huyên, Các vấn đề về lập trình Pascal, Nhà xuất bản Thanh Niên. 
[4] Nguyễn Xuân Huy, Sáng tạo trong thuật toán và lập trình - Tập 1, Nhà xuất bản 
giáo dục. 
[5] Nguyễn Xuân My, Một số vấn đề chọn lọc trong Tin học - Tập 1, Nhà xuất bản 
giáo dục. 
[6] Nguyễn Xuân My, Một số vấn đề chọn lọc trong Tin học - Tập 2, Nhà xuất bản 
giáo dục. 
[7] Nguyễn Hải Lộc - Nguyễn Thanh Tiên, Bài giảng ngôn ngữ lập trình Pascal, Đại 
học sư phạm Huế. 
[8] Các tài liệu về Đệ quy trên Internet. 
Trường THPT Chuyên Quảng Bình 
Gi¸o viªn: TrÇn L­¬ng V­¬ng 
 Trang 33 
môc lôc 
---------------------- 
PhÇn i - phÇn më ®Çu.......................Error! Bookmark not defined. 
PhÇn ii - phÇn néi dung .................Error! Bookmark not defined. 
1. Khái niệm về đệ quy ........................................................................................ 2 
1.1. Khái niệm về hình thức đệ quy.................................................................... 2 
1.2. Khái niệm về đệ quy ................................................................................... 3 
1.3. Các bước để giải bài toán đệ quy................................................................. 3 
2. Giải thuật đệ quy.............................................................................................. 3 
2.1. Khái niệm giải thuật đệ quy ........................................................................ 3 
2.2. Ví dụ ........................................................................................................... 4 
3. Chương trình con đệ quy................................................................................. 5 
3.1. Khái niệm chương trình con đệ quy ............................................................ 5 
3.2. Cấu trúc chính của chương trình con đệ quy ............................................... 5 
4. Nguyên tắc hoạt động của giải thuật đệ quy................................................... 6 
4.1. Khái niệm stack: ......................................................................................... 6 
4.2. Nguyên tắc hoạt động: ................................................................................ 6 
5. Ưu điểm và hạn chế của đệ quy....................................................................... 6 
5.1. Ưu điểm:..................................................................................................... 6 
5.2. Hạn chế:...................................................................................................... 7 
6. Một số bài toán về đệ quy ................................................................................ 7 
7. Đệ quy quay lui (Back tracking) ................................................................... 18 
7.1. Tổng quan về đệ quy quay lui ................................................................... 18 
7.2. Giải thuật tổng quát................................................................................... 18 
8. Một số bài toán về đệ quy quay lui................................................................ 19 
8.1. Bài toán Tìm hoán vị................................................................................. 19 
8.2. Bài toán Tám quân hậu ............................................................................. 22 
8.3. Bài toán Mã đi tuần................................................................................... 27 
PhÇn iii - phÇn kÕt luËn ...............Error! Bookmark not defined. 
tµi liÖu tham kh¶o ......................................................................................32