漢諾塔公式

漢諾塔問題在數學層面的公式：

不用說，你看到這個公式一定一臉懵逼，我現在來講解這個公式的作用。

先來回想一下大象放冰箱要幾步，三步吧，打開冰箱，放進去，關上門就行了，我們先不要去思考一些細碎的步驟，將一個復雜的問題先簡單化，再慢慢去分析。

那漢諾塔問題也是同樣的簡單三步：（假設有n個盤子）

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

二、把最大的盤子放到C柱。

三、然后將B柱上的所有盤子放到C柱。

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

n層漢諾塔有（2^n-1）次移動，來將盤子全部從A盤到C盤.

C語言遞歸公式

相應我們可以寫出對應的C語言遞歸公式：（n就是盤子的個數，xyz就是柱子的名字）

相信你肯定有很多疑問，我們現在先來舉幾個例子再解釋問題吧。

?一個盤子就不說了，因為最大的盤子就是他，所以他直接就去C盤了。

兩層漢諾塔

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

這是兩個盤，共移動三次就移動完了，那三個盤呢？

三層漢諾塔

?把全部過程堪稱一個整體，最大盤上面的所有盤全部看成一個整體，我們也只用執行三個步驟，我們要利用把大事化小的觀點，不要一上來就思考具體是怎么移動的，這樣看不清問題的本質。

我們再來具體分析三步具體要怎么移動.

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

?漢諾塔的內部其實就像一個金字塔一樣，其實每一次調用自己，就是按照上面所說精髓的公式調用自己，讓自己的參數發生了變化。我希望大家能夠自己去照著畫一下流程，

第二步：將A到C，這就是將上圖的第二步那寫上第四次移動：A->C。

第三步，將B柱上的全部盤子借助A放到C

第七步完成后就會發現沒有要執行的語句了，漢諾塔函數就結束返回到main函數了，自此求解漢諾塔函數的步驟就完成了。

好的，這樣，我們移動三層漢諾塔的過程的就完成了，三次漢諾塔完成就算是解決了這個問題，因為即使盤子再多也就是一樣的公式套用而已，明白兩層和三層漢諾塔的運行原理就可以了，再多層的塔也是相同的流程。不難發現，遞歸就是讓數學公式在C語言中體現了出來，讓問題變的十分”簡單“。

剩下就是了程序的主函數部分了，這個問題的主函數就很簡單，主函數只用傳來盤子的數量和三個柱子的名字就行了；代碼如下

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

總結