Trang chủ » Blog » [Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội – Hanoi Tower

[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội – Hanoi Tower

bởi ngoctran2 | 23/07/2024 08:32 | Blog | Thuật toán

Để hưởng ứng sức nóng của chuỗi series “Mỗi ngày 1 thuật toán”, CodeGym sẽ đem đến cho bạn lời giải chi tiết cho bài toán kinh điển – Tháp Hà Nội. Không chỉ cung cấp mã nguồn Java, Python, bài viết dưới đây còn trình bày mã nguồn dạng Pseudo-code. Điều này giúp người đọc có cái nhìn rõ ràng hơn về giải thuật.

1. Ý tưởng chính của bài toán Tháp Hà Nội

Thuật toán Tháp Hà Nội (Hanoi Tower) là một bài toán cổ điển trong khoa học máy tính, được đề cập lần đầu tiên vào năm 1883. Bài toán Tháp Hà Nội như sau:

  • Có 3 cọc (A, B, C)
  • Trên cọc A có n đĩa (các đĩa có kích thước khác nhau, lớn nhất ở dưới, nhỏ nhất ở trên)
  • Mục tiêu là chuyển toàn bộ n đĩa từ cọc A sang cọc C, với điều kiện:
    • Chỉ được chuyển 1 đĩa tại một thời điểm
    • Không được đặt một đĩa lớn hơn lên trên một đĩa nhỏ hơn

2. Thuật toán giải quyết 

  • Di chuyển n – 1 đĩa từ cọc A sang cọc B (sử dụng cọc C làm trung gian)
  • Di chuyển đĩa lớn nhất từ cọc A sang cọc C
  • Di chuyển n – 1 đĩa từ cọc B sang cọc C (sử dụng cọc A làm trung gian)
  • Độ phức tạp của thuật toán này là: 2^n – 1 bước di chuyển.

3. Hình ảnh minh hoạ bài toán Hanoi Tower với 3 đĩa

[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội

4. Hình ảnh minh hoạ bài toán Hanoi Tower với 4 đĩa

[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội

5. Mã nguồn Pseudo-code

[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội

  • Hàm hanoi(n, fromPeg, auxPeg, toPeg) là hàm đệ quy để giải quyết bài toán Tháp Hà Nội với n đĩa.
  • Nếu n = 1, chỉ cần di chuyển đĩa từ fromPeg sang toPeg bằng cách gọi hàm moveDisk().
  • Nếu n > 1, thực hiện ba bướ c:
    • Di chuyển n-1 đĩa từ fromPeg sang auxPeg bằng cách gọi đệ quy hanoi(n-1, fromPeg, toPeg, auxPeg).
    • Di chuyển đĩa lớn nhất từ fromPeg sang toPeg bằng cách gọi hàm moveDisk().
    • Di chuyển n-1 đĩa từ auxPeg sang toPeg bằng cách gọi đệ quy hanoi(n-1, auxPeg, fromPeg, toPeg).
  • Hàm moveDisk(fromPeg, toPeg) di chuyển đĩa từ fromPeg sang toPeg.

6. Mã nguồn Java

[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội

7. Mã nguồn Python

[Mỗi ngày 1 thuật toán] Bài toán Tháp Hà Nội

 

Xem thêm các bài viết thú vị về Thuật toán tại đây!

0 Lời bình

Gửi Lời bình

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

BÀI VIẾT LIÊN QUAN

BẠN MUỐN HỌC LẬP TRÌNH?

GỌI NGAY

098 953 44 58

Đăng ký tư vấn lộ trình học lập trình

Đăng ký tư vấn, định hướng lộ trình học và giải đáp các thắc mắc về ngành nghề – Miễn phí – Online.

8 + 8 =

TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM
TƯ VẤN VỀ LỘ TRÌNH HỌC NGHỀ LẬP TRÌNH TẠI CODEGYM