Go to Article

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.

## 外部連結

This article uses material from the Wikipedia article "汉诺塔", which is released under the Creative Commons Attribution-Share-Alike License 3.0. There is a list of all authors in Wikipedia

### Game & Play & Gamification

3d,model,playground,board games,computer,strategy,thinktank