Dọn đĩa nhỏ trước khi chuyển đĩa lớn nhất
Gọi Hanoi(n,i,j,k) là nhiệm vụ chuyển n đĩa từ cọc i sang cọc j, dùng cọc k làm trung gian. Với n=1, chỉ chuyển đĩa ấy từ i sang j. Với n>1, chia thành ba pha:
1. Chuyển n−1 đĩa nhỏ từ i sang k, dùng j làm trung gian.
2. Chuyển đĩa lớn nhất n từ i sang j.
3. Chuyển n−1 đĩa nhỏ từ k sang j, dùng i làm trung gian.
Pha 1 làm lộ đĩa n và giữ cọc đích trống. Sau pha 2, đĩa n nằm dưới cùng ở đích; mọi đĩa nhỏ đều có thể được đặt lên nó trong pha 3. Hai pha chuyển chồng nhỏ hơn dùng lại đúng bài toán ban đầu.
Ba pha có số lần chuyển khác nhau
Với ba đĩa từ cọc 1 sang cọc 3, pha đầu chuyển hai đĩa nhỏ sang cọc 2 bằng ba lần chuyển. Pha giữa chỉ chuyển đĩa 3. Pha cuối chuyển hai đĩa nhỏ từ cọc 2 sang cọc 3 bằng ba lần chuyển nữa.
Tổng là 3+1+3=7 lần chuyển đĩa. Một pha chuyển nhiều đĩa vẫn phải được thực hiện qua các lần chuyển từng đĩa; không nhấc cả chồng một lúc.
Tên cọc giữ nguyên, vai trò thay đổi
Thứ tự đối số là **n, nguồn, đích, trung gian**. Vì vậy hai lời gọi nhỏ là `Hanoi(n-1,i,k,j)` và `Hanoi(n-1,k,j,i)`.
Chẳng hạn `Hanoi(4,'A','C','B')` cần chuyển bốn đĩa từ A sang C. Lời gọi đầu là `Hanoi(3,'A','B','C')`: B trở thành đích của ba đĩa nhỏ, còn C tạm làm trung gian. Sau khi chuyển đĩa 4 từ A sang C, lời gọi cuối là `Hanoi(3,'B','C','A')`.
Số đĩa giảm nhưng không được giữ nguyên vai trò ba cọc trong cả hai lời gọi; như vậy mới đặt chồng nhỏ đúng nơi để chuyển đĩa lớn.
Bài luyện
Với Hanoi(4,'A','C','B'), lời gọi đầu để dọn ba đĩa nhỏ là gì?
Số đĩa phải giảm từ 4 xuống 3.
Đó là lời gọi cuối, sau khi đĩa 4 đã chuyển.
Ba đĩa nhỏ đi từ nguồn A sang trung gian B, dùng C làm trung gian của bài toán nhỏ.
Chồng nhỏ bị đưa tới đích C trước đĩa lớn nhất.
Lời giải
Lời gọi đầu có dạng Hanoi(n−1,i,k,j). Thay n=4, i=A, j=C, k=B được Hanoi(3,A,B,C): ba đĩa nhỏ được dọn sang B.
Bài luyện
Theo ba pha cho n=3, từ cọc 1 sang cọc 3, thao tác ở pha giữa là gì?
Không được chuyển hai đĩa cùng một lần.
Đó không phải thao tác chuyển đĩa lớn nhất của pha giữa.
Cọc 2 đang chứa các đĩa nhỏ nên không đặt đĩa 3 lên đó.
Sau pha đầu, hai đĩa nhỏ đã ở cọc 2 và cọc 3 rỗng.
Lời giải
Pha 1 đưa hai đĩa nhỏ sang cọc 2, làm lộ đĩa 3 ở nguồn và để cọc 3 rỗng. Pha giữa chỉ chuyển đĩa 3 từ cọc 1 sang cọc 3.
Bài luyện
Ba pha trong hình cho n=3 gồm tổng cộng bao nhiêu lần chuyển đĩa?
Hai pha nhỏ có ba lần chuyển mỗi pha; pha giữa có một.
3 là số pha, chưa phải số lần chuyển.
6 còn thiếu lần chuyển đĩa lớn nhất.
Không phải cả ba pha đều có ba lần chuyển.
Lời giải
Pha đầu cần 3 lần, pha giữa 1 lần và pha cuối 3 lần. Vì vậy tổng số lần chuyển đĩa là 3+1+3=7.
Đang học