Tháp Hà Nội – Wikipedia tiếng Việt

Tháp Hà Nội là một trò chơi toán học. Tên gọi của trò chơi này gắn liền với yếu tố Việt Nam.

Bìa hộp đựng những game show Tháp Hà Nội được Pháp sản xuất lần đầu .

Dạng thường gặp nhất của trò chơi này gồm một bộ các đĩa kích thước khác nhau, có lỗ ở giữa, nằm xuyên trên ba cái cọc. Bài toán đố bắt đầu bằng cách sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Yêu cầu của trò chơi là di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:

• Chỉ có 3 cột để di chuyển.
• Một lần chỉ được di chuyển một đĩa (không được di chuyển đĩa nằm giữa).
• Một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất).

Trò chơi Tháp Hà Nội hoàn toàn có thể đã Open ở Đông Á từ thế kỷ 19 hoặc trước đó. Các đĩa được làm bằng sứ ở Trung Quốc, Nhật Bản và Nước Ta .Trò chơi này được đưa sang phương Tây lần đầu bởi nhà toán học người Pháp Edouard Lucas vào năm 1883 .Trò chơi này nhanh gọn được những nhà toán học nghiên cứu và điều tra sau đó, và trở thành ví dụ về giải pháp giải đệ quy tầm cỡ trong dạy học và tin học. Lời giải tối ưu cho game show hoàn toàn có thể tìm thấy đúng chuẩn cho trường hợp 3 cọc. Nhưng khi lan rộng ra cho 4 cọc hoặc nhiều hơn, giải thuật đúng chuẩn cho đến nay vẫn chưa được khẳng định chắc chắn .Các phiên bản tiên phong được Pháp sản xuất, kèm theo tờ minh họa ngoài bìa và hai tờ hướng dẫn .

Tờ thứ nhất[sửa|sửa mã nguồn]

Tờ hướng dẫn thứ nhất của game show Tháp Hà Nội được Pháp sản xuất lần đầu .

“THÁP HÀ NỘI
Trò chơi trí tuệ của An nam
Trò chơi được đem về từ Bắc Kì
Bởi giáo sư N. CLAUS (của SIAM)
Trường Cao đẳng Quan Li-Sou-Stian!

Trò chơi này được tìm thấy, lần đầu, trong cuốn sách được minh họa Quan thoại FER-FER-TAM-TAM, đang được xuất bản, trong tương lai gần, 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à ở Bắc Kì, chúng được làm bằng sứ.
Trò chơi có mục đích là dỡ bỏ các đĩ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, trạm kim cương từ Golconde. 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, Ý ĐÔ và SÀI GÒN
Trong các hiệu sách và tiệm bán hàng mới lạ
1883

Bản quyền đã giữ”

Tờ thứ hai[sửa|sửa mã nguồn]

Tờ hướng dẫn thứ hai của game show Tháp Hà Nội được Pháp sản xuất lần đầu .” Luật chơi và cách chơi trò THÁP HÀ NỘI

Đế đặt nằm ngang; các cột 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ột bên cạnh, một đĩa trong một di chuyển, theo luật sau:
I. — Sau mỗi di chuyển, các đĩa đều nằm trên một, hai, hoặc ba cột, theo thứ tự từ lớn đến nhỏ từ thấp đến cao.
II. — Đĩa trên cùng của một trong ba cột đĩa được đặt vào cột rỗng.
III. — Đĩa trên cùng của một trong ba cột đĩa được đặt lên một cột đĩa khác, nếu đĩa này nhỏ hơn các đĩa của cột này.

Trò chơi có thể dễ dàng tự khám phá, bằng việc giải quyết dần từ 3, 4, và 5 đĩa.

Trò chơi luôn giải được và đòi hỏi thời gian chơi lâu khoảng gấp đôi mỗi khi cho thêm một đĩa vào Tòa tháp. Bất kỳ ai giải được cho tám đĩa, ví dụ, chuyển các đĩa từ cột 1 sang cột 2, cũng sẽ biết cách giải cho chín đĩa. Chỉ cần chuyển tám đĩa sang cột 3, rồi chuyển đĩa thứ chín sang cột 2, và mang tám đĩa từ cột 3 về cột 2. Bây giờ, khi thêm một đĩa vào trò chơi, tổng số di chuyển tăng gấp đôi, cộng với một, so với trước.

vân vân.
Với tốc độ một di chuyển trong 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ột. Sau đó cần xây dựng lại tòa thấp trên một cột định trước. Với 64 đĩa, số lần di chuyển là khổng lồ; số này dài 20 chữ số.
Xem thêm chi tiết trong chương nói về Baguenaudier ở:

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à École Polytechnique

Quai des Augustins, 55″

Trong truyện khoa học viễn tưởng cổ điển Now Inhale (Hít vào nào) của Eric Frank Russell (trong Astounding Science Fiction tháng 4 năm 1939, cũng như trong nhiều tuyển tập văn học khác), có một người anh hùng là tù nhân trên một hành tinh nơi mà luật địa phương bắt tù nhân chơi một trò chơi đến khi thắng hay thua thì thôi, sau đó sẽ tiến hành hành quyết ngay. Người anh hùng được biết là chỉ được chơi trong ngục với các thiết bị đơn giản tuân thủ luật chơi đã được định rõ trước khi chơi và không thể thay đổi được nữa khi trò chơi đã bắt đầu, và trò chơi có điểm kết thúc hữu hạn. Trò chơi và cuộc hành quyết sau đó sẽ được truyền hình khắp hành tinh, và xem người tù vô vọng cố gắng vật lộn với trò chơi càng lâu càng tốt là một thứ giải trí thật hấp dẫn; kỷ lục trước đây là mười sáu ngày. Người anh hùng đã tính toán rằng một con tàu giải cứu có thể mất cả năm hoặc hơn mới đến nơi được nên đã chọn chơi trò Tháp Hà Nội với 64 đĩa để đợi con tàu đến cứu. Khi dân địa phương nhận ra điều đó, họ rất tức tối nhưng theo luật chơi thì không thể làm gì được. Có lẽ họ sẽ thay đổi luật chơi đối với những tù nhân tương lai.

Cách giải trong thực tiễn[sửa|sửa mã nguồn]

( Trên ) Lời giải cho 3 đĩa. ( Dưới ) Lời giải cho 4 đĩa . Tái tạo lại trang trong phần này để xem sự đối sánh tương quan giữa hai giải thuật .Nhiều cách giải đã được tăng trưởng trong bài toán tháp Hà Nội. Ở đây ra mắt một cách chơi trong thực tiễn .Lần lượt vận động và di chuyển đĩa 1 và một trong những đĩa lớn hơn. Nếu có hai đĩa lớn hơn thì phải chuyển đĩa nhỏ lên đĩa lớn. Khi chuyển một đĩa số lẻ, luôn chuyển nó một cọc theo chiều kim đồng hồ đeo tay ; khi chuyển một đĩa số chẵn, luôn chuyển nó một cọc ngược chiều kim đồng hồ đeo tay .

Một cách dễ hơn để nhớ cách giải là chú ý đĩa nhỏ nhất sẽ được chuyển mỗi lần di chuyển thứ hai, và luôn được chuyển theo cùng chiều. Trong các lần chuyển đĩa nhỏ nhất, chỉ có một lần chuyển hợp lệ mà không phải chuyển đĩa nhỏ nhất thêm một lần nữa.

Cách giải khác[sửa|sửa mã nguồn]

Mục đích của bài toán là triển khai được nhu yếu của game show. Dạng bài toán thông dụng nhất là : ” Người chơi được cho ba cái cọc và 1 số ít đĩa có kích cỡ khác nhau hoàn toàn có thể cho vào những cọc này. Ban đầu sắp xếp những đĩa theo trật tự size vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải chuyển dời hàng loạt số đĩa sang một cọc khác, tuân theo những quy tắc sau :

• một lần chỉ được di chuyển một đĩa
• một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)”.

Bài toán này có giải thuật đúng mực. Tuy nhiên những lan rộng ra cho trường hợp có nhiều hơn ba cọc cho đến nay vẫn chưa được giải cặn kẽ .Đa số những game show dạng này có 8 đĩa. Đối với người mới chơi thì có vẻ khó nhưng thật ra thuật giải của nó rất là đơn thuần :

Thuật giải đệ quy[sửa|sửa mã nguồn]

• đặt tên các cọc là A, B, C — những tên này có thể chuyển ở các bước khác nhau (ở đây: A = Cọc Nguồn, B = Cọc Trung Gian, C = Cọc Đích)
• gọi n là tổng số đĩa
• đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng)

Để chuyển n đĩa từ cọc A sang cọc C thì cần :

1. chuyển n-1 đĩa từ A sang B. Chỉ còn lại đĩa n trên cọc A
2. chuyển đĩa n từ A sang C
3. chuyển n-1 đĩa từ B sang C cho chúng nằm trên đĩa n

Phương pháp trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho n-1.

Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho n = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc C.

Giải thích thuật giải[sửa|sửa mã nguồn]

( Trên ) Lời giải cho 3 đĩa. ( Dưới ) Lời giải cho 4 đĩa . Tái tạo lại trang trong phần này để xem sự đối sánh tương quan giữa hai giải thuật .Sau đây là dạng dễ xem hơn của thuật giải này :

1. chuyển đĩa 1 sang cọc C
2. chuyển đĩa 2 sang cọc B
3. chuyển đĩa 1 từ C sang B sao cho nó nằm lên 2

Vậy ta hiện có 2 đĩa đã nằm trên cọc B, cọc C hiện thời trống

1. chuyển đĩa 3 sang cọc C
2. lặp lại 3 bước trên để chuyển 1 & 2 cho nằm lên 3

Mỗi lần dựng xong tháp từ đĩa i đến 1, chuyển đĩa i+1 từ cọc A là cọc xuất phát, rồi lại di chuyển tháp đã dựng lên đĩa i+1.

Giải thuật bằng trình diễn nhị phân[sửa|sửa mã nguồn]

Các vị trí đĩa hoàn toàn có thể xác lập được trực tiếp từ màn biểu diễn nhị phân của số thứ tự chuyển dời ( cơ số 2 với một chữ số cho mỗi đĩa ) trong đó những dãy 1 và những dãy 0 tượng trưng cho những dãy những đĩa liền nhau trên cùng cọc, và mỗi khi chữ số có đổi khác thì đĩa sau đó sẽ dời sang trái hay phải một cọc ( hay chuyển sang cọc ngoài cùng phía đối lập ). Chữ số ở đầu đại diện thay mặt cho đĩa lớn nhất và nếu là chữ số 0 thì có nghĩa là đĩa lớn nhất không dời khỏi cọc xuất phát và ngược lại. Đặt những chữ số 1 và 0 luân phiên bên dưới những chữ số của một bước chuyển được cho phép biết được vận động và di chuyển theo một chiều khi nó hợp với chữ số của bước chuyển tại nơi chữ số đổi khác và theo chiều kia khi nó không hợp. Do đó bước chuyển 00000000 … có nghĩa là đặt 8 đĩa lớn nhất lên cọc khởi đầu, bước chuyển 11111111 … có nghĩa là đặt chúng lên cọc ở đầu cuối, và bước chuyển 11011000 … có hai đĩa lớn nhất trên cọc đích, đĩa tiếp theo trên cọc xuất phát, hai đĩa tiếp theo ở cọc trung gian, và ba đĩa tiếp theo nữa trên cọc xuất phát, bất kể có thêm bao nhiêu chữ số đại diện thay mặt những đĩa nhỏ hơn. Ta hoàn toàn có thể thuận tiện tính được những vị trí của những đĩa trong một bộ tám mươi đĩa sau một số ít những bước tiến, nếu số lượng giới hạn đủ lớn để chứa nó. Việc dùng giải pháp đệ quy cho trường hợp tám mươi đĩa như thế này hoàn toàn có thể không thực tiễn .
Tháp Hà Nội là một bài toán thường được dùng để dạy về lập trình cơ bản. Một phiên bản bằng hình của bài toán này được lập trình trong chương trình soạn thảo emacs, hoàn toàn có thể truy vấn được bằng cách gõ M-x hanoi. Ngoài ra cũng có một thuật giải mẫu viết bằng ngôn từ Prolog .Bài toán Tháp Hà Nội thường được dùng trong điều tra và nghiên cứu tâm ý về cách xử lý yếu tố. Cũng có những biến thể khác của bài toán này gọi là Tháp Luân Đôn dùng trong chẩn đoán và điều trị thần kinh tâm ý so với những công dụng thực hành thực tế .

Trường hợp bốn cọc trở lên[sửa|sửa mã nguồn]

Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó.

Mặc dù không biết được đúng chuẩn cần bao nhiêu lần chuyển dời, hoàn toàn có thể có một vài tác dụng tiệm cận. Có một ” giải thuật được coi như tối ưu ” hoàn toàn có thể vận dụng một cách đệ quy để tìm một lời giải – xem lý giải cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer ( tiếng Anh ) .Mặc dù với số đĩa nhỏ thử nghiệm trên máy tính thì ” giải thuật được coi như tối ưu ” này là thực sự tối ưu, nhưng nó vẫn chưa có một chứng tỏ tổng quát để coi là thực sự tối ưu. Tuy nhiên, những hiệu quả nghiên cứu và điều tra trong năm 2004 Lưu trữ 2005 – 09-05 tại Wayback Machine ( tiếng Anh ) đã cho thấy giải thuật được coi như tối ưu phải nằm trong cùng độ lớn với giải thuật tối ưu .

Liên kết ngoài[sửa|sửa mã nguồn]

Source: https://mix166.vn
Category: Hỏi Đáp