汉诺塔

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

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

算法求解

递归解

C++ 语言实现:

#include <iostream>
#include <cstdio>
using namespace std;

void hannoi (int n, char from, char buffer, char to)
{
if (n == 0)
return;
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;
}


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);
}
}


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;


图像解释

• 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.