# 河內塔

November 28, 2021

## 程式實作

``````#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) {
} 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);
}
}
}
``````
``````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, 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)
``````
``````# encoding: UTF-8
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
``````
``````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.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).
``````
``````# 我寫的玩具語言 https://github.com/JustinSDK/toy_lang

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

## 延伸思考

### 不遞迴的河內塔

``````def hanoi(n, a, b, c):
param_stack_recursion2 = [[n, a, b, c]]

while param_stack_recursion2:
m, pa, pb, pc = param_stack_recursion2.pop()

param_stack_recursion1 = []
while True:
if m == 1:
print(pa, pc) # hanoi(1, A, B, C)

# hanoi(m - 1, A, C, B) is completed
leng = len(param_stack_recursion2)
while param_stack_recursion1:
m = m + 1
sa, sb, sc = param_stack_recursion1.pop()

# hanoi(m - 1, B, A, C)
param_stack_recursion2.insert(leng, [m - 1, sb, sa, sc])

if param_stack_recursion2:
_, mb, ma, mc = param_stack_recursion2[-1]
print(ma, mc) # move A to C

break

param_stack_recursion1.append([pa, pb, pc])
# hanoi(m - 1, A, C, B)
m = m - 1
pa, pb, pc = pa, pc, pb

hanoi(4, 'A', 'B', 'C')
``````

### 基於格雷碼的河內塔

``````def is_even(n):
return n % 2 == 0

def which_disk(n):
c = n ^ (n + 1)
i = 0
while c != 0:
c = c >> 1
i = i + 1
return i

def hanoi(n):
number_of_moves = 2 ** n - 1
dir = [1, 0] if is_even(n) else [0, 1]
pin = [1] * number_of_moves

for i in range(0, number_of_moves):
disk = which_disk(i)
p_idx, d_idx = disk - 1, disk & 1
next = (pin[p_idx] + dir[d_idx]) % 3 + 1
print(pin[p_idx], next)
pin[p_idx] = next

hanoi(4)
``````