Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC SƢ PHẠM

NGUYỄN THỊ HỒNG PHƢỢNG
THUẬT TOÁN FRAME – STEWART GIẢI BÀI TOÁN
THÁP HÀ NỘI TỔNG QUÁT
LUẬN VĂN THẠC SĨ TOÁN HỌC

LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: Giải tích
Mã số: 60 46 01

Người hướng dẫn khoa học: PGS. TS. TẠ DUY PHƢỢNG
THÁI NGUYÊN - 2010 Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

1
MỤC LỤC
Trang
MỤC LỤC
LỜI NÓI ĐẦU 2
Chƣơng 1 4


Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

2
LỜI NÓI ĐẦU Trò chơi (Bài toán) Tháp Hà Nội được phổ biến rộng rãi ở Paris năm
1883 bởi nhà toán học Edouard Lucas, là một bài toán nổi tiếng thế giới, hiện
nay đang được nghiên cứu bởi rất nhiều nhà toán học và khoa học máy tính,
các chuyên gia giáo dục và y học, được đưa vào nhiều giáo trình tin học và
sách về trò chơi toán học như một ví dụ điển hình về thuật toán đệ qui và lập
trình căn bản, nhưng hình như chưa được chú ý nghiên cứu ở Việt Nam. Mặc
dù trò chơi Tháp Hà Nội có mặt trên khá nhiều trang WEB và giáo trình tiếng
Việt, số lượng bài viết tiếng Việt giới thiệu về trò chơi và bài toán Tháp Hà
Nội trên các tạp chí là rất ít và còn rất sơ lược (xem [1]-[6]), hình như chưa có
bài nghiên cứu tiếng Việt nào về bài toán Tháp Hà Nội, trong khi đó chỉ tính
riêng số bài báo nghiên cứu về bài toán Tháp Hà Nội trong lĩnh vực Toán-Tin
học đã có đến hơn 450 bài với khoảng 250 bài với đầu đề có cụm từ "The
Tower of Hanoi", đăng trên hơn 100 tạp chí khoa học uy tín (trong [5] thống
kê số lượng bài báo khoa học viết về Tháp Hà Nội là 464 bài). Đó là chưa kể
đến những bài viết về sử dụng bài toán Tháp Hà Nội trong khoa học giáo dục
và y học. Trò chơi Tháp Hà Nội thú vị đến mức nó đã được dùng làm đề tài
của một số luận án Tiến sĩ và luận văn cao học. Một hội thảo khoa học quốc
tế [21] với tên gọi Workshop on the Tower of Hanoi and Related Problems đã
được tổ chức năm 2005.
Bài toán Tháp Hà Nội không chỉ thú vị ở chỗ nó mang tên Hà Nội, thủ
đô của Việt nam, mà nó hấp dẫn các nhà Toán-Tin học bởi nó liên quan đến
nhiều vấn đề như giải thuật đệ qui, hệ đếm, tam giác Pascal, thảm Sierpinski,
lý thuyết đồ thị và chu trình Hamilton, ôtômát hữu hạn, độ phức tạp tính

học trường ĐHSP Thái Nguyên đã quan tâm giúp đỡ, tạo điều kiện thuận lợi
cho tôi thực hiện kế hoạch học tập của mình.
Xin cảm ơn người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tôi trong
suốt quá trình làm luận văn.
Thái Nguyên, 19.8.2010 Nguyễn Thị Hồng Phượng

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

4
Chƣơng 1
TỔNG QUAN VỀ TRÒ CHƠI THÁP HÀ NỘI
§1. Lịch sử trò chơi Tháp Hà Nội

Bìa cuốn sách của E. Lucas xuất bản tại Paris năm 1895, trong đó có 4
trang (179-183) viết về trò chơi Tháp Hà Nội.
1.1 Truyền thuyết
Theo một truyền thuyết, liên tục suốt ngày đêm, các nhà tu hành của tòa
tháp Brahma trong thành Bernares (Ấn Độ) phải chuyển 64 đĩa vàng từ một
cọc này sang cọc khác của tòa tháp. Các đĩa có kích thước khác nhau và lúc

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

5
đầu được đặt trên một trong ba cọc của tòa tháp theo thứ tự đĩa nhỏ ở trên, đĩa
lớn ở dưới. Đĩa trên cùng được chuyển sang cọc khác, mỗi lần chỉ di chuyển
một đĩa. Do tính dễ vỡ, đĩa lớn không được đặt lên trên đĩa nhỏ. Trong quá
trình di chuyển, có thể đặt đĩa lên một cọc trung gian. Khi công việc hoàn

Tháp Hà Nội”. Nếu có tư liệu khẳng định nhà toán học nổi tiếng E. Lucas đã
đến Hà Nội từ trước năm 1883 (Pháp chiếm Hà Nội năm 1882) thì thật là thú
vị. Tuy nhiên, lúc đó E. Lucas đã ra khỏi quân đội và đang dạy học, vì vậy ít
có khả năng ông đã đến Hà Nội.
Cũng có lẽ Cột cờ Hà Nội đã gợi ý cho E.
Lucas đặt tên trò chơi của mình là Tháp Hà
Nội: “The Flag Tower of Hanoi may have
served as the inspiration for the name”. Cột cờ
Hà Nội có đáy gồm ba khối vuông xây chồng
lên nhau. Trò chơi Tháp Hà Nội đơn giản nhất
cũng gồm ba đĩa tròn xếp chồng lên nhau. Cột
cờ Hà Nội xây năm 1805-1812, Tháp Rùa xây
năm 1886, trò chơi Tháp Hà Nội xuất hiện ở
Paris 1883.
Có thể Pháp chiếm Hà Nội là đề tài thời sự
ở Paris vào những năm 1882-1883, và điều này
gợi ý E. Lucas đặt tên cho trò chơi của mình là
Tháp Hà Nội?
Trò chơi Tháp Hà Nội vừa được phổ biến
đã được đón nhận rộng rãi vì sự đơn giản và hấp
dẫn của nó. Mặc dù chưa có câu trả lời rõ ràng
về lí do E. Lucas đặt tên cho trò chơi của mình
là trò chơi Tháp Hà Nội, người Việt Nam vẫn có
thể tự hào và cần quan tâm về trò chơi này.
Dưới đây là bìa của hộp đựng trò chơi
Tháp Hà Nội sản xuất lần đầu tiên tại Paris năm
1883 và hai tờ hướng dẫn qui tắc chơi. Đây là
những tư liệu quí về lịch sử trò chơi.
bởi chính phủ Trung Hoa. Tháp Hà Nội có các đĩa, nhỏ dần, có số lượng thay
đổi, mà chúng tôi làm bằng gỗ, có lỗ ở giữa. Ở Nhật Bản, Trung Quốc, và ở
Đông Kinh, chúng được làm bằng sứ.
Trò chơi có mục đích là dỡ bỏ từng đĩa, và đặt vào cột bên cạnh, theo
các quy tắc nhất định. Vui và bổ ích, dễ học và dễ chơi trong thành phố, ngoài
nông thôn, trên chuyến du lịch, nó được tạo ra để mang đến kiến thức khoa
học, giống mọi trò chơi kỳ thú và mới lạ của giáo sư N. CLAUS (của SIAM).
Chúng tôi trao giải thưởng 1000 franc, 100 nghìn franc, một triệu franc,
và nhiều hơn, cho ai hoàn thành, bằng việc dùng tay di chuyển tháp Hà Nội
với 64 đĩa, theo quy tắc của trò chơi. Chúng tôi nói ngay là cần số lần di
chuyển là:
18 446 744 073 709 551 615, nhiều hơn năm tỷ thế kỷ!
Theo một truyền thuyết Ấn Độ, những người Brahmin đã tiếp nối nhau
trong một thời gian dài để thay đổi Đền Bernares, di chuyển 64 đĩa vàng của
Tòa tháp Brahma. Khi công việc hoàn thành, Tòa tháp và Brahmin sẽ đổ, và
lúc đó là thời điểm kết thúc của vũ trụ!
PARIS, BẮC KINH, TOKYO và SÀI GÒN
Trong các hiệu sách và tiểu thuyết
1883
Bản quyền đã giữ.

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

10

Bản dịch tờ hướng dẫn trò chơi Tháp Hà Nội được sản xuất lần đầu tại Paris:
Luật chơi và cách chơi trò chơi THÁP HÀ NỘI
Đế đặt nằm ngang; các cọc thẳng đứng. Các đĩa đặt theo thứ tự từ lớn đến
nhỏ từ thấp lên cao, tạo nên một Tòa tháp. Trò chơi đòi hỏi di chuyển các đĩa,
bằng cách đặt chúng vào cọc bên cạnh, mỗi lần chuyển một đĩa, theo luật sau:

8 đĩa
255 lần

Với tốc độ một di chuyển mất một giây, cần bốn phút để chuyển tám đĩa.
Các biến thể của trò chơi: Có thể thay đổi đến vô cùng điều kiện của
bài toán tháp Hà Nội như sau. Khi bắt đầu, xếp các đĩa theo thứ tự bất kỳ lên
một, hai, hay cả ba cọc. Sau đó cần xây dựng lại tòa tháp trên một cọc định
trước. Với 64 đĩa, số lần di chuyển là khổng lồ, số này dài 50 chữ số. Xem
thêm chi tiết trong chương nói về Baguenaudier (trò chơi tháo vòng) ở:
TOÁN HỌC GIẢI TRÍ
bởi Mr. Édouard Lucas
giáo sư toán học cao cấp tại Lycée Saint-Louis
Hai tập nhỏ, trong hai màu
Paris, 1883, bởi GAUTHER-VILLARS,
máy in của Académie des Sciences và Ecole Polytechnique
Trên mạng Internet có rất nhiều chương trình hiển thị minh họa và hướng
dẫn trò chơi Tháp Hà Nội (với ba cọc). Ngoài ra, có thể tìm mua trò chơi
Tháp Hà Nội làm bằng gỗ hoặc sứ tại các cửa hàng Việt Nam hoặc nước
ngoài để giải trí.
Dưới đây chúng tôi chụp lại bốn trang (179-183) viết về Tháp Hà Nội
trong cuốn sách Số học vui của E.Lucas xuất bản năm 1895 (sau khi Ông mất)

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

12
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên


đơn giản và tối ưu.
Một mở rộng tự nhiên của bài toán Tháp Hà Nội với ba cọc là Bài toán
Tháp Hà Nội với bốn (hoặc nhiều) cọc.
Theo một số tài liệu, chính tác giả của bài toán Tháp Hà Nội, E. Lucas
cũng là người đầu tiên xét bài toán với nhiều cọc vào năm 1899. Năm 1902-
1903 Henry Ernest Dudeney đã viết về bài toán Tháp Hà Nội với bốn cọc
trong hai bài báo. Trong hai trang đầu tiên của cuốn sách nổi tiếng của Ông
The Canterbury Puzzles (xem [7]) ông đã viết về bài toán này (và gọi là

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

16
Reve's puzzle) với số cọc là 4 và số đĩa là 8, 10 hoặc 21, chỉ có khác là Ông đã
thay các đĩa bằng các quân cờ. Trong phần lời giải (trang 131-132), Dudeney
đã khẳng định (không chứng minh) rằng số lần chuyển cần thiết tương ứng
với 8, 10 hoặc 21 đĩa là 33, 49 hoặc 321. Hơn nữa, Ông còn xét trường hợp
với số đĩa là số tam giác, tức là các số
( 1)
2
k
kk
t


,
1,2, k 
Giả sử
( 1)
2
k

4
6 17M 
,
 
4
10 49M 
,… Tuy nhiên Dudeney không cho một thuật toán
nào cho phép tìm ra các số này, và cũng không có một gợi ý nào cho trường
hợp số đĩa không phải là số tam giác, thí dụ khi
8n 
.
Bài toán tổng quát với
3p 
cọc,
p
là số bất kì với số đĩa
n
bất kì được
B. M. Stewart đề xuất năm 1939 (Problem 3918 trong tạp chí The Americal
Mathematical Montly [17]). Lời giải của bài toán này đã được Stewart [19] và
Frame [9] trình bày cũng trong tạp chí này năm 1941. Các thuật toán của
Stewart và Frame cùng với một số thuật toán cải biên khác đã được chứng
minh là tương đương theo nghĩa số lần chuyển đĩa là bằng nhau (xem [11]).
Vì vậy người ta thường gọi thuật toán của hai ông hoặc các thuật toán cải biên
tương tự là thuật toán Frame- Stewart. Thuật toán Frame-Stewart cùng các
thuật toán tương đương sẽ được trình bày trong Chương 3 và Chương 4.
Thuật toán Stewart (1941)
Thuật toán truy hồi do Stewart đề xuất 1941, được coi là presumably-
optimal solution (lời giải giả định là tối ưu) cho bài toán bốn cọc (hoặc nhiều
hơn). Giả sử

cọc còn lại (vì cọc 1 đang được dùng để chứa
l
đĩa nhỏ
nhất), mất
1
()
p
S n l


lần chuyển.
Bước 3. Cuối cùng, chuyển
l
đĩa trên cùng từ cọc 1 tới cọc đích, mất
()
p
Sl

lần chuyển nữa. Được phép sử dụng tất cả các cọc.
Như vậy, tổng cộng cần
1
2 ( ) ( )
pp
S l S n l


lần chuyển.
Bài toán đặt ra là, cần tính số
l
để tổng này là nhỏ nhất.

lk
, trong khi đó nếu
1kk
t n t


thì cả hai
giá trị
1k 
và
k
đều là cách chọn tối ưu cho
l
. Như vậy, Stewart và Frame
đã đề xuất thuật toán hiển cho bài toán Tháp Hà Nội với bốn cọc. Thuật toán
này trùng với lời giải của Dudeney trong các trường hợp riêng nêu trên. Từ
đây ta cũng có nhận xét rằng, khác với trường hợp bài toán với ba cọc, lời giải
cho bài toán với bốn cọc có thể là không duy nhất.
Otto Dunkel, tổng biên tập của tạp chí The Americal Mathematical
Montly khi cho đăng hai lời giải trên đã chỉ ra rằng chứng minh tính tối ưu
của Frame và Stewart chỉ áp dụng được cho các thuật toán của một lược đồ
chung mô tả bởi Frame và Stewart mà thôi. Nói cách khác, Frame và Stewart
mới chỉ chứng minh rằng trong số tất cả các giá trị có thể của
l
theo thuật

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

18
toán của hai ông phải có ít nhất một giá trị

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

19
2.2.1 Bài toán Tháp Hà Nội với vị trí bất kì
Bài toán Tháp Hà Nội với ba cọc và
n
đĩa đã được E. Lucas cải biên ngay
khi phổ biến cách chơi năm 1883. Đó là trò chơi Tháp Hà Nội với vị trí bất kì:
có thể coi vị trí của đĩa là bất kì (không nhất thiết phải tất cả các đĩa nằm trên
một cọc, mà có thể ở trên các cọc khác nhau, miễn là tuân theo qui tắc “đĩa ở
trên nhỏ, đĩa nằm dưới to”). Bài toán đã được Hinz nghiên cứu khá kĩ.
2.2.2 Bài toán Tháp Hà Nội quay vòng (cyclic moving)
Có thể đóng ba cọc trên ba đỉnh của một tam giác và chuyển động các
đĩa theo chiều quay của kim đồng hồ hoặc ngược lại.
2.2.2 Bài toán Tháp Hà Nội song song (parallel moving)
Có thể chuyển các đĩa từ cọc này sang cọc khác trong cùng một thời gian.
2.2.2 Bài toán Tháp Hà Nội hỗn hợp
Kết hợp giữa bài toán Tháp Hà Nội quay vòng với chuyển động song song.
Các cải biên của bài toán Tháp Hà Nội đặt ra những bài toán mới thú vị,
có thể nói khó không kém bài toán ban đầu.
2.3 Một số vấn đề toán học liên quan đến bài toán Tháp Hà Nội
Nhiều bài toán của toán học và tin học thú vị xuất hiện trong trò chơi
Tháp Hà Nội. Dưới đây liệt kê một vài vấn đề chính.
2.3.1 Đồ thị Hà Nội
Các nhà toán học đã phát hiện ra rằng Tháp Hà Nội có cùng bản chất với
bài toán tìm đường Hamilton (Hamilton Path) trên một hình giả phương cấp
n
(
n
-Hypercube), một bài toán cũng rất nổi tiếng.

và điều trị thần kinh tâm lý đối với các chức năng thực hành. Những vấn đề
này không được đề cập trong luận văn này

Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên

21
Chƣơng 2
TRÒ CHƠI THÁP HÀ NỘI

§1 Trò chơi tháp Hà Nội và thuật giải đệ qui
Luật chơi của trò chơi Tháp Hà Nội đã được qui định rõ trong tờ hướng
dẫn thứ hai khi Trò chơi Tháp Hà Nội được phổ biến lần đầu tại Paris năm
1883 (xem Chương 1). Trong cuốn sách của mình, E. Lucas mô tả trò chơi
gồm 8 đĩa ([12], trang 180-181). Dưới đây trình bày lời giải bài toán Tháp Hà
Nội với ba cọc và số đĩa
n
bất kì.
Bài toán 1
Có
n
đĩa kích thước nhỏ dần xếp chồng lên nhau trên một cọc (được gọi
là cọc nguồn, cọc A), đĩa lớn ở dưới, đĩa nhỏ ở trên. Ngoài cọc nguồn còn có
hai cọc trống khác, được gọi là cọc đích và cọc trung gian (cọc B và cọc C).
Hãy chuyển các đĩa này từ cọc nguồn sang cọc đích (một trong hai cọc B
hoặc C) tuân theo hai qui tắc sau:
Qui tắc 1. Mỗi lần chỉ được chuyển một đĩa từ cọc này sang cọc khác và
được dùng cọc thứ ba làm cọc trung chuyển.
Qui tắc 2. Không được xếp đĩa lớn nằm trên đĩa nhỏ.
Giải
Trước tiên ta xét bài toán với 1, 2, 3 đĩa.

Bài toán với 4 đĩa: cần 15 lần chuyển (Hình 4)
Với
4n 
ta minh họa các bước chuyển đĩa như Hình 4 dưới đây.
Dòng 1 cột 1 biểu thị cả bốn đĩa nằm trên cọc A.

Hình 4
Trước tiên ta giải bài toán ba cọc (mất 7 lần chuyển):
Lần 1 (dòng 2 cột 1): Chuyển đĩa trên cùng (số 1) từ cọc A sang cọc C.
Lần 2 (dòng 3 cột 1): Chuyển đĩa số 2 từ cọc A sang cọc B.
Lần 3 (dòng 4 cột 1): Chuyển đĩa số 1 từ cọc C sang cọc B (cọc C trống).
Lần 4 (dòng 5 cột 1): Chuyển đĩa số 3 từ cọc A sang cọc B.
Lần 5 (dòng 6 cột 1): Chuyển đĩa số 1 từ cọc C sang cọc A.
Lần 6 (dòng 7 cột 1): Chuyển đĩa số 2 từ cọc C sang cọc B (cọc C trống).
Lần 7 (dòng 8 cột 1): Chuyển đĩa số 1 từ cọc A sang cọc B.
Như vậy, sau 7 lần chuyển, bài toán với 3 cọc và 3 đĩa đã giải xong.
Lần 8 (dòng 1 cột 2): Chuyển đĩa số 4 từ cọc A sang cọc C.
Tiếp theo lại giải bài toán ba cọc: Chuyển ba đĩa từ cọc B sang cọc C (mất
thêm 7 lần chuyển):