# 汉诺塔

（重定向自河內塔

3个圆盘的汉诺塔的移动
4个圆盘的汉诺塔的移动

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

## 算法求解

### 遞迴解

C++ 语言实现:

#include <iostream>
using namespace std;

void Towers(int n,char a,char b,char c){
if(n==1){
cout<<"Move disk "<<n<<" from"<<a<<" to "<<c<<endl;
}
else{
Towers(n-1,a,c,b);
cout<<"Move disk "<<n<<" from"<<a<<" to "<<c<<endl;
Towers(n-1,b,a,c);

}
}
int main(int argc, char *argv[]) {
int n;
cin>>n;
Towers(n,'A','B','C');
cout<< endl;

}


Python 语言实现:

def hanoi(n, a, b, c):
if n == 1:
print(a, '-->', c)
else:
hanoi(n - 1, a, c, b)
hanoi(1    , a, b, c)
hanoi(n - 1, b, a, c)
# 调用
if __name__ == '__main__':
hanoi(5, 'A', 'B', 'C')


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.


hanoi :: Integer -> String -> String -> String -> [(String, String)]
hanoi 0 _ _ _ = []
hanoi 1 from _ to = [(from, to)]
hanoi x from buffer to =
hanoi (x-1) from to buffer ++ hanoi 1 from buffer to ++ hanoi (x-1) buffer from to


#### 任意初始結構（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);
}
}


## 图像解释

• a, b 和 c 表示三个柱子
• 按照从小到大的顺序, 从左到右地列出的盘子的位置.

• 对于任意的全部盘子在一根柱子的情况下, 将所有盘子移动到另一个柱子的最短路径只有一个.
• 对于任意的两个盘子分布情况之间转换的时候, 只有一个或者两个不同的最短路径.
• 对于任意的盘子分布情况, 都有一个或者两个将所有盘子移动到任意一个柱子上的最长不相交路径.
• 对于任意的两个盘子分布情况之间转换的时候, 只有一个或者两个不同的最长不相交路径.
• ${\displaystyle N_{h}}$ 是将有 ${\displaystyle h}$ 个盘子的塔, 将所有盘子从一个柱子移动到另一个柱子的非相交路径的数量(一开始盘子都在一个柱子上). 可以得出：
• ${\displaystyle N_{1}=1}$ N 1 = 2,
• ${\displaystyle N_{h+1}=(N_{h})^{2}+(N_{h})^{3}}$ .

## 多塔汉诺塔问题

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

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

• ${\displaystyle f(n,k)}$ 为在有 ${\displaystyle 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.