# 汉诺塔

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

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

## 解法

### 遞歸解

C++ 语言实现:

/*
* Project     : hannoi
* 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 A, char B, char C)
{
if (n == 1)
{
cout << "Move disk " << n << " from " << A << " to " << C << endl;

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

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

// end
// iCoding@CodeLab
//


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;


## 多塔汉诺塔问题

• 在有3个柱子时，所需步数的公式较简单，但对于4个以上柱子的汉诺塔尚未得到通用公式，但有一递归公式（未得到证明，但目前为止没有找到反例）：
• $f(n,k)$为在有k个柱子时，移动n个圆盘到另一柱子上需要的步数，则：

## 流行文化

2011年電影《猿人爭霸戰：猩凶革命》曾出現河內塔以測試猩猩智商