河內塔

說明

河內之塔(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時，則所需次數為：

2⁶⁴- 1 = 18446744073709551615

每天搬一個盤子，需要約505390248594782世紀，就算每秒鐘搬一個盤子，也要約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)

實作：Toy C Java Python Scala Ruby JavaScript Haskell Prolog

def hanoi(n, a, b, c) {
    if n == 1 {
        println('Move sheet from {0} to {1}'.format(a , c))
    } 
    else {
        hanoi(n - 1, a, c, b)
        hanoi(1, a, b, c)
        hanoi(n - 1, b, a, c) 
    }
}

hanoi(3, 'A', 'B', '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']

Prolog

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).