“漢諾塔“問題的遞歸實(shí)現(xiàn)

一、漢諾塔

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

/*

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

*/

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

二、游戲思路

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

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

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

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

一共7步。

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

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

三、編程思路

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

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

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

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

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

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

我們要做的仍然是將“塔尖”移動到B，將“底座”移動到C，再將B處的塔尖移動到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處的“塔尖”移動到B
        std::cout << "step" << step++ <<":" << "move " << A << " to " << C << endl;////將A處的“底座”移動到C
        PseduCode(n - 1, B, A, C);  //將B處的“底座”移動到C
    }
}