Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 8: Suy ngẫm

 = (a mod 3)+1); 
'n': ke := (a = (b mod 3)+1); 
't': Ke := (abs(a-b) = 1); 
'h': Ke := True; 
end {case}; 
end; 
Tương tự, khi hai cọc a và b không kề nhau ta cũng thực hiện các thao tác như 
nhau. 
Biết hàm Ke, ta dựa vào các thuật toán riêng cho mỗi trường hợp để viết phương án 
cho bài toán Hà Nội sắc màu như sau: 
(*---------------------------------------- 
Ha Noi sac mau 
x: xanh - xuoi chieu kim dong ho 
n: nau - nguoc chieu kim dong ho 
t: trang - chuyen thang 
h: hong - chuyen tu do 
---------------------------------------*) 
procedure Hnm(n: byte; a,b: byte); 
begin 
if n = 0 then exit; 
if Ke(n,a,b) then 
begin 
Hnm(n-1,a,6-a-b); 
inc(d); 
writeln(f,d,'. ',a,' -> ',b); 
Hnm(n-1,6-a-b,b); 
end else 
begin 
Sáng tạo trong Thuật toán và Lập trình Tập I 
277 
Hnm(n-1,a,b); 
inc(d); 
writeln(f,d,'. ',a,' -> ',6-a-b); 
Hnm(n-1,b,a); 
inc(d); 
writeln(f,d,'. ',6-a-b,' -> ',b); 
Hnm(n-1,a,b); 
end; 
end; 
(* Pascal *) 
(************************************** 
 HNM.PAS – Thỏp Hà Nội màu 
 x – xanh: Xuụi chiều kim đồng hồ 
 n – nõu: Ngược chiều kim đồng hồ 
 t – Trắng: thẳng theo hàng ngang 
 h – Hà Nội cổ: kinh điển 
****************************************) 
uses crt; 
var d: longint; {dem so buoc chuyen} 
 f: text; {output file} 
 s: string; {cau hinh thap} 
{---------------------------------------- 
 Kiem tra tinh chat ke giua 2 coc a va b 
-----------------------------------------} 
function Ke(n,a,b: byte): Boolean; 
begin 
case s[n] of 
'x': ke := (b = (a mod 3)+1); 
'n': ke := (a = (b mod 3)+1); 
't': Ke := (abs(a-b) = 1); 
'h': Ke := True; 
end {case}; 
end; 
(*---------------------------------------- 
Ha Noi sac mau 
x: xanh - xuoi chieu kim dong ho 
n: nau - nguoc chieu kim dong ho 
t: trang - chuyen thang 
h: hong - chuyen tu do 
---------------------------------------*) 
procedure Hnm(n: byte; a,b: byte); tự viết 
{------------------------------- 
 To chuc goi thu tuc Hnm 
------------------------------} 
procedure runHnm(Thap:string); 
begin 
s := Thap; 
d := 0; 
assign(f,'hnm.out'); 
rewrite(f); 
writeln('-----------------'); 
Sáng tạo trong Thuật toán và Lập trình Tập I 
278 
Hnm(length(s),1,2); 
writeln(f,'Total: ',d,' step(s)'); 
close(f); 
readln; 
end; 
BEGIN 
runHnm('txhxn'); 
END. 
// C# 
using System; 
namespace SangTao1 
{ 
 /*------------------------------------ 
 * Thap Ha Noi 
 * -----------------------------------*/ 
 class ThapHaNoi 
 { 
 static int d = 0; 
 static char[] s = new char[64]; 
 static void Main() 
 { 
 Console.WriteLine("\n Ha Noi Sac Mau"); 
 RunHaNoiSacMau("xnxht", 1, 2); 
 Console.WriteLine("\n Total: " + 
 d + " steps"); 
 Console.ReadLine(); 
 } // Main 
 static bool Ke(char KieuThap, int a, int b) 
 { 
 switch (KieuThap) 
 { 
 case 'x': return (b == (a % 3) + 1); 
 case 'n': return (a == (b % 3) + 1); 
 case 't': return (Math.Abs(a - b) == 1); 
 } 
 return true; 
 } 
 /*------------------------------------- 
 Ha Noi sac mau 
 x: xanh - xuoi chieu kim dong ho 
 n: nau - nguoc chieu kim dong ho 
 t: trang - chuyen thang 
 h: hong - chuyen tu do 
---------------------------------------*/ 
void HaNoiSacMau(int n, int a, int b) 
 { 
 if (n == 0) return; 
 if (Ke(s[n], a, b)) 
 { 
 HaNoiSacMau(n - 1, a, 6 - a - b); 
Sáng tạo trong Thuật toán và Lập trình Tập I 
279 
 Console.WriteLine((++d)+ 
". ("+s[n]+") "+a+" -> "+b); 
 HaNoiSacMau(n - 1, 6 - a - b, b); 
 } 
 else 
 { 
 HaNoiSacMau(n - 1, a, b); 
 Console.WriteLine((++d)+ 
 ". ("+s[n]+") " 
 +a+" -> "+(6-a-b)); 
 HaNoiSacMau(n - 1, b, a); 
 Console.WriteLine((++d)+ 
 ". ("+s[n]+")" 
 +(6-a-b) +" -> "+b); 
 HaNoiSacMau(n - 1, a, b); 
 } 
 } 
 static void RunHaNoiSacMau(string w, 
 int a, int b) 
 { 
 d = 0; 
 w.CopyTo(0, s, 1, w.Length); 
 HaNoiSacMau(w.Length, a, b); 
 } 
 } // ThapHaNoi 
} // SangTao1 
Hƣớng dẫn kiểm thử 
Ta sẽ dùng kĩ thuật đối sánh để kiểm thử các trường hợp. 
Ta chọn và cố định các giá trị n, a và b. Chẳng hạn, n = 4, a = 1, b = 2. 
Khi đó ta có: 
RunHn(n) và RunHnm('hhhh') cho cùng kết quả. 
RunHnx(n) và RunHnm('xxxx') cho cùng kết quả. 
RunHnn(n) và RunHnm('nnnn') cho cùng kết quả. 
RunHnt(n) và RunHnm('tttt') cho cùng kết quả. 
Nếu ghi các kết quả này vào các tệp tương ứng, sau đó gọi thủ tục đối sánh từng 
cặp hai tệp tương ứng thì có thể kiểm định được một số trường hợp. 
Để xây dựng các tình huống kiểm thử khác nhau còn lại bạn để ý đến các tính chất 
thuận nghịch của các thủ tục khác nhau. Thí dụ, như đã phân tích ở phần trên, các lời 
gọi Hnx(3,1,2) và Hnn(3,3,1) phát sinh cùng một số lần chuyển. 
Bạn hãy thử phát hiện thêm sự tương đồng giữa các lời gọi Hnm với các tham trị 
khác nhau. 
Sáng tạo trong Thuật toán và Lập trình Tập I 
280 
Đọc thêm 
Lƣơc sử 
Một số bài toán về tháp Hà Nội đã được đưa vào các kì thi Olympic Tin học 
tại một số quốc gia. Chúng ta thử tìm hiểu cội nguồn của các bài toán thuộc 
loại này. 
Năm 1883, trên một tờ báo ở Paris có đăng bài mô tả một trò chơi toán học 
của giáo sư Claus với tên là Tháp Hà Nội. Nội dung trò chơi được mọi người 
say mê làm thử chính là bài toán Tháp Hà Nội cổ. 
Thời đó ở thủ đô Paris dân chúng đổ xô nhau mua đồ chơi này và suốt 
ngày ngồi chuyển tháp. Trong lịch sử về các trò chơi thông minh đã từng có 
những cơn sốt như vậy. Tính trung bình mỗi thế kỉ có một vài cơn sốt trò chơi. 
Thế kỉ thứ XX có cơn sốt Rubic, thế kỉ XIX là các trò chơi 15 và tháp Hà Nội. 
Bài toán này nổi tiếng đến mức trở thành kinh điển trong các giáo trình về thuật 
giải đệ quy và được trình bày trong các thông báo chính thức của các phiên 
bản chuẩn của các ngữ trình như ALGOL-60, ALGOL-68, Pascal, Delphy, C, 
C++, Ada,... khi muốn nhấn mạnh về khả năng đệ quy của các ngôn ngữ đó. 
Theo nhà nghiên cứu Henri De Parville công bố vào năm 1884 thì tác giả 
của trò chơi tháp Hà Nội có tên thật là nhà toán học Eduard Lucas, người có 
nhiều đóng góp trong lĩnh vực số luận. Mỗi khi viết về đề tài giải trí thì ông đổi 
tên là Claus. Bạn có để ý rằng Claus là một hoán vị các chữ cái của từ Lucas. 
De Parville còn kể rằng bài toán tháp Hà Nội bắt nguồn từ một tích truyền 
kì ở Ấn Độ. Một nhóm cao tăng Ấn Độ giáo được giao trọng trách chuyển dần 
64 đĩa vàng giữa ba cọc kim cương theo các điều kiện đã nói ở bài toán Tháp 
Hà Nội cổ. Khi nào hoàn tất công việc, tức là khi chuyển xong toà tháp vàng 64 
tầng từ vị trí ban đầu sang vị trí kết thúc thì cũng là thời điểm tận thế. Sự việc 
này có xảy ra hay không ta sẽ xét ở bài tập 8.10. 
Lời giải được công bố đầu tiên cho bài toán tháp Hà Nội là của Allardice và 
Frase, năm 1884. 
Năm 1994 David G. Poole ở Đại học Trent, Canada đã viết một bài khảo 
cứu cho tờ Mathematics Magazine số tháng 12 nhan đề "Về các tháp và các 
tam giác của giáo sư Claus" cùng với một phụ đề "Pascal biết Hà Nội". Poole 
đã liệt kê 65 công trình khảo cứu bài toán tháp Hà Nội đăng trên các tạp chí 
toán-tin trong khoảng mười năm. Tác giả cũng chỉ ra sự liên quan giữa các 
công thức tính số lần chuyển các tầng tháp và một phương pháp quen biết 
dùng để tính các hệ số của dạng khai triển nhị thức Newton (a + b)
n
. Phương 
pháp này được gọi là Tam giác Pascal, mang tên nhà toán học kiêm vật lí học 
Pháp Blaise Pascal (1623-1662), người đã chế tạo chiếc máy tính quay tay đầu 
tiên trên thế giới. 
Một số nhà nghiên cứu trong và ngoài nước có bàn luận về địa danh 
Hà Nội. Theo tôi vấn đề này vẫn còn ngỏ. Hầu hết các bài viết xoay quanh đề 
tài chuyển tháp nói trên đều dùng thuật ngữ bài toán tháp Hà Nội. Khi giới thiệu 
về bài toán Hà Nội nhiều tháp Dudeney đặt tên là bài toán đố của Reve (The 
Reve's Puzzle). Tuy nhiên, nhiều nhà nghiên cứu cho rằng tốt hơn cả là nên 
đặt tên và phân loại theo tên nguyên thuỷ của bài toán, nghĩa là Tháp Hà Nội. 
Ngoài các dạng Tháp Hà Nội đã liệt kê ở phần trên một số tác giả còn đề 
xuất những dạng khá kì lạ, chẳng hạn như bài toán sau đây. 
Sáng tạo trong Thuật toán và Lập trình Tập I 
281 
Hà Nội nhiều tháp 
Trong trò chơi này người ta làm thêm những cọc, chẳng hạn thay vì ba ta dùng bốn 
cọc và cũng có thể bố trí tháp tại nhiều cọc. Ý kiến này do H.E. Dudeney, một tác giả 
hàng đầu về toán học giải trí người Anh đưa ra vào năm 1908. Đã có nhiều bài đăng lời 
giải cho bài toán này, có những bài mới xuất hiện gần đây vào những năm 1988 và 
1989. Dù vậy chưa ai chứng minh được rõ ràng số lần chuyển của bài giải là tối thiểu 
như đã làm với các dạng tháp Hà Nội khác. 
Bài tập 
Bạn hãy thử lập công thức tính số lần chuyển các tầng tối thiểu cho các bài toán 
sau: 
Tháp Hà Nội, 
Tháp Hà Nội Xuôi, 
Tháp Hà Nội Ngược và 
Tháp Hà Nội Thẳng. 
Lời cảm ơn Các tư liệu trên và một số tư liệu khác trong bài được trích dẫn từ các 
bài viết của giáo sư viện sĩ Nguyễn Xuân Vinh, Khoa Kỹ thuật không gian, Đại học 
Michigan, cộng tác viên NASA, Hoa Kỳ. Tác giả xin chân thành cám ơn giáo sư đã cho 
phép trích dẫn và chỉ giáo về các phương pháp truyền thụ tri thức khoa học cho giới trẻ. 
 NXH 
 8/4/2008 
Sửa ngày 4/4/09 
Sáng tạo trong Thuật toán và Lập trình Tập I 
282 
Nguyễn Xu©n Huy 
s¸ng t¹o trong 
thuËt to¸n 
vµ lËp tr×nh 
víi C#, Pascal 
tuyÓn c¸c bµi to¸n tin n©ng cao 
cho häc sinh vµ sinh viªn giái 
TËp mét 
Lêi giíi thiÖu 
S¸ch tr×nh bµy cã hÖ thèng c¸c ph-¬ng ph¸p thiÕt 
kÕ thuËt to¸n minh häa qua c¸c bµi to¸n thi häc 
sinh giái vµ Olimpic häc sinh vµ sinh viªn trong 
n-íc, khu vùc vµ quèc tÕ. C¸c bµi to¸n ®Òu ®-îc 
ph©n tÝch ®Çy ®ñ kÌm theo thuËt to¸n vµ toµn v¨n 
ch-¬ng tr×nh viÕt trªn ng«n ng÷ C# vµ Pascal. 
S¸ch lµ tµi liÖu bæ Ých cho häc sinh trung häc, 
gi¸o viªn c¸c tr-êng phæ th«ng vµ cao ®¼ng vµ 
sinh viªn c¸c tr-êng ®¹i häc muèn hoµn thiÖn kiÕn 
thøc ®Ó tham dù c¸c kú thi Olimpic Tin häc quèc 
gia vµ quèc tÕ. 
C¸c ch-¬ng tr×nh song ng÷ Pascal vµ C# gióp cho 
b¹n ®äc chuyÓn ®æi nhanh chãng sang c¸c m«i 
tr-êng lËp tr×nh tiªn tiÕn.