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