天天看點

漢諾塔問題 最簡單的圖文講解遞歸實作

問題簡化:

假設有 A,B,C三個柱子。有n個盤子,從大到小依次放在A柱上,我們目标是把A柱的盤子移到C柱。遵循如下原則:

1.小盤的上面不能放大圓盤。

2.在三根柱子之間一回隻能移動一個圓盤。

3.隻能移動在最頂端的圓盤。 

解法介紹

在了解遞歸時,難點就像國小生了解方程一樣,無法了解将未知的設定為x,假設它為已知的方式求解。遞歸也一樣,我們将某個函數通過定義,假設它能實作這個功能,并且在函數内部又肯定會依賴于這個功能,會發生自己調用自己的情況。比如我們這裡的功能機為:

tower(int n, string from, string to, string tmp)
這個功能機能實作将n個盤子,從源柱from,利用臨時柱tmp,最終将盤子移動到目标柱to上。
它既然能将n個盤子搬過去,那一定也能将n-1個盤子搬過去。這就是遞歸的精髓。遞歸的出口就是當隻有一個時,直接搬過去就行。      

思路與源碼:

這三個柱子在變換着充當源柱,目标柱,臨時柱。

void tower(int n, string from, string to, string tmp) {
    if (n == 1) {
        cout << n  << from << " to " << to << endl;   //A
    }
    else {
        tower(n - 1, from, tmp, to);  //B
        cout << n  << from << " to " << to << endl; //C
        tower(n - 1, tmp, to, from); //D
    }
}

int main(int argc, char** argv) {
    tower(7, " A ", " C ", " B ");
}      

繼續閱讀