K8 TIN Đại Học Hùng Vương
TRƯỜNG ĐẠI HỌC HÙNG VƯƠNG
KHOA TOÁN – CÔNG NGHỆ
******o0o******
Báo cáo bài tiểu luận
MÔN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
Đề tài:
TÌM HIỂU VỀ BÀI TOÁN THÁP HÀ NỘI
Giảng viên hướng dẫn:
Nguyễn Thị Hảo
Nhóm sinh viên thực hiện:
1. Trương Thị Thúy Hương
2. Nguyễn Hoàng Phong
3. Lã Thị Ánh Tuyết
4. Nguyễn Thị Châm
5. Nguyễn Thị Thanh Huyền
6. Nguyễn Quang Trung
- 1 -
K8 TIN Đại Học Hùng Vương
MỤC LỤC
Trang
Lời nói đầu 3
Chương 1. MỞ ĐẦU VỀ BÀI TOÁN 4
1.1. Tìm hiểu bài toán 4
1.2. Phân tích & đánh giá ban đầu 5
Chương 2. GIẢI THUẬT ĐỆ QUY
THUẬT TOÁN & CÀI ĐẶT CHƯƠNG TRÌNH 6
2.1. Sơ lược về giải thuật đệ quy 6
2.1.1. Khái niệm đệ quy 6
2.1.2. Giải thuật đệ quy 6
2.1.3.Thiết kế giải thuật đệ quy 6

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 toán,v.v Bài toán Tháp Hà Nội gợi ý cho
nhiều nghiên cứu trong khoa học máy tính và toán học.
Chính vì thế nhóm Sv k8 Tin chọn đề tài này để cùng các bạn khám phá
những gì còn bí ẩn sau bài toán THÁP HÀ NỘI.
- 3 -
K8 TIN Đại Học Hùng Vương
Chương 1.
MỞ ĐẦU VỀ BÀI TOÁN
1.1. Tìm hiểu bài toán
Có thể còn ít người Việt Nam biết Tháp Hà Nội, nhưng rất nhiều thanh
niên sinh viên trên toàn thế giới lại biết đến nó. Đó là vì, Tháp Hà Nội là tên
một bài toán rất nổi tiếng trong Chương trình khoa học tính toán (Computing
Science) dành cho sinh viên những năm đầu tại các trường đại học ở nhiều
nơi trên thế giới.
Bài toán hay trò chơi tháp Hà Nội được nhắc tới trong rất nhiều tài liệu.
Tương truyền rằng: Ngày xửa ngày xưa, lâu lắm rồi, ở một vùng xa xôi viễn
đông, thành phố Hà Nội của Việt Nam, vị quân sư của Hoàng đế vừa qua đời,
Hoàng đế cần một vị quân sư mới thay thế. Bản thân Hoàng đế cũng là một
nhà thông thái, nên ngài đặt ra một bài toán đố, tuyên bố ai giải được sẽ
được phong làm quân sư. Bài toán của Hoàng đế là: cho n cái đĩa (ngài
không nói chính xác là bao nhiêu) và ba cái trục: A là trục nguồn, B là trục
đích, và C là trục trung chuyển. Những cái đĩa có kích cỡ khác nhau và có lỗ
ở giữa để có thể lồng vào trục, theo quy định "nhỏ trên lớn dưới". Đầu tiên,
những cái đĩa này được xếp tại trục A. Vậy làm thế nào để chuyển toàn bộ
các đĩa sang trục B, với điều kiện chuyển từng cái một và luôn phải đảm bảo
quy định "nhỏ trên lớn dưới", biết rằng trục C được phép sử dụng làm trục
trung chuyển?
Vì địa vị quân sư được coi là vinh hiển nên có rất nhiều người dự thi.

tăng nêu trên lại nói là dễ quá! Vì vị đó đã sử dụng phép truy hồi, một quy tắc
toán học cho phép xác định số hạng thứ n từ số hạng đứng trước nó, tức số
hạng thứ n-1. Cái giỏi của vị cao tăng là ông tìm ra một quy tắc chung, tức
một thuật toán chung cho tất cả các bước chuyển đĩa.
Thay vì mô tả toàn bộ quá trình chuyển đĩa từng cái một, người ta đã mô
tả một quy tắc chung. Cứ làm theo quy tắc đó, lặp đi lặp lại chẳng cần suy
nghĩ gì, rồi cuối cùng tự nhiên sẽ tới đích. Vì thế vị cao tăng nói rằng bài toán
này "tự nó giải nó".
Và vì vậy, một hướng tối ưu để giải quyết bài toán này là bằng cách sử
dụng phép truy hồi, hay còn được gọi là phép đệ quy.
- 5 -
K8 TIN Đại Học Hùng Vương
Chương 2.
GIẢI THUẬT ĐỆ QUY
THUẬT TOÁN & CÀI ĐẶT CHƯƠNG TRÌNH
2.1. Sơ lược về giải thuật đệ quy
2.1.1. Khái niệm đệ quy
Ta nói một đối tượng là đệ quy (recursive algorithm) nếu nó bao gồm
chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
Ví dụ:
1. Số tự nhiên
a) 1 là một số tự nhiên
b) x là số tự nhiên nếu x-1 là số tự nhiên
2. Hàm n giai thừa: n!
a) 0! = 1
b) Nếu n > 0 thì n! = n(n-1)!
2.2.2. Giải thuật đệ quy
Nếu lời giải của bài toán T được thực hiện bằng lời giải của một bài
toán T’, có dạng giống T, thì đó là một lời giải đệ quy. Giải thuật tương tự với
lời giải như vậy gọi là giải thuật đệ quy.

- Chuyển (n-1) đĩa trên từ c1 sang c3
- Chuyển đĩa thứ n từ c1 sang c2
- Chuyển (n-1) đĩa từ c3 sang c2
Một cách tổng quát, khi không còn là một đĩa, toàn bộ quá trình thực
hiện di chuyển được chia làm 3 giai đoạn:
Giai đoạn 1: chuyển n-1 đĩa trên từ cọc gốc đến cọc trung gian
Giai đoạn 2: chuyển một đĩa (đĩa thứ n) từ cọc gốc đến cọc đích
Giai đoạn 3: chuyển n-1 đĩa từ cọc trung gian đến cọc đích
- 7 -
K8 TIN Đại Học Hùng Vương
Có thể hình dung việc thể hiện 3 giai đoạn này theo mô hình:

- 8 -
K8 TIN Đại Học Hùng Vương
Để giải quyết các giai đoạn trên, ta đưa ra một chương trình con
“dich_chuyen” với cấu trúc như sau:
dich_chuyen(n_dia, tu_coc, toi_coc, coc_trung_gian);
procedure dich_chuyen(n, c1, c2, c3:integer);
begin
if n=1 then writeln(c1, ‘ -> ‘,c2) else
begin
dich_chuyen(n-1, c1, c3, c2);
dich_chuyen( 1, c1, c2, c3);
dich_chuyen(n-1, c3, c2, c1);
end;
end;
Trong đoạn chương trình con trên, tại sao ta phải có lời gọi đệ quy của
chính nó tới 3 lần? Bởi vì mỗi một lần gọi như vậy thể hiện một giai đoạn vừa
kể trên. Ban đầu, ta muốn di chuyển toàn bộ n đĩa từ cọc gốc (c1) sang cọc
đích (c2). Muốn làm được công việc đó, trước hết phải kiểm tra xem số đĩa

hiện tiếp các lệnh tiếp theo:
- Chuyển 1 đĩa từ cọc (c1) sang cọc (c2).
- Chuyển n-1 đĩa từ cọc (c3) sang cọc (c2).
Đến đây, toàn bộ quá trình đệ quy trên lại được lặp lại. Bắt đầu mức 2
của câu lệnh thứ 3. Và cứ như vậy, bài toán dịch chuyển 3 đĩa đã được hoàn
thành.
Mô tả lại toàn bộ quá trình như sau:
{muc 1} dich_chuyen(3, c1, c2, c3);
{muc 2} dich_chuyen(2, c1, c3, c2);
{muc 3} dich_chuyen(1, c1, c2, c3);
dich_chuyen(1, c1, c3, c2);
dich_chuyen(1, c2, c3, c1);
dich_chuyen(1, c1, c2, c3);
dich_chuyen(2, c3, c2, c1);
{muc 2} dich_chuyen(1, c3, c1, c2);
dich_chuyen(1, c3, c2, c1);
dich_chuyen(1, c1, c2, c3);
Như vậy, bài toán Tháp Hà Nội tổng quát với n đĩa được dẫn đến bài
toán tương tự với kích thước nhỏ hơn. Và ta đã có lời giải cho bài toán tháp
Hà Nội rất nổi tiếng.Việc áp dụng thuật toán đệ quy vào việc giải quyết bài
toán này là một trong những giải pháp tối ưu nhất, dễ nghiên cứu, dễ hiểu.
- 10 -
K8 TIN Đại Học Hùng Vương
2.3. Cài đặt chương trình
Program thaphanoi;
uses crt;
var
n: integer;
procedure dich_chuyen(n, c1, c2, c3:integer);
begin

 Ta có quan hệ đệ quy như sau :
T(1)=O(1)
T(n) = O(1)+T(n-1)
Từ đó ta tính được độ phức tạp của bài toán là:
O(n)=T(n)=2
n

Chương 3.
Ý NGHĨA CỦA BÀI TOÁN
3.1. Về khoa học
Tháp Hà Nội còn sử dụng trong nghiên cứu giáo dục về giải quyết vấn
đề, trong chuẩn đoán và điều trị thần kinh sinh lí đối với các chức năng thực
hành
3.2. Trong lĩnh vực nghiên cứu toán-tin
Đó là giải thuật đệ quy, 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 toán,
3.3.Trong lĩnh vực giải trí
Tháp Hà Nội là một trò chơi trí tuệ rất vui, bổ ích, dễ học, dễ chơi, rèn
luyện tính kiên nhẫn.
- 12 -
K8 TIN Đại Học Hùng Vương
4.4. Về mặt lịch sử
Tháp Hà Nội được E. Lucas phát hiện từ năm 1883, nhưng mãi đến gần đây
người ta mới nhận ra ý nghĩa hiện đại của nó. Hiện vẫn chưa rõ vì sao Lucas
lại gọi chồng đĩa trong bài toán là Tháp Hà Nội, mà không gọi là Tháp Bắc
Kinh, hay Tháp Tokyo.
4.5. Thành tựu
Tháp Hà Nội đã mở tung cánh cửa cho tương lai khi nhiều nghiên cứu
lấy Tháp Hà Nội làm điểm xuất phát đã đạt được thành tựu mới:
(1) Nâng câu hỏi của Tháp Hà Nội lên một mức cao hơn, sao cho số lần

+ Thuyết Trình: Phong.
- 14 -