Sinh viên thực hiện: Cao Xuân Sơn(1100804)
Vũ Thị Lan Anh(1400006)
Trần Văn Hậu(1400108)
Trần Văn Hậu(1400108)
Giảng viên: Ts. Trần Xuân Thanh
MỤC LỤC
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, 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 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ế với tên gọi Workshop on the Tower of Hanoi
Chương 1: Giới thiệu bài toán
Tháp Hà Nội
Có thể còn ít người Việt Nam
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ừ vị học giả đến bác nông phu, họ đua nhau trình lên
Hoàng đế lời giải của mình. Nhiều lời giải dài tới hàng nghìn bước, và nhiều lời
giải có chữ "chuyển sang bước tiếp theo" (go to). Nhưng hoàng đế thấy
mệt mỏi vì những lời giải đó, nên cuối cùng hạ chiếu: "Ta không hiểu những
lời giải này. Phải có một cách giải nào khác dễ hiểu và nhanh chóng hơn".
May mắn thay, cuối cùng đã có một cách giải như thế.
Thật vậy, ngay sau khi chiếu vua ban ra, một vị
cao tăng trông bề ngoài giống như một kỳ nhân hạ sơn tới xin yết kiến hoàng đế.
Vị cao tăng nói: "Thưa Bệ hạ, bài toán đố đó dễ quá, hầu như nó tự giải
cho nó". Quan trùm cấm vệ đứng hầu ngay bên cạnh vua quắc mắt nhìn gã kỳ
nhân, muốn quẳng gã ra ngoài, nhưng Hoàng đế vẫn kiên nhẫn tiếp tục lắng nghe.
"Nếu chỉ có 1 đĩa, thì...; nếu có nhiều hơn 1 đĩa (n>1), thì...",
cứ thế vị cao tăng bình tĩnh giảng giải. Im lặng được một lát, cuối cùng Hoàng đế
sốt ruột gắt: "Được, thế cao tăng có nói rõ cho ta lời giải hay không cơ
chứ?". Thay vì giải thích tiếp, gã kỳ nhân mỉm cười thâm thúy rồi biến mất,
bởi vì hoàng đế tuy giỏi giang nhưng rõ ràng là chưa hiểu ý nghĩa của phép truy
hồi (recursion). Nhưng các bạn sinh viên ngày nay thì có thể thấy cách giải của
vị cao tăng là hoàn toàn đúng.
Toàn bộ đoạn chữ nghiêng ở trên được trích
nguyên văn từ cuốn sách giáo khoa dành cho sinh viên ngành thuật toán và lập
trình - "giải toán nâng cao và cấu trúc dữ liệu" (intermediate
problem solving and data structures) do Paul Henman và Robert Veroff, hai giáo
sư Đại học New Mexico, cùng biên soạn với Frank Carrano, giáo sư Đại học Rhode
Island (Mỹ).
Bạn nào chưa từng biết Tháp Hà Nội thì cũng
nên "thử sức" một chút xem sao, vì đây là một trò chơi rất thú vị. Bạn
có thể bắt đầu bằng bài toán 3 đĩa, rồi nâng lên 4 đĩa. Với 4 đĩa chắc bạn bắt
đầu thấy rắc rối. Nâng tiếp lên 5 và cao hơn nữa, chẳng hạn n = 1 triệu, bài
toán sẽ rắc rối đến mức không ai đủ kiên trì và đủ thì giờ để thử từng đĩa một.
Vậy mà vị cao tăng dám nói là dễ quá! Xin tiết lộ, ấy là 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.
Vậy thay vì mô tả toàn bộ quá trình chuyển đĩa
từng cái một như những thí sinh trước đó đã làm, vị cao tăng chỉ 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ó".
Trong khoa học tính toán ngày nay, phép truy hồi
là thuật toán cơ bản để lập trình. Ưu điểm của phương pháp truy hồi là ở chỗ nó
dùng một công thức nhất định để diễn tả những phép tính lặp đi lặp lại bất chấp
số lần lặp lại là bao nhiêu. Nếu số lần lặp lại lên đến con số hàng triệu hàng
tỷ thì con người không đủ sức và thời gian để làm, nhưng máy tính thì có thể giải
quyết trong chớp mắt. Điểm mạnh của computer là ở chỗ nó không hề biết e ngại
và mệt mỏi trước những công việc lặp đi lặp lại lên đến hàng triệu hàng tỷ lần.
Và vì thế, việc cộng tác giữa computer với con người là mô hình lý tưởng của
lao động trí óc trong cuộc sống hiện đại.
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.
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 chuyển đĩa là nhỏ nhất. 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.
(2) Nhà toán học D.G. Poole đã sáng tạo ra Lược
Đồ Hà Nội - một tam giác có các đỉnh tương ứng với các cách sắp xếp đĩa trong
Tháp Hà Nội, từ đó tìm ra những liên hệ lý thú giữa Tam giác Pascal với Lược đồ
Hà Nội. Liên hệ này đã được công bố trong một công trình mang một cái tên đầy
liên tưởng: Pascal biết Hà Nội (Pascal knows Hanoi
Hiện nay, tại một số đại học ở Australia, uy
tín của sinh viên Việt Nam trong lĩnh vực lập trình được đánh giá ngang với
sinh viên Ấn Độ - một cường quốc lập trình của thế giới, làm cho Tháp Hà Nội vốn
đã nổi tiếng lại càng nổi tiếng hơn.
Chương 2: Bài toán và cách giải bài
toán Tháp Hà Nội
2.1
Phát biểu bài toán Tháp Hà Nội
Có 3 cọc
A,B,C. Trên cọc A có một chồng gồm n cái đĩa đường kính giảm dần từ dưới lên
trên cân phải chuyển chồng đĩa từ cọc A sang cọc C tuân thủ quy tắc: mỗi lần chỉ
được chuyển 1 đĩa và chỉ được xếp đĩa có đường kính nhỏ hơn lên đĩa có đường
kính lớn hơn. Trong quá trình chuyển được phép dùng cọc B làm cọc trung gian.
Bài toán có 2 chiều, chiều nghịch dùng
để phân tích bài toán và dùng để lập trình, chiều thuận để thực hiện trên mô
hình. Ở đây nguyên lí thực hiện (tức là cách hiểu bài toán) nằm ở chiều nghịch,
còn cách thực hiện nằm ở chiều thuận. Chiều nghịch dùng cho dân lập trình và
chiều thuận dành cho dân toán.
Chiều nghịch thì dân lập trình hay gọi là bài
toán đệ qui. Bài toán này có ví dụ đơn giản như sau: giaithừa(n)=giaithừa(n-1)*n.
Muốn tính giai thừa của n thì đơn giản, lấy n nhân với giai thừa của (n-1). Còn
giai thừa của (n-1) thì tính sao? Đơn giản, cứ lấy (n-1) nhân với giai thừa của
(n-2) …
2.2.1. Chiều nghịch (nguyên lí)
Muốn đưa n khối tròn từ cột A (cột nguồn)
sang cột C (cột đích) thông qua cột B (cột trung gian) thì chỉ cần đưa (n-1) khối
tròn từ A qua B, rồi đưa 1 khối tròn từ A qua C và cuối cùng là đưa (n-1) khối
tròn từ B qua C. Đã làm xong bài toán!!!
Còn (n-1) khối tròn từ A sang B thì làm sao mà
đưa? Đơn giản, khi đó xem A là cột nguồn, B là cột đích và C là cột trung gian.
Việc tiến hành tương tự, đưa (n-2) khối từ cột nguồn qua cột trung gian, 1 khối
từ cột nguồn sang cột đích và cuối cùng là (n-2) khối từ cột trung gian sang cột
đích.
2.2.2. Chiều thuận
Nói đơn giản để hiệu thì như chiều nghịch đã nói. Còn thực
hiện (chiều thuận) thì làm sao? Khối tròn đầu tiên từ cột nguồn A thì chuyển
vào đâu? Cột trung gian B hay cột đích C?
Với khối tròn đầu tiên thì chuyển về cột đích
(với n là số lẻ) và cột trung gian (với n là số chẳn). Xếp được 1 khối tròn (khối
nhỏ nhất) theo đúng yêu cầu thì tiếp theo là xếp 2 khối tròn theo đúng yêu cầu
(2 khối nhỏ nhất và nhỏ nhì). Cứ xếp 2 khối đó vào cột còn lại so với lần đầu
tiên và làm tiếp vớ 3, 4, … khối tròn. Điều vừa nói được diễn đạt như sau:
Với n lẻ: cách xếp các khối như sau. Đầu tiên
là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài
toán với n=2) ….
• 1 khối nhỏ nhất qua C (cột đích)
• 2 khối nhỏ nhất qua B (cột trung gian)
• 3 khối nhỏ nhất qua C (cột đích)
• 4 khối nhỏ nhất qua B (cột trung gian)
• Tiếp tục như trên
Với n chẳn: cách xếp các khối như sau. Đầu
tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất
(bài toán với n=2) ….
• 1 khối nhỏ nhất qua B (cột trung gian)
• 2 khối nhỏ nhất qua C (cột đích)
• 3 khối nhỏ nhất qua B (cột trung gian)
• 4 khối nhỏ nhất qua C (cột đích)
• Tiếp tục như trên
Phát triển của cách làm trên: Muốn chuyển n khối
tròn từ cột nguồn sang cột đích thì làm như sau (ở đây ta phải hiểu rõ cột nguồn
không nhất thiết là cột A, cột đích là C hay cột trung gian là B mà phải hiểu tổng
quát, có thể cột nguồn là B chẳng hạn (trong phép chuyển (n-1) cột từ cột B
sang cột C như trong cách làm ở phần nghịch)):
Với n lẻ: cách xếp các khối như sau. Đầu tiên
là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất (bài
toán với n=2) ….
• 1 khối nhỏ nhất qua cột đích
• 2 khối nhỏ nhất qua cột trung gian
• 3 khối nhỏ nhất qua cột đích
• 4 khối nhỏ nhất qua cột trung gian
• Tiếp tục như trên
Với n chẳn: cách xếp các khối như sau. Đầu
tiên là xếp được 1 khối nhỏ nhất (bài toán với n=1). Sau đó xếp 2 khối nhỏ nhất
(bài toán với n=2) ….
• 1 khối nhỏ nhất qua cột trung gian
• 2 khối nhỏ nhất qua cột đích
• 3 khối nhỏ nhất qua cột trung gian
• 4 khối nhỏ nhất qua cột đích
• Tiếp tục như trên
- Như vậy thì số lần chuyển cho bài toán là
bao nhiêu? Với bài toán tháp Hà Nội chuyển n khối tròn từ cột
nguồn A sang cột đích C thông qua cột trung gian B thì cần có 2^0 + 2^1 + 2^2 +
… + 2^n lần chuyển
Chương 3: Giải bài toán Tháp Hà Nội bằng thuật toán đệ
quy(DevC++)
3.1. Thuật toán đệ
quy giải bài toán
3.2. Chương trình
3.3. Kết quả chương
trình
Kết quả chương trình
với n=1.
Kết quả chương trình
với n=2.
Kết quả chương trình
với n=3.
Kết quả chương trình
với n=4.
KẾT LUẬN
Trong bài tập lớn này, chúng em
đã trình bày được khái quát lịch sử của bài toán Tháp Hà Nội, thuật toán đệ quy
của bài toán và mô phỏng chương trình. Bài làm còn sơ sài mong thầy và các bạn
bỏ qua cho chúng em. Em xin chân thành cảm ơn!
TÀI LIỆU THAM KHẢO
[1] Phạm Trà Ân, Bài toán Tháp Hà Nội, Tạp chí
Toán học và Tuổi trẻ, số 280, tháng 10.2000.
[2] Phạm Trà Ân, Bài toán Tháp Hà
Nội-Cái nhìn từ lý thuyết Độ phức tạp tính toán, Tạp chí Thông tin Toán học, Tập
6 Số 2, tháng 8 năm 2002, trang 10-13.
[3] Vũ Đình Hòa, Bài toán Tháp Hà
Nội, Tạp chí Toán Tuổi thơ 2, Số 68, tháng 10.2008.
[4] Tạ Duy Phượng, Trò chơi Tháp Hà Nội-Lịch sử
và bài toán tổng quát, Tạp chí Toán học và Tuổi trẻ, số 280, tháng 1.2010.
[5] Tạ Duy Phượng, Trò chơi Tháp Hà Nội và những
bài toán liên quan (Bản thảo), 150 trang.
[6] Nguyễn Xuân Tấn, Bài toán “Tháp Hà Nội”-một
bài toán hóc búa hơn một trăm năm nay, Tạp chí Thông tin Toán học, Tập 6 Số 1,
tháng 3 năm 2002, trang 2-4.
[7] Các bài trên các trang WEB viết
về trò chơi Tháp Hà Nội.
Download chương trình: https://drive.google.com/file/d/0B5fbXrMbFIyBeTFsalJEVUtzRlk/view?usp=sharing
Không có nhận xét nào:
Đăng nhận xét