Tháp Hà Nội
Trong bài tập này, bạn sẽ hiện thực trò chơi Tháp Hà Nội bằng một thuật toán đệ quy. Mục tiêu là chuyển toàn bộ đĩa từ một trong ba cọc sang cọc khác, theo các quy tắc sau:
- Mỗi lần chỉ được di chuyển một đĩa.
- Chỉ được lấy đĩa ở trên cùng của một chồng và đặt lên trên cùng của chồng khác.
- Không được đặt đĩa lớn lên trên đĩa nhỏ.
Thuật toán minh họa là một triển khai trò chơi này với bốn đĩa và ba cọc có tên 'A', 'B' và 'C'. Mã nguồn có hai lỗi. Thực tế, nếu bạn chạy, nó sẽ làm treo console do vượt quá độ sâu đệ quy tối đa. Bạn có thể tìm và sửa các lỗi đó không?
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Sửa trường hợp cơ sở.
- Sửa các lần gọi hàm
hanoi().
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def hanoi(num_disks, from_rod, to_rod, aux_rod):
# Correct the base case
if num_disks >= 0:
# Correct the calls to the hanoi function
hanoi(num_disks, from_rod, aux_rod, to_rod)
print("Moving disk", num_disks, "from rod", from_rod,"to rod",to_rod)
hanoi(num_disks, aux_rod, to_rod, from_rod)
num_disks = 4
source_rod = 'A'
auxiliar_rod = 'B'
target_rod = 'C'
hanoi(num_disks, source_rod, target_rod, auxiliar_rod)