# 河內塔

## 解法

264- 1 = 18446744073709551615

## 演算法

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

``````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;} ``

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

``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)})``

``# encoding: Big5def 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)    endendprint "請輸入整數："hanoi(gets.to_i, "A", "B", "C").each do |move|    print "盤子從 #{move[:from]} 移動至 #{move[:to]}\n"end``

``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);});``

``import Text.Printfhanoi 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 cmain = 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).``````