我的數據結構學習從漢諾塔開始，這個簡單的算法我可是整整想了一晚上，現在終于有點明白了，上機單步了幾遍，有所了解，，還是寫點什么以供以后參考，也希望能對正在學算法的盆友有所裨益······

?????? 總得來說漢諾塔就是層疊遞歸調用的典型例子，一直是利用A—>B? A-->C? B-->C這樣的單個步驟。

?????? 具體來說，當盤數大于一時，不違背原則下（過程中總是大在下小的在上），A先借助B再放到C上。總是把盤數看成兩個來解決問題。

?????? 比如說，當盤數為二時，顧名思義，這個很簡單只要三下即可完成。這個時候，可以這樣想，如果是三個，就相當于二個完成，還有一個待完成，（注意要有把問題簡化為兩個盤的思想,這樣是遞歸思想的思想實現），那么把完成的看成一個，剩下待完成的看成一個（帶完成的還可以把最近要完成的看成一個，剩下的先別管），這樣問題就回到了二個盤數時的第一步完成狀態，接下來就是遞歸的精華了（我是膜拜數學的強大，一個式子可以表達萬種情感），然后C上的（二個看成一個那）在借助B放到A上，這樣第三個就可以從B放到C上，接下來又是二個了（這個是真正的二個），看基本步驟完成。當盤數是N時，也是利用這種思想，一步一步簡化，遞歸完成。

?????? 接下來談一下N個盤要幾次完成問題

??????? 書上說是2^n-1次，經過計算驗證是正確的。當然我有我的思考計算，哈哈····思考如下：

??????? 當完成n個時設用M(n)次，那么，如上我說的算法當完成n個（也就是n+1個時了）還有一個，這時需要把在C上的看成一個，借助B移動到A上（這時最后一個已到B上），當然要做M（n）次搬動了，完成后，B上的最后一個（（n+1）個）搬動到C上。這時，問題又回到了n次開始，當然需要M(n)次了。這么一來就是M（n）*2次，加上最后一個的兩次，總共是M(n)*2+2=M(n+1)次，好了現在是純數學問題了，可以利用數學知識算出來最后結果，（我還沒算，哈哈，我數學不好呀），步驟沒錯的話，應該結果是M（n）=2^n-1.

??????? 以上只是個人體會，寫的有些弱智，有什么不正確的還請高人指教。

???????? 下面是程序具體實現，（上面為C下面C++）僅供參考······

??????????????????????????????????????????????????? ???

?

[cpp]? view plain copy print ?

#include<stdio.h>????????????????????

int??a=0;??

void?hanoi(int?n,?char?A,?char?B,?char?C)??

?{??

???

?a++;??

?if(n==1)??

?{??

??printf("Move?sheet?%d?from?%c?to?%c\n",n,A,C);??

????}??

?else??

?{??

??hanoi(n-1,A,C,B);??

??printf("Move?sheet?%d?from?%c?to?%c\n",n,A,C);??

??hanoi(n-1,B,A,C);??

?}??

?printf("a是：%d\n",a);??

}??

int?main()??

{??

?int?n;??

?printf("請輸入盤數：");??

?scanf("%d",&n);??

?hanoi(n,"A","B","C");??

?return?0;??

}??

???

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~??

??

#include<iostream>??

using?namespace?std;??

void?move(int?n,?char?s,?char?d)??

{??

????cout<<n<<","<<s<<"->"<<d<<endl;??

}??

void?hanoi(int?n,?char?A='A',?char?B='B',char?C='C')??

?{???if(1==n)??

??????????move(n,A,C);??

??else??

??{??

??????hanoi(n-1,A,C,B);?move(n,A,C);?hanoi(n-1,B,A,C);??

??}??

}??

int?main()??

{??

?int?i=0;??

?cout<<"請輸入盤數：";??

?cin>>i;??

????hanoi(i);??

?return?0;??

}??

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~??

[cpp]? view plain copy print ?

總結

以上是生活随笔為你收集整理的汉诺塔--（数据结构）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。