河內塔


 說明

河內之塔(Towers of Hanoi)是法國人M.Claus(Lucas)於1883年從泰國帶至法國的,河內為越戰時北越的首都,即現在的胡志明市;1883年法國數學家 Edouard Lucas曾提及這個故事,據說創世紀時Benares有一座波羅教塔,是由三支鑽石棒(Pag)所支撐,開始時神在第一根棒上放置64個由上至下依 由小 至大排列的金盤(Disc),並命令僧侶將所有的金盤從第一根石棒移至第三根石棒,且搬運過程中遵守大盤子在小盤子之下的原則,若每日僅搬一個盤子, 則當 盤子全數搬運完畢之時,此塔將毀損,而也就是世界末日來臨之時。

解法

如果柱子標為ABC,要由A搬至C,在只有一個盤子時,就將它直接搬至C,當有兩個盤子,就將B當作輔助柱。
河內塔
 
河內塔
 
河內塔


如果盤數超過2個,將第三個以下的盤子遮起來,就很簡單了,每次處理兩個盤子,也就是:A->B、A ->C、B->C這三個步驟,而被遮住的部份,其實就是進入程式的遞迴處理。
河內塔


事實上,若有n個盤子,則移動完畢所需之次數為2^n - 1,所以當盤數為64時,則所需次數為:

264- 1 = 18446744073709551615

為5.05390248594782e+16年,也就是約5000世紀,如果對這數字沒什麼概念,就假設每秒鐘搬一個盤子好了,也要約 5850億年左右。  

演算法

Procedure HANOI(n, A, B, C) 
IF(n == 1)
PRINT("Move sheet " n " from " A " to " C)
ELSE
HANOI(n-1, A, C, B)
HANOI(1, A, B, C)
HANOI(n-1, B, A, C)

實作:C    Java    Python    Scala    Ruby    JavaScript    Haskell    Prolog

  • C
#include <stdio.h>

void hanoi(int n, char A, char B, char C) {
if(n == 1) {
printf("Move sheet from %c to %c\n", A, C);
}
else {
hanoi(n-1, A, C, B);
hanoi(1, A, B, C);
hanoi(n-1, B, A, C);
}
}

int main() {
int n;
printf("請輸入盤數:");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}

  • Java
import java.util.*;
import static java.lang.System.out;

public class Hanoi {
static class Move {
char from, to;
Move(char from, char to) {
this.from = from;
this.to = to;
}
}

List<Move> solve(int n) {
moves = new ArrayList<Move>();
move(n, 'A', 'B', 'C');
return moves;
}

private List<Move> moves;

private void move(int n, char a, char b, char c) {
if(n == 1) {
moves.add(new Move(a, c));
} else {
move(n - 1, a, c, b);
move(1, a, b, c);
move(n - 1, b, a, c);
}
}

public static void main(String args[]) {
out.print("請輸入盤數:");
Hanoi hanoi = new Hanoi();
int n = new Scanner(System.in).nextInt();
for(Move move : hanoi.solve(n)) {
out.printf("盤由 %c 移至 %c%n", move.from, move.to);
}
}
}

  • Python
def hanoi(n, A, B, C):
if n == 1:
return [(A, C)]
else:
return hanoi(n-1, A, C, B) + hanoi(1, A, B, C) + hanoi(n-1, B, A, C)

n = input("請輸入整數:")
for move in hanoi(int(n), 'A', 'B', 'C'):
print("盤由 %c 移至 %c" % move)

  • Scala
def hanoi(n: Int, a: Char, b: Char, c: Char) : List[(Char, Char)] = {
if (n == 1) List((a, c))
else hanoi(n - 1, a, c, b) ++ hanoi(1, a, b, c) ++ hanoi(n - 1, b, a, c)
}

print("請輸入整數:")
hanoi(readInt, 'A', 'B', 'C').foreach(_ match {
case (from, to) => printf("盤由 %c 移到 %c%n", from, to)
})

  • Ruby
# encoding: Big5
def hanoi(n, a, b, c)
if n == 1
[{from: a, to: c}]
else
hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) + hanoi(n - 1, b, a, c)
end
end

print "請輸入整數:"
hanoi(gets.to_i, "A", "B", "C").each do |move|
print "盤子從 #{move[:from]} 移動至 #{move[:to]}\n"
end

  • JavaScript
function hanoi(n , a, b, c) {
if(n === 1) {
return [{from : a, to : c }]
}
return hanoi(n - 1, a, c, b).concat(
hanoi(1, a, b, c),
hanoi(n - 1, b, a, c)
);
}

hanoi(3, 'A', 'B', 'C').forEach(function(move) {
print('盤從 ' + move.from + ' 移至 ' + move.to);
});

  • Haskell
import Text.Printf

hanoi 1 a _ c = [(a, c)]
hanoi n a b c = hanoi (n - 1) a c b ++ hanoi 1 a b c ++ hanoi (n - 1) b a c

main = do
putStrLn "Please enter a number: "
n <- getLine
sequence [printf "Move from %c to %c\n" from to
| (from, to) <- hanoi (read n) 'A' 'B' 'C']


hanoi(1, A, _, C, [[A, C]]).
hanoi(N, A, B, C, Result) :- NP is N - 1,
                             hanoi(NP, A, C, B, R1),
                             hanoi(1, A, B, C, R2),
                             hanoi(NP, B, A, C, R3),
                             append([R1, R2, R3], Result).

show([]) :- nl.
show([H|R]) :- writef("Move from %n to %n\n", H), show(R).
                 
main([Arg0|_]) :-
        atom_number(Arg0, N),
        hanoi(N, a, b, c, Result),
        show(Result).