數(shù)據(jù)結構與算法分析論文(遞歸的討論)(文件)
【正文】 表head的所有data域(假設為int型)之和的遞歸算法如下： int Sum(LinkList *head) { if (head==NULL) return 0。有序數(shù)組元素為1；3；4。31。遞歸算法的特點就是：將問題分解成為形式上更加簡單的子問題來進行求解。 利用遞歸算法解題，首先要對問題的以下三個方面進行分析： 決定問題規(guī)模的參數(shù)。 解決問題的通式。三、遞歸算法的一個壞例子漢諾塔(Hanoi tower)問題：傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。如果僧侶移動金盤一次需要1秒鐘，移動這么多次共需約5845億年。因此，我們太陽系的整個壽命無疑要短于二百億年?；舅枷耄? 1個盤子的漢諾塔問題可直接移動。移動方法示意圖如下這樣，漢諾塔問題的遞歸算法可設計如下：void Hanoi(int n,char a,char b,char c){if(n==1)//遞歸出口printf(\t將第%d個盤片從%c移動到%c\n,n,a,c)。//把n1個圓盤從auxPeg借助fromPeg移到toPeg}}主程序如下：include n)。A39。C39。}程序運行截圖如上當盤子數(shù)字比較小時運行時間較短，可以接受。實際上，這個問題是數(shù)學上求解漸近階的問題。用遞歸算法實現(xiàn)的漢諾塔程序效率分析總結如下：優(yōu)點：①遞歸過程結構清晰 ②程序易讀 ③正確性容易證明缺點：①時間效率低 ②空間開銷大，問題規(guī)模擴大時，噩夢來臨。參考文獻1.《數(shù)據(jù)結構與算法分析——C語言描述》Mark Allen Weiss著2.《C語言設計語言》。而采用迭代算法、尾遞歸的消除、利用棧消除任何遞歸就是3個常用的遞歸算法的非遞歸化處理方法。可見，當盤子數(shù)上升時，運算消耗的時間呈指數(shù)態(tài)上升。究其原因，我們用時
外語相關推薦
鄂ICP備17016276號-1