數(shù)據(jù)結構與算法分析論文(遞歸的討論)(編輯修改稿)
2025-07-16 23:12 本頁面
【文章內(nèi)容簡介】 法編寫算法既方便又有效。例如,求一個不帶頭結點的單鏈表head的所有data域(假設為int型)之和的遞歸算法如下： int Sum(LinkList *head) { if (head==NULL) return 0。 else return(headdata+Sum(headnext))。 } ③問題求解的過程是遞歸的。一個典型的例子是在有序數(shù)組中查找一個數(shù)據(jù)元素是否存在的折半查找算法。有序數(shù)組元素為1；3；4。5。17。18。31。33。尋找值為17的數(shù)據(jù)（如上圖）。折半查找無非就是三種情況，其中兩種情況的問題解法如果以算法來表示，都存在算法調(diào)用自身的情況。遞歸算法的特點就是：將問題分解成為形式上更加簡單的子問題來進行求解。遞歸算法不但是一種有效的分析問題方法，也是一種有效的算法設計方法，是解決很多復雜問題的重要方法。遞歸算法的基本思想是：把規(guī)模大的、較難解決的問題變成規(guī)模較小的、易解決的同一問題。規(guī)模較小的問題又變成規(guī)模更小的問題，并且小到一定程度可以直接得出它的解，從而得到原來問題的解。 利用遞歸算法解題，首先要對問題的以下三個方面進行分析： 決定問題規(guī)模的參數(shù)。需要用遞歸算法解決的問題，其規(guī)模通常都是比較大的，在問題中決定規(guī)模大?。ɑ騿栴}復雜程度）的量有哪些？把它們找出來。 問題的邊界條件及邊界值。在什么情況下可以直接得出問題的解？這就是問題的邊界條件及邊界值。 解決問題的通式。把規(guī)模大的、較難解決的問題變成規(guī)模較小、易解決的同一問題，需要通過哪些步驟或等式來實現(xiàn)？這是解決遞歸問題的難點。把這些步驟或等式確定下來。 把以上三個方面分析好之后，就可以在子程序中定義遞歸調(diào)用。三、遞歸算法的一個壞例子漢諾塔(Hanoi tower)問題：傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一
外語相關推薦
鄂ICP備17016276號-1