# 河內塔

3個圓盤的河內塔的移動
4個圓盤的河內塔的移動

1. 每次只能移動一個圓盤；
2. 大盤不能疊在小盤上面。

## 解法

### 遞歸解

C++ 語言實現:

/*
* Project     : hanoi
* File        : main.cpp
* Author      : iCoding
*
* Date & Time : Sat Oct 06 21:01:55 2012
*
*/
using namespace std;
#include <iostream>
#include <cstdio>

void hannoi (int n, char from, char buffer, char to)
{
if (n == 1)
{
cout << "Move disk " << n << " from " << from << " to " << to << endl;

}
else
{
hannoi (n-1, from, to, buffer);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hannoi (n-1, buffer, from, to);
}
}

int main()
{
int n;
cin >> n;
hannoi (n, 'A', 'B', 'C');
return 0;
}

// end
// iCoding@CodeLab
//


Python 語言實現:

def hanoi(n, a='A', b='B', c='C'):
if n == 1:
print('move', a, '-->', c)
return
hanoi(n-1, a, c, b)
print('move', a, '-->', c)
hanoi(n-1, b, a, c)

print(hanoi(5))


Erlang 語言求解：

-module(hanoi).
-export([hanoi/1]).
hanoi(N) when N>0 ->
do_hanoi({N, 1, 3}).

do_hanoi({0, _, _}) ->
done;
do_hanoi({1, From, To}) ->
io:format("From ~p, To ~p~n", [From, To]);
do_hanoi({N, From, To}) ->
do_hanoi({N-1, From, by(From, To)}),
do_hanoi({1, From, To}),
do_hanoi({N-1, by(From, To), To}).

by(From, To) ->
[Result|_] = [1, 2, 3] -- [From, To],
Result.


#### 任意初始結構（arbitrary initial configuration）的解法

 ; Let conf be a list of the positions of the disks in order of increasing size.
; Let the pegs be identified by the numbers 0, 1 and 2.
(define (hanoi conf t)
(let ((c (list->vector conf)))
(define (move h f t)
(vector-set! c h t)
(printf "move disk ~s from peg ~s to peg ~s~n" h f t))
(define (third-peg f t) (- 3 f t))
(define (hanoi h t)
(if (> h 0)
(let ((h (sub1 h)))
(let ((f (vector-ref c h)))
(if (not (= f t))
(let ((r (third-peg f t)))
(hanoi h r)
(move h f t)))
(hanoi h t)))))
(hanoi (vector-length c) t)))


int conf[HEIGHT]; /* Element conf[d] gives the current position of disk d. */

void move(int d, int t) {
/* move disk d to peg t */
conf[d] = t;
}

void hanoi(int h, int t) {
if (h > 0) {
int f = conf[h-1];
if (f != t) {
int r = 3 - f - t ;
hanoi(h-1, r);
move(h-1, t);
}
hanoi(h-1, t);
}
}


procedure Hanoi(n: integer; from, to, by: char);
Begin
if (n=1) then
writeln('Move the plate ',n,' from ', from, ' to ', to)
else begin
Hanoi(n-1, from, by, to);
Writeln('Move the plate ',n,' from ', from, ' to ', to);
Hanoi(n-1, by, to, from);
end;
End;


### 非遞歸解

SAS Institute Inc. 員工 Yinliang Wu 在研究河內塔結果數據時發現了一種基於如下隱藏模式的新求解方法：

• 對於 1 個盤子的情況，移動步驟總是從源柱子到目標柱子，即 a-> c;
• 基於此初始狀態，對於 n 個盤子的求解可以由如下模式產生：
• 對 n-1 個盤子的移動步驟，交換目標柱子和中間柱子，即 定義 T1 =交換(b,c);
• 插入從源柱到目標柱子的移動步驟：a->c;
• 對 n-1 個盤子的移動步驟，交換來源柱子和中間柱子，即 定義 T2=交換(b,a);

• seq(1)={from->to}={a->c}
• seq(2)={ T1(seq(1)), {from->to}, T2(seq(1))}. 因為 T1=swap(middle, to) 和 T2=swap(middle, from), 則　T1({a->c})= {a->b}, T2({a->c})={b->c}, 最終的步驟為 seq(2)={a->b, a->c, b->c}
• seq(3)=T1(seq(2)), {from->to}, T2(seq(2))} = {a->c, a->b, c->b} + {a->c} + { b->a, b->c, a->c} ={a->c, a->b, c->b, a->c, b->a, b->c, a->c}

## 多塔河內塔問題

• 在有3個柱子時，所需步數的公式較簡單，但對於4個柱子以上時，情形複雜許多。Frame及Stewart在1941年時分別提出了基本上相同的一套演算法[1]，Bousch則在2014年證明了Frame-Stewart演算法在4個柱子時就是最佳解[2]，但此演算法在5個柱子以上是否是最佳解仍是未知。

Frame-Stewart演算法本質上也是遞歸的，可簡單敘述如下：

• ${\displaystyle f(n,k)}$為在有k個柱子時，移動n個圓盤到另一柱子上需要的步數，則：

## 流行文化

2011年電影《猩球崛起》曾出現河內塔以測試猩猩智商。其後續電影《猩球崛起2》中也有類似的場景。

## 參考來源

1. ^ Stewart, B.M.; Frame, J.S. Solution to advanced problem 3819. American Mathematical Monthly. March 1941, 48 (3): 216–9. JSTOR 2304268. doi:10.2307/2304268.
2. ^ Bousch, T. La quatrieme tour de Hanoi. Bull. Belg. Math. Soc. Simon Stevin. 2014, 21: 895–912.