By Tương truyền cách đây rất lâu, tại một vùng đất xa xôi của Viễn Đông, thuộc Hà Nội, Việt Nam, vị quân sư của hoàng đế vừa qua đời, và hoàng đế cần một vị quân sư mới thay thế. Bản thân vị hoàng đế cũng là người sáng suốt nên đã đặt ra câu đố rằng ai giải được bài toán này sẽ được phong làm quân sư. Bài toán của hoàng đế là: đưa ra n đĩa (ông không nói chính xác là bao nhiêu) và ba trục: A là trục nguồn, B là trục đích và C là trục trung gian. Những tấm ván này có nhiều kích thước khác nhau và có lỗ ở giữa để có thể cắm cây vào theo quy tắc “lớn nhỏ lên trên”. Đầu tiên, các đĩa này được sắp xếp trên trục A. Vậy làm thế nào để chuyển đổi tất cả các đĩa trên trục B, miễn là chúng được chuyển từng cái một và luôn đảm bảo rằng quy tắc là “nhỏ trên lớn dưới”, để biết rằng L là trục C được sử dụng làm trục chuyển tiếp?
Vì vị trí quân sư được coi như một vinh dự nên có rất nhiều ứng viên. Từ học giả đến nông dân, họ chạy đến để đề xuất giải pháp với hoàng đế. Nhiều giải pháp có hàng nghìn bước và nhiều giải pháp bao gồm từ “chuyển sang bước tiếp theo”. Nhưng hoàng đế cảm thấy mệt mỏi với những giải pháp này, và cuối cùng nói: “Tôi không hiểu những giải pháp này. Phải có một giải pháp khác dễ hiểu và nhanh hơn.” May mắn thay, cuối cùng cũng có một giải pháp như vậy.
Thật vậy, sau khi nhà vua bị trục xuất, một nhà sư trông giống như một quý tộc đã cầu xin hoàng đế giúp đỡ. Quốc sư nói: “Vấn đề của chúng ta rất dễ dàng, hắn hầu như có thể tự mình giải quyết.” Thị vệ trưởng đứng bên cạnh vương phi cau mày nhìn quý phi và muốn đuổi hắn đi, nhưng hoàng thượng vẫn kiên nhẫn nghe. “Nếu chỉ có một tấm thì …; nếu có nhiều hơn một tấm (n> 1) thì …”, giải thích qua loa và điềm tĩnh. Sau một lúc im lặng, cuối cùng hoàng đế cũng sốt ruột nói: “Thôi, ngươi nói cho ta biết biện pháp?” Quý phi không tiếp tục giải thích, mà là cười thật sâu, sau đó liền biến mất, bởi vì hoàng đế rất thông minh, nhưng hiển nhiên Không hiểu ý nghĩa của đệ quy. Nhưng các sinh viên ngày nay có thể thấy rằng giải pháp của nhà sư là đúng.
Văn bản in nghiêng ở trên được lấy từ sách giáo khoa dành cho sinh viên thuật toán và lập trình do hai giáo sư Paul Henman và Robert Veroff đồng biên tập “Cấu trúc dữ liệu và giải quyết vấn đề trung gian” tại Đại học New Mexico và giáo sư Frank Carrano của Đại học Rhode Island.
Ai đã từng biết đến Hanoi Tower thì nên “thử” vì đây là một trò chơi rất thú vị. Bạn có thể bắt đầu với 3 đĩa và sau đó lên đến 4 đĩa. Với 4 đĩa, bạn sẽ bắt đầu tìm ra vấn đề. Ví dụ ở mức 5 hoặc cao hơn, n = 1 triệu, bài toán sẽ trở nên phức tạp đến mức không ai có đủ kiên nhẫn và thời gian để thử từng đĩa một. Tuy nhiên, sư muội dám nói rằng việc này quá dễ dàng! Điều này là do anh ta đã sử dụng tìm kiếm, vui lòng hiển thị-một quy tắc toán học xác định số hạng thứ n từ số hạng n-1 phía trước nó. Cái hay của nhà sư là ông đã tìm ra một quy luật chung, tức là có một thuật toán chung trong tất cả các công đoạn chuyển đĩa.
Do đó, thay vì mô tả lần lượt toàn bộ quá trình truyền dẫn của các đĩa quang như các đối thủ trước đây, nhà sư chỉ mô tả một quy luật chung. Chỉ cần làm theo quy tắc này lặp đi lặp lại mà không cần suy nghĩ, và kết quả cuối cùng là đương nhiên. Do đó, các vị trí cấp cao chỉ ra rằng vấn đề này đã được “giải quyết”.
Trong khoa học máy tính ngày nay, khôi phục là thuật toán cơ bản của lập trình. Ưu điểm của phương pháp trích xuất là nó sử dụng công thức để biểu diễn các phép tính lặp lại, bất kể số lần lặp lại. Nếu số lần lặp lại lên đến hàng trăm tỷ, thì con người không còn sức lực và thời gian để làm việc đó, nhưng máy tính có thể xử lý nó trong nháy mắt. Ưu điểm của máy tính là không sợ hãi và mệt mỏi khi thực hiện các công việc được lặp đi lặp lại hàng triệu tỷ lần. Vì vậy, sự hợp tác giữa máy tính và con người là một hình mẫu lý tưởng cho việc lao động trí óc trong cuộc sống hiện đại.
Về mặt lịch sử, Tháp Hà Nội được phát hiện bởi E. Lucas vào năm 1883, nhưng ý nghĩa hiện đại của nó mãi đến gần đây mới được phát hiện. Hoàn thành. Không rõ tại sao Lucas lại gọi chồng đĩa được đề cập là Tháp Hà Nội thay vì Tháp Bắc Kinh hoặc Tháp Tokyo.
Khi nhiều nghiên cứu đã thúc đẩy Tháp Hà Nội trong tương lai, nó đã mở ra cánh cửa tương lai với Hà Nội là điểm xuất phátThành tựu mới: (1) Nâng vấn đề Tháp Hà Nội lên một cấp độ cao hơn để giảm thiểu số lần chuyển đĩa. Các nhà toán học phát hiện ra rằng các tính chất của Tháp Hà Nội có các tính chất giống như bài toán tìm đường đi Hamilton trên n giả hình vuông (n-hypercube) đã biết. – (2) Nhà toán học DG Poole đã tạo ra đồ thị Hà Nội – một tam giác có các đỉnh tương ứng với cách sắp xếp đĩa trong tháp Hà Nội, do đó tìm ra mối quan hệ thú vị giữa tam giác Pascal và đồ thị Hà Nội. Sự kết nối này đã được công bố trong một dự án mang tên Pascal Knows Hanoi (Pascal Knows Hanoi).
Hiện tại, ở một số trường đại học ở Úc, sinh viên Việt Nam có uy tín về lập trình không kém gì sinh viên Ấn Độ – một cường quốc lập trình toàn cầu, điều này càng làm cho Tháp Hà Nội vốn đã nổi tiếng.
(Tia Sáng)
