問題簡化:
假設有 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 ");
}