我對漢諾塔的理解，我對漢諾塔理解

我對漢諾塔的理解，我對漢諾塔理解

最近在復習C++相關的算法，而這之中就有漢諾塔，網上也看了很多信息，代碼很簡單，但是感覺原理沒有講透。我就想著我來分享我對漢諾塔的看法。

一、漢諾塔問題

     漢諾塔：漢諾塔（又稱河內塔）問題是源於印度一個古老傳說的益智玩具。大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。   該問題的百度百度百科鏈接：點擊打開鏈接  

二、代碼思路

漢諾塔問題，簡單來說就是有A,B,C三個柱子，然後將A中的盤子移動到C中的盤子，但是每次移動的時候必須保證小盤子在大盤子上面。B 作為一個輔助盤子。

 

首先當只有1個盤子在A上的時候，就移動1次，從A 移動C。

那有兩個盤子在A上的時候，肯定先將小盤子移動到B，然後大盤子由A移動到C。小盤子由 B移動到C。

分析兩個盤子的情況，兩個盤子比1個盤子的情況多了一步，把小盤子移動到B的過程，另外兩步的本質都可以看出由A移動到C。

 

那麼當有N個盤子在A上的時候，我們是怎麼樣來做的？我們的解決辦法是否可以理解成有兩個盤子的狀態。

N個盤子，       A,B,C 三個柱子 

第一步，   將n-1個盤子移動到B，即  f(n-1, A,C,B)      這裡的意思是 N-1的盤子，通過C為中間，移動到B盤

第二步，    將最底下的大盤子， 由 A移動C move(A,C)

第三步，    此時經過前兩步驟，A：0個盤子 ，  B：N-1個盤子， C：1個最大的盤子

那麼接下來，就是將B 移動到 C  ， 即  f(n-1,B,A,C)    這裡的意思是 n-1的盤子，通過A為中間，移動到C盤  

 

 

關於遞歸來講，就兩個，第一個，明白循環結束條件， 第二個，循環體。

那麼循環結束條件就是，n<1，即沒有盤子的情況

 

#include <iostream>

class han{
public:
    int num;
    han(int a):num(a){}
    
    void move(char m, char n){
        static int numb = 0;
        numb++;
        std::cout << "第" << numb << "次" << std::endl;
        std::cout << m << "-> " << n << std::endl;
    }
    void pai(int num, char a, char b, char c){
        if (num < 1){
            return;
        }
        else{
            pai(num - 1, a, c, b);
            move(a,c);
            pai(num-1,b,a,c);
        }
    }
    void solve(){
        char A = 'A';
        char B = 'B';
        char C = 'C';
        pai(this->num, A, B, C);


    }
};



int main(){
    
        int n = 0;
        std::cout << "請輸入你想放的盤子:    ";
        std::cin >> n;
        han han1(n);
        han1.solve();
        std::cout << std::endl;
    
    




    std::cin.get();
    std::cin.get();
    return 0;
}