數(shù)據(jù)結構與算法分析論文(遞歸的討論)-資料下載頁
2025-06-19 23:12本頁面
【正文】 ,c)。else{ Hanoi(n1,a,c,b)。//把n1個圓盤從fromPeg借助toPeg移到auxPeg printf(\t將第%d個盤片從%c移動到%c\n,n,a,c)。 Hanoi(n1,b,a,c)。//把n1個圓盤從auxPeg借助fromPeg移到toPeg}}主程序如下：include void main(){ int n。//漢諾塔盤子數(shù)目 printf(\n 請輸入漢諾塔盤子數(shù)目:\n)。scanf(%d,amp。n)。getchar()。 printf( %d個盤片移動過程:\n,n)。Hanoi(n,39。A39。,39。B39。,39。C39。)。 getchar()。 return。}程序運行截圖如上當盤子數(shù)字比較小時運行時間較短，可以接受。但是當盤子數(shù)字≥20時，程序運行時間長到無法忍受。究其原因，我們用時間復雜度來分析。在算法分析中，當一個算法中包含遞歸調(diào)用時，其時間復雜度的分析會轉(zhuǎn)化為一個遞歸方程求解。實際上，這個問題是數(shù)學上求解漸近階的問題。經(jīng)過計算，上面程序的時間復雜度為O(2 exp n)?？梢?，當盤子數(shù)上升時，運算消耗的時間呈指數(shù)態(tài)上升。所以當盤子數(shù)多的時候，計算機需要消耗很久才能算出結果，而這個時間往往讓人不可忍受。用遞歸算法實現(xiàn)的漢諾塔程序效率分析總結如下：優(yōu)點：①遞歸過程結構清晰 ②程序易讀 ③正確性容易證明缺點：①時間效率低 ②空間開銷大，問題規(guī)模擴大時，噩夢來臨。 ③算法不容易優(yōu)化 所以，對于頻繁使用的算法，或不具備遞歸功能的程序設計語言，需要把遞歸算法轉(zhuǎn)換為非遞歸算法。而采用迭代算法、尾遞歸的消除、利用棧消除任何遞歸就是3個常用的遞歸算法的非遞歸化處理方法。至于這三個方法這里就不贅述了，需要了解的可以查閱相關書籍資料。參考文獻1.《數(shù)據(jù)結構與算法分析——C語言描述》Mark Allen Weiss著2.《C語言設計語言》
外語相關推薦
鄂ICP備17016276號-1