一、漢諾塔

創(chuàng)新互聯(lián)是專業(yè)的南充網(wǎng)站建設(shè)公司，南充接單;提供做網(wǎng)站、網(wǎng)站設(shè)計(jì),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行南充網(wǎng)站開發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

下面是一段關(guān)于漢諾塔游戲的介紹：

/*

漢諾塔：漢諾塔（又稱河內(nèi)塔）問(wèn)題是源于印度一個(gè)古老傳說(shuō)的益智玩具。大梵天創(chuàng)造世界的時(shí)候做了三根柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

*/

簡(jiǎn)單來(lái)說(shuō)，它的規(guī)則就是：每個(gè)盤之上不能托比當(dāng)前盤大小還要大的盤。 在滿足這個(gè)規(guī)則的前提下，要將一端(A端)的所有盤移動(dòng)到另一端（C）

二、游戲思路

假設(shè)有1個(gè)盤：則經(jīng)過(guò)的步驟為： A -> C 1步即可

而假設(shè)有2個(gè)盤，則需要： A -> B , A -> C, B -> C ,總共3步

假設(shè)有3個(gè)盤，則步驟為： 

A -> C, A -> B, C -> B,  A -> C, B -> A, B -> C, A -> C

一共7步。

似乎能總結(jié)出層數(shù)和最少的如下規(guī)律： 

事實(shí)上，的確如此。

三、編程思路

現(xiàn)在如果要求實(shí)現(xiàn)一個(gè)函數(shù)，根據(jù)輸入的層數(shù)n，求出將當(dāng)前漢諾塔從A移動(dòng)到C的最少步數(shù)，則甚至不需要用程序進(jìn)行推算，直接用上面的公式  ： 2|^ n - 1 即可。

但如果在上述要求的前提下，還要求出具體的做法，或者說(shuō)要求每一步的具體步驟，則需要讓程序自己進(jìn)行推算，具體過(guò)程如下：

當(dāng)層數(shù)為1層的時(shí)候，可以直接讓當(dāng)前盤從A移動(dòng)到C，

當(dāng)層數(shù)為2層的時(shí)候，將塔尖移動(dòng)到B，將底座移動(dòng)到C，然后將塔尖從B移動(dòng)到C即可，

而對(duì)于大于2層的情況，也可以套用當(dāng)前的思路：

可以將最上面的一層看作“塔尖”，將剩下的部分看作“底座”

我們要做的仍然是將“塔尖”移動(dòng)到B，將“底座”移動(dòng)到C，再將B處的塔尖移動(dòng)到C。

代碼如下：

void HanoiStep(int n, char A, char B, char C)
{
        static int step = 1;
    if(n == 1)
    {
        //A to C
    }
    else
    {
        PseduCode(n - 1, A, C, B); //將A處的“塔尖”移動(dòng)到B
        std::cout << "step" << step++ <<":" << "move " << A << " to " << C << endl;////將A處的“底座”移動(dòng)到C
        PseduCode(n - 1, B, A, C);  //將B處的“底座”移動(dòng)到C
    }
}