Chương 1 Một số cải biên của bài toán Tháp Hà Nội
2.2 Thuật toán lặp cho bài toán Tháp Hà Nội xoay vòng
Từ các suy luận, phân tích và chứng minh các tính chất của bài toán Tháp Hà Nội xoay vòng trong Mục 2.1, ta dễ dàng xây dựng được thuật toán lặp giải bài toán Tháp Hà Nội xoay vòng.
2.2.1 Giải thuật lặp cho bài toán Tháp Hà Nội
Các qui ước trong Giải thuật lặp giải Bài toán Tháp Hà Nội:
1.Số các đĩa được đánh từ 1 (đĩa nhỏ nhất) đến N (đĩa lớn nhất).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
2.Các cọc được đặt theo thứ tự (đặt theo hàng ngang), do vậy sử dụng các khái niệm di chuyển một đĩa theo chiều kim đồng hồ và ngược chiều kim đồng hồ.
Giải thuật lặp sử dụng ba qui tắc dưới đây:
Qui tắc 1Chỉ di chuyển các đĩa số lẻ theo chiều kim đồng hồ (nghĩa là cùng chiều nhau) và các đĩa số chẵn theo chiều ngược kim đồng hồ (nghĩa là cùng chiều nhau nhưng theo chiều ngược lại với đĩa chẵn).
Qui tắc 2Không di chuyển hai đĩa cùng một lúc.
Qui tắc 3Không đặt đĩa lớn hơn trên đĩa nhỏ hơn.
Xét ví dụN 3. Chúng ta sẽ giả sử rằng theo chiều kim đồng hồ là sang phải.
Ví trí ban đầu.
Đĩa 1 di chuyển theo chiều kim đồng hồ đồng..hồ
Đĩa 2 di chuyển theo ngược chiều kim đồng hồ do đĩa 1 vừa mới di chuyển.
Đây chỉ là bước di chuyển hợp pháp.
Di chuyển đĩa 3 theo chiều kim đồng hồ vì đĩa 1 vừa di chuyển.
Đây chỉ là di chuyển hợp pháp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
Thuật toán lặp bài toán Tháp Hà Nội trên ngôn ngữ Pascal:
Iterative_Algorithm;
Uses Crt;
Var N,i,j,pos2,pos3,third,second,nummoves: Byte;
locations: Array [0..100] of Byte;
Begin ClrScr;
Write('Nhap so dia N ='); Readln(N);
i:= 1; second:= 0;
For j:= 0 To N-1 Do locations[j]:= 0;
locations[N+1]:= 2;
nummoves:= 1;
For i:= 1 To N Do nummoves := nummoves * 2;
nummoves:= nummoves - 1;
For i:= 1 To nummoves Do Begin
If (i mod 2 = 1) Then Begin
second := locations[1];
locations[1]:= (locations[1] + 1) mod 3;
Writeln('Di chuyen dia 1 toi cot ', locations[1]);
End
Else Begin
third := 3 - second - locations[1];
Đĩa 2 di chuyển ngược chiều kim đồng hồ vì đĩa 1 vừa mới di chuyển.
Kết thúc.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
pos2:= N+1;
For j:= N+1 Downto 2 Do If (locations[j] = second) Then pos2:= j;
pos3:= N+1;
For j:= N+1 Downto 2 Do If (locations[j] = third) Then pos3:= j;
Write('Di chuyen dia ');
If (pos2 < pos3) Then Begin
Writeln(pos2,' toi cot ', third);
locations[pos2]:= third;
End Else Begin
Writeln(pos3,' toi cot ', second);
locations[pos3]:= second;
End;
End;
End;
Write('So buoc di chuyen la: ', nummoves);
Readln;
End.
--- Kết quả thu đƣợc nhƣ sau:
N=3
N= 4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
2.2.2 Thuật toán lặp cho bài toán Tháp Hà Nội xoay vòng Dưới đây chúng ta mô tả từng bước thuật toán lặp như sau:
1. For l n 1to 1 do
2. Trước tiên kiểm tra n có ở trên cọc B (cọc đích) hay không? Nếu có thì gán big = “true” rồi đến bước 3, ngược lại gán big = “false” rồi sang bước 4.
3. Nếu big = “true” thì kiểm tra xem vòng l trên vòng l 1không? Nếu có thì gán big = “true”, ngược lại gán big = “false” và làm tiếp l.
4. Nếu big = “false” thì kiểm tra xem cọc của vòng lkế tiếp cọc của vòng 1
l hay không? Nếu có gán big = “true”, ngược lại gán big = “false” và làm tiếp l.
5. Cuối cùng nếu big = “false” thì di chuyển đĩa 1 rồi lặp lại bước 1 tới khi tất cả các đĩa ở trên cọc đích.
6. Cuối cùng nếu big = “false” thì di chuyển hai lần đĩa nhỏ nhất và lặp lại bước 1 tới khi tất cả các đĩa trên cọc đích.
Bảng 1dưới đây cho kết quả của Bài toán Tháp Hà Nội với chuyển động xoay vòng với thuật toán lặp (cùng chiều kim đồng hồ).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
A B C A B C A B C A B C
1 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0
3 0 0 3 0 0 2 0 0 1 0 0
4 0 0 4 1 2 4 3 1 4 2 3
0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 1 0 0 0 0 0
3 0 0 3 0 1 2 0 0 1 0 2
4 1 0 4 0 2 4 3 0 4 0 3
0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 1 0 0 0 0 0
3 0 0 0 0 1 2 0 0 0 0 2
4 0 1 4 3 2 4 0 3 4 1 3
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
3 0 0 1 0 0 2 0 0 0 0 2
4 2 1 4 3 2 4 1 3 4 0 3
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1
3 0 0 0 1 0 2 0 1 0 0 2
4 2 0 4 3 2 4 0 3 0 4 3
0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
3 0 0 2 1 0 0 0 1 0 0 2
4 0 2 4 3 0 4 2 3 1 4 3
0 6 12 18
1 7 13 19
2 8 14 20
3 9 15 21
4 10 16 22
5 11 17 23
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
A B C A B C A B C A B C
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 2 0
0 1 2 0 2 0 0 3 1 0 3 0
0 4 3 3 4 0 0 4 2 1 4 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 2 0
0 1 0 0 2 0 0 3 0 0 3 0
2 4 3 3 4 1 1 4 2 0 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 1 1 2 0 0 3 0
2 4 3 3 4 0 0 4 2
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 2 1 1 0 0 0 3 0
0 4 3 3 4 2 2 4 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 2 0 0 1 0 0 3 0
1 4 3 3 4 2 2 4 1
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 2 0
0 2 0 0 0 1 0 3 0
0 4 3 3 4 2 0 4 1
Kết luận
24 30 36 42
25 31 37 43
29 35 41
26 32 38
27 33
28 34 40
39
Có tất cả 43 bước di chuyển
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn/
Bảng 1: Kết quả của Bài toán Tháp Hà Nội với chuyển động xoay vòng với thuật toán lặp (cùng chiều kim đồng hồ)