# 雙色、三色河內塔

## 解法

• 雙色河內塔 C
``#include <stdio.h>void print(char from, char to) {    printf("盤由 %c 移至 %c\n", from, to);}void hanoi(int n, char a, char b, char c) {    if (n == 1) {        print(a, c);        print(a, c);    } else {        hanoi(n - 1, a, c, b);        hanoi(1, a, b, c);        hanoi(n - 1, b, a, c);    }}void hanoi2colors(int n) {    char a = 'A';    char b = 'B';    char c = 'C';    int i;    for(i = n / 2; i > 1; i--) {        hanoi(i - 1, a, b, c);        print(a, b);        print(a, b);        hanoi(i - 1, c, b, a);        print(b, c);    }    print(a, b);    print(a, c);}int main() {    int n;    printf("盤數：");    scanf("%d", &n);    hanoi2colors(n);        return 0;}  ``

• 雙色河內塔 Java
``import java.util.*;import static java.lang.System.out;public class Hanoi2Colors {    static class Move {        char from, to;        Move(char from, char to) {            this.from = from;            this.to = to;        }    }        private List<Move> moves;        List<Move> solve(int n) {        moves = new ArrayList<Move>();        hanoi2Colors(n);        return moves;    }            public void hanoi(int n, char a, char b, char c) {        if (n == 1) {            moves.add(new Move(a, c));        } else {                    hanoi(n - 1, a, c, b);            hanoi(1, a, b, c);            hanoi(n - 1, b, a, c);        }    }     public void hanoi2Colors(int n) {        char a = 'A';        char b = 'B';        char c = 'C';        for (int i = n / 2; i > 1; i--) {            hanoi(i - 1, a, b, c);            moves.add(new Move(a, b));            moves.add(new Move(a, b));            hanoi(i - 1, c, b, a);            moves.add(new Move(b, c));        }        moves.add(new Move(a, b));        moves.add(new Move(a, c));    }    public static void main(String[] args) {        out.print("盤數：");        Hanoi2Colors hanoi2Colors = new Hanoi2Colors();        int n = new Scanner(System.in).nextInt();        for(Move move : hanoi2Colors.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)        def hanoi2Colors(n):    a, b, c= 'A', 'B', 'C'    l = [hanoi(i - 1, a, b, c) + [(a, b), (a, b)]        + hanoi(i - 1, c, b, a) + [(b, c)] for i in range(n // 2, 1, -1)]    return [item for subList in l for item in subList] + [(a, b), (a, c)]    for move in hanoi2Colors(int(input('盤數：'))):    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)}def hanoi2Colors(n: Int) = {    val (a, b, c) = ('A', 'B', 'C')    val list = for(i <- n / 2 until (1, -1)) yield (hanoi(i - 1, a, b, c)          ++ List((a, b), (a, b)) ++ hanoi(i - 1, c, b, a) ++ List((b, c)))    list.flatten ++ List((a, b), (a, c))}print("盤數：")hanoi2Colors(readInt).foreach(_ match {    case (from, to) => printf("盤由 %c 移到 %c%n", from, to)})``

• 雙色河內塔 Ruby
``#encoding: Big5def step(f, t)    {from: f, to: t}enddef hanoi(n, a, b, c)    if n == 1        [step(a, c)]    else        hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) + hanoi(n - 1, b, a, c)    endend        def hanoi2Colors(n)    a, b, c = "A", "B", "C"    (2..(n / 2)).to_a.reverse.map { |i|        hanoi(i - 1, a, b, c) + [step(a, b), step(a, b)] + hanoi(i - 1, c, b, a)         + [step(b, c)]    }.flatten + [step(a, b), step(a, c)]end    print "盤數："hanoi2Colors(gets.to_i).each do |move|    print "盤子從 #{move[:from]} 移動至 #{move[:to]}\n"end``

• 雙色河內塔 JavaScript
``Array.prototype.reduce = function(init, f) {    var value = init;    for(var i = 0; i < this.length; i++) {        value = f(value, this[i]);    }    return value;};    function step(f, t) {    return {from: f, to: t};}function range(from, to) {    var r = [];    if(to > from) for(var c = 0, i = from; i < to; c++, i++) { r[c] = i; }     else for(var c = 0, i = from; i > to; c++, i--) { r[c] = i; }    return r;}function hanoi(n, a, b, c) {    if(n === 1) {        return [step(a, c)];    } else {        return hanoi(n - 1, a, c, b).concat(                 hanoi(1, a, b, c), hanoi(n - 1, b, a, c));    }}function hanoi2Colors(n) {    var a = 'A'; var b = 'B'; var c = 'C';    return range(n / 2, 1).map(function(i) {        return hanoi(i - 1, a, b, c).concat([step(a, b), step(a, b)],                 hanoi(i - 1, c, b, a), [step(b, c)]);    }).reduce([], function(ac, l) {        return ac.concat(l);    }).concat([step(a, b), step(a, c)]);}hanoi2Colors(6).forEach(function(step) {   print('盤從 ' + step.from + ' 移至 ' + step.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 chanoi2Colors n = [item | subList <- list, item <- subList] ++ [(a, b), (a, c)]    where (a, b, c) = ('A', 'B', 'C')          begin = n `div` 2          list = [hanoi (i - 1) a b c ++ [(a, b), (a, b)] ++ hanoi (i - 1) c b a               ++ [(b, c)] |i <- [begin, (begin - 1) .. 2]]    main = do   putStrLn "Please enter a number: "  n <- getLine  sequence [printf "Move from %c to %c\n" from to                | (from, to) <- hanoi2Colors (read n)]``

------------------------------------------------------------------------------------------------------------------

• 三色河內塔 C
``#include <stdio.h>void print(char from, char to) {    printf("盤由 %c 移至 %c\n", from, to);}void hanoi(int n, char a, char b, char c) {    if(n != 0) {        if (n == 1) {            print(a, c);            print(a, c);            print(a, c);        } else {            hanoi(n - 1, a, c, b);            hanoi(1, a, b, c);            hanoi(n - 1, b, a, c);        }    }}void hanoi3colors(int n) {    char a = 'A';    char b = 'B';    char c = 'C';        if(n == 3) {        print(a, b);        print(a, b);        print(a, c);        print(b, c);        print(b, a);        print(c, b);    }    else {        hanoi(n / 3 - 1, a, b, c);        print(a, b);        print(a, b);        print(a, b);        hanoi(n / 3 - 1, c, b, a);        print(b, c);        print(b, c);        print(b, c);        hanoi(n / 3 - 1, a, c, b);        print(c, a);        print(c, a);        hanoi(n / 3 - 1, b, a, c);        print(a, b);        int i;        for(i = n / 3 - 1; i > 0; i--) {            hanoi(i - 1, c, a, b);            print(c, a);            print(c, a);            hanoi(i - 1, b, a, c);             print(a, b);        }    }}int main() {    int n;    printf("盤數：");    scanf("%d", &n);    hanoi3colors(n);        return 0;} ``

• 三色河內塔 Java
``import java.util.*;import static java.lang.System.out;public class Hanoi3Colors {    static class Move {        char from, to;        Move(char from, char to) {            this.from = from;            this.to = to;        }    }        private List<Move> moves;        List<Move> solve(int n) {        moves = new ArrayList<Move>();        hanoi3Colors(n);        return moves;    }            public void hanoi(int n, char a, char b, char c) {        if(n != 0) {            if (n == 1) {                moves.add(new Move(a, c));                moves.add(new Move(a, c));                moves.add(new Move(a, c));            } else {                         hanoi(n - 1, a, c, b);                hanoi(1, a, b, c);                hanoi(n - 1, b, a, c);            }        }    }     public void hanoi3Colors(int n) {        char a = 'A';        char b = 'B';        char c = 'C';        if(n == 3) {            moves.add(new Move(a, b));            moves.add(new Move(a, b));            moves.add(new Move(a, c));            moves.add(new Move(b, c));            moves.add(new Move(b, a));            moves.add(new Move(c, b));        }        else {            hanoi(n / 3 - 1, a, b, c);            moves.add(new Move(a, b));            moves.add(new Move(a, b));            moves.add(new Move(a, b));                        hanoi(n / 3 - 1, c, b, a);            moves.add(new Move(b, c));            moves.add(new Move(b, c));            moves.add(new Move(b, c));                        hanoi(n / 3 - 1, a, c, b);            moves.add(new Move(c, a));            moves.add(new Move(c, a));                        hanoi(n / 3 - 1, b, a, c);            moves.add(new Move(a, b));            for (int i = n / 3 - 1; i > 0; i--) {                hanoi(i - 1, c, a, b);                moves.add(new Move(c, a));                moves.add(new Move(c, a));                hanoi(i - 1, b, a, c);                moves.add(new Move(a, b));            }        }    }    public static void main(String[] args) {        out.print("盤數：");        Hanoi3Colors hanoi3Colors = new Hanoi3Colors();        int n = new Scanner(System.in).nextInt();        for(Move move : hanoi3Colors.solve(n)) {            out.printf("盤由 %c 移至 %c%n", move.from, move.to);        }    }}``

• 三色河內塔 Python
``def flatten(list):    return [item for sublist in list for item in sublist]def hanoi(n, a, b, c):    if n == 0:        return []    else:        if n == 1:            return [(a, c), (a, c), (a, c)]        else:            return hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) \                   + hanoi(n - 1, b, a, c)        def hanoi3Colors(n):    a, b, c= 'A', 'B', 'C'    if n == 3:        return [(a, b), (a, b), (a, c), (b, c), (b, a), (c, b)]    else:        return hanoi(n / 3 - 1, a, b, c) + [(a, b), (a, b), (a, b)] + \               hanoi(n / 3 - 1, c, b, a) + [(b, c), (b, c), (b, c)] + \               hanoi(n / 3 - 1, a, c, b) + [(c, a), (c, a)] + \               hanoi(n / 3 - 1, b, a, c) + [(a, b)] + \               flatten([hanoi(i - 1, c, a, b) + [(c, a), (c, a)] +                    hanoi(i - 1, b, a, c) + [(a, b)]                      for i in range(n // 3 - 1, 0, -1)])    for move in hanoi3Colors(int(input('盤數：'))):    print("盤由 %c 移至 %c" % move)``

• 三色河內塔 Scala
``def hanoi(n: Int, a: Char, b: Char, c: Char): List[(Char, Char)] = {    if(n == 0) Nil    else {        if(n == 1) List((a, c), (a, c), (a, c))        else hanoi(n - 1, a, c, b) ++              hanoi(1, a, b, c) ++ hanoi(n - 1, b, a, c)    }}def hanoi3Colors(n: Int) = {    val (a, b, c) = ('A', 'B', 'C')    if(n == 3) List((a, b), (a, b), (a, c), (b, c), (b, a), (c, b))    else {        hanoi(n / 3 - 1, a, b, c) ++ List((a, b), (a, b), (a, b)) ++         hanoi(n / 3 - 1, c, b, a) ++ List((b, c), (b, c), (b, c)) ++         hanoi(n / 3 - 1, a, c, b) ++ List((c, a), (c, a)) ++        hanoi(n / 3 - 1, b, a, c) ++ List((a, b)) ++         (for(i <- n / 3 - 1 until (0, -1)) yield (hanoi(i - 1, c, a, b) ++           List((c, a), (c, a)) ++ hanoi(i - 1, b, a, c) ++ List((a, b)))).flatten    }}print("盤數：")hanoi3Colors(readInt).foreach(_ match {    case (from, to) => printf("盤由 %c 移到 %c%n", from, to)})``

• 三色河內塔 Ruby
``#encoding: Big5def step(f, t)    {from: f, to: t}enddef hanoi(n, a, b, c)    if n == 0        []    else        if n == 1            [step(a, c), step(a, c), step(a, c)]        else            hanoi(n - 1, a, c, b) + hanoi(1, a, b, c) + hanoi(n - 1, b, a, c)        end    endend        def hanoi3Colors(n)    a, b, c = "A", "B", "C"    if n == 3        [step(a, b), step(a, b), step(a, c),          step(b, c), step(b, a), step(c, b)]    else        hanoi(n / 3 - 1, a, b, c) + [step(a, b), step(a, b), step(a, b)] +         hanoi(n / 3 - 1, c, b, a) + [step(b, c), step(b, c), step(b, c)] +         hanoi(n / 3 - 1, a, c, b) + [step(c, a), step(c, a)] +        hanoi(n / 3 - 1, b, a, c) + [step(a, b)] +        (1..(n / 3 - 1)).to_a.reverse.map { |i|            hanoi(i - 1, c, a, b) + [step(c, a), step(c, a)] +            hanoi(i - 1, b, a, c) + [step(a, b)]        }.flatten    endend    print "整數："hanoi3Colors(gets.to_i).each do |move|    print "盤子從 #{move[:from]} 移動至 #{move[:to]}\n"end``

• 三色河內塔 JavaScript
``Array.prototype.reduce = function(init, f) {    var value = init;	for(var i = 0; i < this.length; i++) {        value = f(value, this[i]);    }	return value;};    function step(f, t) {    return {from: f, to: t};}function range(from, to) {    var r = [];    if(to > from) for(var c = 0, i = from; i < to; c++, i++) { r[c] = i; }     else for(var c = 0, i = from; i > to; c++, i--) { r[c] = i; }    return r;}function hanoi(n, a, b, c) {    if(n === 0) {        return [];    } else {        if(n === 1) {            return [step(a, c), step(a, c), step(a, c)];        } else {            return hanoi(n - 1, a, c, b).concat(                    hanoi(1, a, b, c), hanoi(n - 1, b, a, c));        }    }}function hanoi3Colors(n) {    var a = 'A'; var b = 'B'; var c = 'C';    if(n === 3) {        return [step(a, b), step(a, b), step(a, c),          step(b, c), step(b, a), step(c, b)];    }    else {        return hanoi(n / 3 - 1, a, b, c).concat(            [step(a, b), step(a, b), step(a, b)],            hanoi(n / 3 - 1, c, b, a),             [step(b, c), step(b, c), step(b, c)],            hanoi(n / 3 - 1, a, c, b),             [step(c, a), step(c, a)],            hanoi(n / 3 - 1, b, a, c),             [step(a, b)],             range(n / 3 - 1, 0).map(function(i) {                return hanoi(i - 1, c, a, b).concat(                        [step(c, a), step(c, a)],                         hanoi(i - 1, b, a, c), [step(a, b)]);            }).reduce([], function(ac, l) {                return ac.concat(l);            })        );    }}hanoi3Colors(6).forEach(function(step) {   print('盤從 ' + step.from + ' 移至 ' + step.to);});``

``import Text.Printfhanoi 0 _ _ _ = []hanoi 1 a _ c = [(a, c), (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 chanoi3Colors n = case n of     3 -> [(a, b), (a, b), (a, c), (b, c), (b, a), (c, b)]    n -> hanoi begin a b c ++ [(a, b), (a, b), (a, b)] ++          hanoi begin c b a ++ [(b, c), (b, c), (b, c)] ++          hanoi begin a c b ++ [(c, a), (c, a)] ++         hanoi begin b a c ++ [(a, b)] ++          [item | subList <- list, item <- subList]    where (a, b, c) = ('A', 'B', 'C')          begin = n `div` 3 - 1          list = [hanoi (i - 1) c a b ++ [(c, a), (c, a)]               ++ hanoi (i - 1) b a c ++               [(a, b)] |i <- [begin, (begin - 1) .. 1]]    main = do   putStrLn "Please enter a number: "  n <- getLine  sequence [printf "Move from %c to %c\n" from to                | (from, to) <- hanoi3Colors (read n)]``