漢諾塔相信很多人小時候都玩過這樣的游戲，這是源于印度的古老傳說，大家可千萬不要小看這個游戲，里面體現(xiàn)了古人的大智慧，在這里我們能學(xué)到最直觀的演示方法，本篇主要是針對漢諾塔的問題進(jìn)行分析和代碼展示。

一、前言

漢諾塔，又稱河內(nèi)塔，是一個益智玩具。大梵天創(chuàng)造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

二、解題思路

思路很簡單：有三根相鄰的柱子，從左到右分別為：托盤A、托盤B、托盤C；

托盤A按照“從下到上、從大到小”疊放著3個不同大小的盤子；

第一步：將盤子1從托盤A移動至托盤C

第二步：將盤子2從托盤A移動至托盤B

第三步：將盤子1從托盤C移動至托盤B

第四步：將盤子3從托盤A移動至托盤C

第五步：將盤子1從托盤B移動至托盤A

第六步：將盤子2從托盤B移動至托盤C

第七步：將盤子1從托盤A移動至托盤C

動圖演示

是不是很簡單？

我們從上面移動的過程中，可以看到，托盤B始終作為一個過渡的存在，并且可以把它想象成中轉(zhuǎn)柱；

那么我們就可以這樣理解：

托盤A：起始柱A；

托盤B：中轉(zhuǎn)柱B；

托盤C：目標(biāo)柱C

三、代碼實現(xiàn)

分析：那么我們怎么用代碼來實現(xiàn)呢？

這是一個非常經(jīng)典的遞歸問題。

假設(shè)有n個盤子，需要把這些盤子從第一根起始柱A移動到第三根目標(biāo)柱C中。

（1）首先需要把n-1個盤子移動到第二根中轉(zhuǎn)柱B上；

（2）再把最后一個也就是最大的那一個盤子移動到第三根目標(biāo)柱C上；

（3）最后再把剩下的n-1個盤子移動到第三根目標(biāo)柱C上。

我們定義f(n)是需要移動的次數(shù)； 

f(1)=1，f(2)=3，f(3)=7

…

f(n)=2f(n?1)+1 

代碼如下：

#include <stdio.h>

void move(int n, char pos1, char pos3)
{
    //打印移動的過程
    // 1代表上面最小的盤子
    // 2代表中間位置的盤子
    // 3代表下面最大的盤子
    printf("盤子%d: 從 %c柱 移動到 %c柱\n", n, pos1, pos3);

}

void Hanoi(int n, char pos1, char pos2, char pos3)
{
    //如果是1個盤子，直接從起始柱A移動到目標(biāo)柱C
    if (n == 1) 
    {
        move(n, pos1, pos3);
    }
    else
    {
        //如果盤子大于1個，需要把n-1個盤子，從起始柱pos1，通過目標(biāo)柱pos3，移動到中轉(zhuǎn)柱pos2
        Hanoi(n-1, pos1, pos3, pos2); 

        //此時pos1上的n-1個盤子全部移動pos2上去了，那么可以直接把pos1上剩下的1個盤子，直接移動到pos3上
        move(n, pos1, pos3);

        //把pos2剩下的n-1個盤子，通過中轉(zhuǎn)位置pos1，移動到目標(biāo)位置pos3
        Hanoi(n-1, pos2, pos1, pos3);
    }
}

int main()
{
    //盤子個數(shù)
    int n = 3;

    //起始柱A
    char pos1 = 'A';

    //中轉(zhuǎn)柱B
    char pos2 = 'B';

    //目標(biāo)柱C
    char pos3 = 'C';

    printf("移動%d個盤子的步驟如下↓\n", n);

    //漢諾塔函數(shù)
    Hanoi(n, pos1, pos2, pos3);

    return 0;
}

如果我們編譯并運行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

移動3個盤子的步驟如下↓
盤子1: 從 A柱 移動到 C柱
盤子2: 從 A柱 移動到 B柱
盤子1: 從 C柱 移動到 B柱
盤子3: 從 A柱 移動到 C柱
盤子1: 從 B柱 移動到 A柱
盤子2: 從 B柱 移動到 C柱
盤子1: 從 A柱 移動到 C柱