1算法(25h)(編輯修改稿)
2024-08-20 06:47 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的關(guān)系 。 ? 歸納是一種抽象 即從特殊現(xiàn)象中找出一般關(guān)系。但由于在歸納的過(guò)程中不可能對(duì)所有的情況進(jìn)行列舉，因此，最后由歸納得到的結(jié)論還只是一種猜測(cè)，還需要對(duì)這種猜測(cè)加以必要的證明 。 ? 基本思想 從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。其中初始條件或是問(wèn)題本身已經(jīng)給定，或是通過(guò)對(duì) 問(wèn)題的分析與化簡(jiǎn)而得到確定 。 ? 例題 ? ??? 10 20,2,1,0,5 ?ndxx xInn遞推法例題分析 發(fā)現(xiàn)相鄰兩個(gè)積分之間存在以下關(guān)系 : nII nn151 ?? ?151??? nn InI 只要知道 In1 就可以算出 In ，也就是說(shuō)，只要知道了 I0，就可以通過(guò)這個(gè)遞推公式計(jì)算出所有的積分值 In（ n=1， 2， … ， 20）。 這個(gè)關(guān)系就可以得到如下遞推公式 遞推法例題分析 ? ?????? 100 1 8 2 3 2 )5/6l n (5ln6ln51 dxxI?????????? 20,2,1,511 8 2 3 2 10?nInIInn? 相鄰兩個(gè)積分之間除了具有遞推關(guān)系式 : nII nn151 ?? ?10 ??? nn II以外，還滿(mǎn)足下列不等式 因而， I20 應(yīng)比 I0小。且所有的積分值都不可能為負(fù)。 這樣行嗎？ 遞推法 例題分析 改進(jìn) 方法 根據(jù)遞推關(guān)系式可以 改進(jìn) 成另一個(gè)遞推公式： nn InI 51511 ????????????? 1,29,30,51511130?nInIInn遞推關(guān)系如下： 遞推法總結(jié) : 例題分析 改進(jìn)前后 ? 在老遞推算法中，初值是近似的，即 實(shí)際上存在一個(gè)誤差；老遞推算法遞推過(guò)程中，當(dāng)計(jì)算到 I20時(shí)，其誤差是初值誤差的 520倍。 ? 在新遞推算法中，雖然初值 I30是近似的，而且誤差可能很大。但在用新遞推算法遞推過(guò)程中，每遞推計(jì)算一次， 后一個(gè)計(jì)算值的誤差是前一個(gè)計(jì)算值誤差的 1/5，因此，當(dāng)計(jì)算到 I20時(shí)，其誤差是初值 I30誤差的 1/510 。 基本思想 （ 1）為了降低問(wèn)題的復(fù)雜程度，總是將問(wèn)題 逐層 分解 ，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。 （ 2）這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上 并沒(méi)有 對(duì)問(wèn)題進(jìn)行求解 ，而只是當(dāng)解決了最后那些 最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的 逆過(guò)程 逐步進(jìn)行綜合 ，這就是 遞歸的基本思想。 （ 3）因此，遞歸的基礎(chǔ)也是歸納。 遞歸法舉例說(shuō)明 例： 編寫(xiě)一個(gè)過(guò)程，對(duì)于輸入的參數(shù) n，依次打印輸 出自然數(shù) 1到 n。 非遞歸算法 。 PROCEDURE WRT(n) FOR k=1 TO n DO OUTPUT k RETURN 遞歸算法 。 PROCEDURE WRT1（ n） IF（ n≠0） THEN {WRT1（ n1） OUTPUT n } RETURN 總結(jié)： ? 遞歸是構(gòu)造計(jì)算機(jī)算法的一種基本方法 。 如果一個(gè)過(guò)程直接或間接地調(diào)用它自身 ， 則稱(chēng)該過(guò)程是遞歸的 ， 遞歸過(guò)程必須有一個(gè)遞歸終止條件 ，即存在 “ 遞歸出口 ” 。 無(wú)條件的遞歸是毫無(wú)意義的 。 ? 遞歸分為直接遞歸與間接遞歸兩種。如果一個(gè)算法 P顯式地調(diào)用自己則稱(chēng)為直接遞歸，例如算法 。如果算法 P調(diào)用另一個(gè)算法 Q，而算法 Q又調(diào)用算法 P，則稱(chēng)為間接遞歸調(diào)用。 ? 遞歸過(guò)程能將一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)較簡(jiǎn)單的問(wèn)題，然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)題再歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程可以一直做下去，直到最簡(jiǎn)單的問(wèn)題
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1