漢諾塔公式

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

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

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

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

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

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

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

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

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

C語言遞歸公式

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

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

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

兩層漢諾塔

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

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

三層漢諾塔

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

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

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

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

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

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

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

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

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

#include <stdio.h>
void change (char x,char y)     //打印盤子移動軌跡的函數(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柱最大盤外的盤子借助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');
}

總結(jié)

到此這篇關(guān)于帶你理解C語言中的漢諾塔公式的文章就介紹到這了,更多相關(guān)C語言漢諾塔公式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論