詳加解釋河內塔問題的演算法則

Question

Procedure Hanoi(X, Z, Y; N : integer);
{
if(N = 1) then "Move disk from Peg X to Peg Y";
else
{
Hanoi(X, Y, Z, N-1);
"Move disk from Peg X to Peg Y";
Hanoi(Z, X, Y, N-1);
}
}

Answer 1

　　「河內塔」為最基本的「遞迴」問題，而「遞迴」的觀念在於把問題本身一次複雜的計算，化成稍微簡單然而多次的計算，然後把每一個計算，依同樣的方法，再化成更簡單然而多次的計算，直到這個計算變成基本計算為止。
　　如果要把塔由 X 搬到 Y，以下是整個程序的說明：
1. 將塔的上面 N-1 層搬到 Z 暫放。
2. 把最下層的塔搬到 Y 放定位。
3. 把 Z 暫放的 N-1 層塔搬到 Y，結束。
　　你可能要問，1 次不是只能搬 1 層塔而已嗎？程序 1, 3 怎麼搬了 N - 1 層？我們的確不能搬動 N-1 層，但是當我們可以搬動 N-1 層時，搬動 N 層就不是問題了。因此搬動 N 層的問題，在此被化簡為 1 次的 1 層搬動與 2 次的 N-1 層搬動。再重複一次程序：
1. 將塔的上面 N-2 層搬到 Z 暫放。
2. 把最下層的塔搬到 Y 放定位。
3. 把 Z 暫放的 N-2 層塔搬到 Y，結束。
　　我們可以發現，N 層可以分解成 N-1 層，N-1 層可以分解成 N-2 層，所以我們可以將問題反覆分解，直到只剩 1 層為止：
1. 將塔的上面 0 層搬到 Z 暫放。（等於沒做）
2. 把最下層的塔搬到 Y 放定位。
3. 把 Z 暫放的 0 層塔搬到 Y，結束。（等於沒做）
　　在程式的設計上，將這種程序分成 2 部分。第 1 部分，如果層數只有 1 層，就直接從 X 搬到 Y 就好了：
　if(N = 1) then "Move disk from Peg X to Peg Y";
　　第二部分，如果多於一層（假設有 N 層），就：
1. 搬動 N-1 層到 Z，至於搬動 N-1 層的方式，使用我們設計的程序就行（也就是呼叫自己這個程序）。
　Hanoi(X, Y, Z, N-1);
2. 搬動最下層到 Y。
　"Move disk from Peg X to Peg Y";
3. 將 N-1 層搬到 Y，至於搬動 N-1 層的方式，使用我們設計的程序就行（也就是呼叫自己這個程序）。
　Hanoi(Z, X, Y, N-1);

Answer 2

看起來懂 但是有觀念卻不懂裡面執行的步驟
找半天都沒人用執行步驟建立觀念的
我到現在還是不懂 或許是自學的關係吧

Answer 3

如果你知道 Hanoi 的規則，這程式就不難看懂。
如果已是最小一個環，就搬啦！
如果不是，那就少一個環的問題，（１）
搬好，就搬這個環
搬好，再搬少一個環的問題。（２）
X Y Z
你不可能一次從 X 到 Y 搬好。
所以，（１）是從 X 搬到 Z 暫存，中途用 Y 當暫存塔。
搬好後，暫存塔 Y 是〝空〞的。
這時可以搬最大環到目的的 Y 環去
這時，X塔〝已空〞，可以當暫存塔。
用 X 當暫存塔，把剛搬到 Z 去的 N-1 個環，搬到目地塔 Y 去。
所謂〝空〞，更正確的說法是：沒有要搬的環（比 N 小的環）

2007-02-05 14:21:20 補充：
哪裡不懂可以再問，我可以寫再清楚一點。
祝
看懂！^_^