歡迎前往個(gè)人博客 駑馬點(diǎn)滴 和視頻空間 嗶哩嗶哩-《挨踢日志》
【問題】
a,b,c是三個(gè)塔座。開始時(shí)，在a上共有n個(gè)圓盤，自上而下颂鸿，圓盤由小到大。編號分別為1,2,...,n. 現(xiàn)在要通過b塔把圓盤從a塔移動(dòng)到c塔.試寫出移動(dòng)過程hanoi(n,a,b,c).
【解答】
建模
我們記錄每一次轉(zhuǎn)移為 x -> y 其中 x~=y攒庵， x, y從{a, b, c}中取值
那么問題就是要給出一些列的轉(zhuǎn)移的有序集合嘴纺，使得按照集合中的步驟，能夠?qū)個(gè)盤從a移動(dòng)到c
這里有3個(gè)塔： a浓冒、b颖医、c，由于a是起始塔裆蒸，而c是目標(biāo)塔，b就是輔助塔糖驴，于是需要引入3個(gè)變量：起始塔僚祷、目標(biāo)塔、輔助塔
同時(shí)還有一個(gè)由圓盤組成的堆的概念贮缕。有一個(gè)變量n用于描述這個(gè)堆的大小辙谜，因?yàn)槲覀儾幌Ｍ騺y堆的從上到下的圓盤是由小到大的布局，所以感昼，n就唯一決定了這個(gè)堆的特性装哆。
顯然，我們接觸到n這個(gè)變量定嗓，自然希望使用數(shù)學(xué)歸納法來解決這樣的問題蜕琴，于是問題，應(yīng)當(dāng)考慮將n的情形轉(zhuǎn)化為n-1的情形宵溅，從而通過遞歸完成我們的解決方案凌简。
首先我們假定解決方案是一個(gè)關(guān)于 n 和 起始塔、輔助塔恃逻、目標(biāo)塔 的函數(shù) hanoi(n, 起始塔, 輔助塔, 目標(biāo)塔)
表示n個(gè)圓盤雏搂，從起始塔藕施，通過輔助塔移動(dòng)到目標(biāo)塔的解決方案。
那么我們需要求解的問題就是：hanoi(n, a, b, c)
而 hanoi(n, a, b, c)的解決方案是一個(gè)步驟方案凸郑，于是我們又可以將這個(gè)過程視為3大步驟：
- 先將a上面的n-1個(gè)盤組成的堆從a裳食，借助輔助塔c，轉(zhuǎn)移到b的解決方案hanoi(n-1, a, c, b)
- 將第n個(gè)盤移動(dòng)到c： hanoi(1, a, b, c)
- 再將b上面的n-1個(gè)盤組成的堆從b芙沥，借助輔助塔a诲祸，轉(zhuǎn)移到c的解決方案hanoi(n-1, b, a, c)
于是遞歸算法如下：
void LankeHelper::hanoi(int n, char a, char b, char c){
if(n==1)
{
cout<<a<<"->"<<c<<"\n";
}
else {
hanoi(n-1,a,c,b);
hanoi(1, a, b, c);
hanoi(n-1,b,a,c);
}
}
int _tmain(int argc, _TCHAR* argv[]){
LankeHelper lh;
lh.hanoi(2,'a','b','c');
system("pause");
return 0;
}
歡迎前往個(gè)人博客 駑馬點(diǎn)滴 和視頻空間 嗶哩嗶哩-《挨踢日志》
