漢諾塔公式

漢諾塔問(wèn)題在數(shù)學(xué)層面的公式：

不用說(shuō)，你看到這個(gè)公式一定一臉懵逼，我現(xiàn)在來(lái)講解這個(gè)公式的作用。

先來(lái)回想一下大象放冰箱要幾步，三步吧，打開(kāi)冰箱，放進(jìn)去，關(guān)上門(mén)就行了，我們先不要去思考一些細(xì)碎的步驟，將一個(gè)復(fù)雜的問(wèn)題先簡(jiǎn)單化，再慢慢去分析。

那漢諾塔問(wèn)題也是同樣的簡(jiǎn)單三步：（假設(shè)有n個(gè)盤(pán)子）

一、把最大的盤(pán)子留在A柱，然后將其他的盤(pán)子全放在B柱。

二、把最大的盤(pán)子放到C柱。

三、然后將B柱上的所有盤(pán)子放到C柱。

這就是漢諾塔的流程，漢諾塔的精髓就是上面三句話。

n層漢諾塔有（2^n-1）次移動(dòng)，來(lái)將盤(pán)子全部從A盤(pán)到C盤(pán).

C語(yǔ)言遞歸公式

相應(yīng)我們可以寫(xiě)出對(duì)應(yīng)的C語(yǔ)言遞歸公式：（n就是盤(pán)子的個(gè)數(shù)，xyz就是柱子的名字）

相信你肯定有很多疑問(wèn)，我們現(xiàn)在先來(lái)舉幾個(gè)例子再解釋問(wèn)題吧。

?一個(gè)盤(pán)子就不說(shuō)了，因?yàn)樽畲蟮谋P(pán)子就是他，所以他直接就去C盤(pán)了。

兩層漢諾塔

共三步：把最大盤(pán)上面的全部放到B，然后最大盤(pán)去C，再把剩余的盤(pán)全部放到C就行了。

這是兩個(gè)盤(pán)，共移動(dòng)三次就移動(dòng)完了，那三個(gè)盤(pán)呢？

三層漢諾塔

?把全部過(guò)程堪稱一個(gè)整體，最大盤(pán)上面的所有盤(pán)全部看成一個(gè)整體，我們也只用執(zhí)行三個(gè)步驟，我們要利用把大事化小的觀點(diǎn)，不要一上來(lái)就思考具體是怎么移動(dòng)的，這樣看不清問(wèn)題的本質(zhì)。

我們?cè)賮?lái)具體分析三步具體要怎么移動(dòng).

第一步中，我們要移動(dòng)三次，分別是A->C、是A->B、C->B這就是一大次完整的移動(dòng)，在這一步中，我們套用了上一次的漢諾塔公式進(jìn)行使用，這就是漢諾塔的難點(diǎn)，接下來(lái)我給大家看個(gè)圖，希望大家能理解，（n是層數(shù)，X,Y,Z則是函數(shù)參數(shù))

?漢諾塔的內(nèi)部其實(shí)就像一個(gè)金字塔一樣，其實(shí)每一次調(diào)用自己，就是按照上面所說(shuō)精髓的公式調(diào)用自己，讓自己的參數(shù)發(fā)生了變化。我希望大家能夠自己去照著畫(huà)一下流程，

第二步：將A到C，這就是將上圖的第二步那寫(xiě)上第四次移動(dòng)：A->C。

第三步，將B柱上的全部盤(pán)子借助A放到C

第七步完成后就會(huì)發(fā)現(xiàn)沒(méi)有要執(zhí)行的語(yǔ)句了，漢諾塔函數(shù)就結(jié)束返回到main函數(shù)了，自此求解漢諾塔函數(shù)的步驟就完成了。

好的，這樣，我們移動(dòng)三層漢諾塔的過(guò)程的就完成了，三次漢諾塔完成就算是解決了這個(gè)問(wèn)題，因?yàn)榧词贡P(pán)子再多也就是一樣的公式套用而已，明白兩層和三層漢諾塔的運(yùn)行原理就可以了，再多層的塔也是相同的流程。不難發(fā)現(xiàn)，遞歸就是讓數(shù)學(xué)公式在C語(yǔ)言中體現(xiàn)了出來(lái)，讓問(wèn)題變的十分”簡(jiǎn)單“。

剩下就是了程序的主函數(shù)部分了，這個(gè)問(wèn)題的主函數(shù)就很簡(jiǎn)單，主函數(shù)只用傳來(lái)盤(pán)子的數(shù)量和三個(gè)柱子的名字就行了；代碼如下

#include <stdio.h>
void change (char x,char y)     //打印盤(pán)子移動(dòng)軌跡的函數(shù)
{
    printf("%c->%c\n", x, y);
}
void f(n, x, y, z)              //漢諾塔函數(shù)
{
    if (n == 1)
    {
        change(x, z);
    }
    else
    {
        f(n - 1, x, z, y);      //公式一：將A柱最大盤(pán)外的盤(pán)子借助C柱移到B柱
            change(x, z);       //公式二：將A上最大盤(pán)移動(dòng)到C柱
        f(n - 1, y, x, z);      //公式三：將B柱上的盤(pán)借助A全部放到C柱
    }
}
int main()
{
    int m;
    scanf("%d", &m);
    f(m, 'A', 'B', 'C');
}

總結(jié)