Bài toán tháp Hà Nội là gì? Khám phá thuật toán đệ quy kinh điển trong lập trình

Bài toán tháp Hà Nội là một trong những thuật toán kinh điển thường được sử dụng để giảng dạy về đệ quy trong lập trình. Với cách hoạt động thú vị và yêu cầu tư duy logic cao, bài toán này giúp người học hiểu rõ cách chia nhỏ và xử lý vấn đề hiệu quả. Trong bài viết dưới đây, hãy cùng FPT Shop tìm hiểu nguyên lý hoạt động và cách giải chi tiết của bài toán tháp Hà Nội.

Bài toán tháp Hà Nội là gì?

Tháp Hà Nội (Tower of Hanoi) là một bài toán kinh điển được nhà toán học người Pháp Édouard Lucas giới thiệu vào năm 1883. Tên gọi của bài toán được lấy cảm hứng từ thủ đô Hà Nội của Việt Nam và đến nay vẫn được sử dụng rộng rãi trong lĩnh vực toán học, khoa học máy tính và lập trình.

Theo truyền thuyết, trong một ngôi đền cổ có ba cọc cùng 64 đĩa vàng với kích thước khác nhau. Các nhà sư phải di chuyển toàn bộ số đĩa từ cọc đầu tiên sang cọc cuối cùng theo đúng quy tắc. Người ta tin rằng khi hoàn thành nhiệm vụ này thì thế giới sẽ kết thúc, khiến bài toán càng trở nên nổi tiếng và thú vị hơn.

Bài toán tháp Hà Nội gồm ba cọc được ký hiệu là A, B và C cùng nhiều đĩa có kích thước khác nhau. Ban đầu, tất cả đĩa được xếp ở cọc A theo thứ tự từ lớn đến nhỏ. Mục tiêu là di chuyển toàn bộ đĩa sang cọc C bằng cách sử dụng cọc B làm trung gian.

Trong quá trình di chuyển, người chơi chỉ được phép chuyển một đĩa mỗi lần và không được đặt đĩa lớn lên trên đĩa nhỏ. Dù nguyên tắc khá đơn giản nhưng khi số lượng đĩa tăng lên, số bước xử lý sẽ tăng rất nhanh. Chính vì vậy, bài toán này thường được dùng để minh họa cho phương pháp đệ quy trong lập trình.

Cách giải bài toán tháp Hà Nội

Để giải bài toán tháp Hà Nội, chúng ta sẽ sử dụng phương pháp đệ quy nhằm chia bài toán lớn thành nhiều bước nhỏ hơn. Ý tưởng chính của thuật toán là trước tiên di chuyển n - 1 đĩa sang cọc trung gian, sau đó chuyển đĩa lớn nhất sang cọc đích và cuối cùng tiếp tục di chuyển n - 1 đĩa còn lại sang cọc đích.

Ví dụ với 3 đĩa, đầu tiên chúng ta sẽ chuyển 2 đĩa nhỏ từ cọc A sang cọc B. Sau đó, đĩa lớn nhất được di chuyển từ cọc A sang cọc C. Cuối cùng, 2 đĩa ở cọc B sẽ tiếp tục được chuyển sang cọc C để hoàn thành bài toán.

Số bước tối thiểu để giải bài toán được tính theo công thức:

2n - 1

Với n = 3, số bước cần thực hiện sẽ là:

23 - 1 = 7

Dù cách giải nghe có vẻ đơn giản, nhưng khi số lượng đĩa tăng lên thì số bước xử lý cũng tăng rất nhanh. Đây cũng là lý do bài toán tháp Hà Nội thường được sử dụng để minh họa cho tư duy đệ quy trong lập trình.

Code giải bài toán tháp Hà Nội

Giải bài toán tháp Hà Nội bằng Pseudo-code

Pseudo-code là dạng mô tả thuật toán bằng ngôn ngữ gần giống lập trình nhưng đơn giản và dễ hiểu hơn. Trước khi triển khai bằng các ngôn ngữ như Python, Java hay C++, người học thường sử dụng Pseudo-code để hình dung cách hoạt động của thuật toán.

Với bài toán tháp Hà Nội, Pseudo-code sẽ mô tả rõ cách chương trình sử dụng đệ quy để chia nhỏ bài toán thành nhiều bước đơn giản hơn. Điều này giúp người học dễ nắm bắt logic xử lý trước khi đi vào code thực tế.

Pseudo-code của bài toán thường được viết như sau:

Trong đoạn mã trên, hàm hanoi() sẽ liên tục gọi lại chính nó với số lượng đĩa giảm dần. Khi chỉ còn một đĩa, chương trình sẽ thực hiện di chuyển trực tiếp và kết thúc lời gọi đệ quy.

Thông qua Pseudo-code, người học có thể dễ dàng hiểu được cấu trúc tổng quát của thuật toán. Đây cũng là bước nền tảng giúp việc chuyển sang các ngôn ngữ lập trình thực tế trở nên đơn giản hơn.

Giải bài toán tháp Hà Nội bằng C++

C++ là một trong những ngôn ngữ lập trình phổ biến khi học cấu trúc dữ liệu và giải thuật. Nhờ khả năng xử lý mạnh mẽ cùng cú pháp rõ ràng, C++ thường được sử dụng để minh họa các bài toán đệ quy như tháp Hà Nội.

Trong chương trình C++, thuật toán sẽ sử dụng hàm đệ quy để giảm dần số lượng đĩa cần di chuyển. Khi số đĩa bằng 1, chương trình sẽ thực hiện thao tác di chuyển trực tiếp từ cọc nguồn sang cọc đích.

Đoạn code C++ giải bài toán tháp Hà Nội như sau:

Trong đoạn chương trình trên, mỗi lời gọi hàm sẽ chia bài toán thành hai bài toán nhỏ hơn trước khi xử lý đĩa lớn nhất. Đây cũng là nguyên lý hoạt động đặc trưng của phương pháp đệ quy trong lập trình.

Giải bài toán tháp Hà Nội bằng Java

Java là ngôn ngữ lập trình hướng đối tượng được sử dụng rất phổ biến trong giảng dạy thuật toán. Với cú pháp dễ đọc và khả năng quản lý chương trình tốt, Java là lựa chọn phù hợp để triển khai bài toán tháp Hà Nội.

Tương tự C++, chương trình Java cũng sử dụng đệ quy để giảm số lượng đĩa sau mỗi lần gọi hàm. Quá trình này tiếp tục cho đến khi chỉ còn một đĩa và chương trình thực hiện di chuyển trực tiếp.

Đoạn code Java cho bài toán tháp Hà Nội như sau:

Khi chạy chương trình, Java sẽ hiển thị lần lượt từng bước di chuyển đĩa giữa các cọc theo đúng quy tắc của bài toán. Điều này giúp người học dễ dàng theo dõi và kiểm tra logic xử lý của thuật toán.

Giải bài toán tháp Hà Nội bằng Python

Python là ngôn ngữ lập trình nổi bật nhờ cú pháp ngắn gọn và dễ đọc. Vì vậy, nhiều người mới học lập trình thường lựa chọn Python để tìm hiểu các thuật toán cơ bản, trong đó có bài toán tháp Hà Nội.

So với C++ hay Java, code Python của bài toán này đơn giản hơn nhưng vẫn giữ nguyên nguyên lý hoạt động của đệ quy. Chương trình sẽ liên tục giảm số lượng đĩa cho đến khi đạt điều kiện dừng.

Đoạn code Python cho bài toán tháp Hà Nội như sau:

Trong đoạn chương trình trên, hàm hanoi() sẽ gọi lại chính nó với số lượng đĩa giảm dần sau mỗi lần xử lý. Khi chỉ còn một đĩa, chương trình sẽ thực hiện thao tác di chuyển trực tiếp và kết thúc đệ quy.

Tạm kết

Qua bài viết trên, FPT Shop đã giúp bạn giải bài toán tháp hà nội thông qua nhiều phương pháp và ngôn ngữ lập trình khác nhau như Python, Java, C++ hay Pseudo-code. Hy vọng những thông tin này sẽ giúp bạn hiểu rõ cách hoạt động của thuật toán, đồng thời nâng cao khả năng tư duy logic và kỹ năng lập trình hiệu quả hơn.

Để hỗ trợ lập trình hiệu quả, xử lý thuật toán mượt mà và tối ưu trải nghiệm học tập, bạn hãy tham khảo ngay các dòng laptop MSI tại FPT Shop. Với hiệu năng mạnh mẽ, thiết kế hiện đại cùng khả năng đa nhiệm ổn định, đây sẽ là lựa chọn phù hợp cho học sinh, sinh viên và lập trình viên. Hãy tham khảo ngay tại FPT Shop!

Xem thêm:

• Tìm hiểu chu trình Euler từ bài toán bảy cây cầu đến ứng dụng thực tiễn
• Giải thuật là gì? Mách bạn cách tìm hiểu và thiết kế giải thuật chi tiết từ A – Z