推理與證明方法ppt課件-資料下載頁
2025-04-30 18:07本頁面
【正文】 的（ Recursion）。遞歸定義的函數(shù)遞歸定義的函數(shù) f：：f的定義域：非負(fù)整數(shù)集 遞歸基礎(chǔ)： f(0) 遞歸步驟： f(n)=g(f(k)),kn,n≥0,Date 28推理與證明方法推理與證明方法自然數(shù)階乘 n!就是采用遞歸方法計算出來的。令 f(n)=n!， 則 f(n)可以表示為：f(0)=1f(n)=nf(n–1) n0Example 1Date 29推理與證明方法推理與證明方法菲波那契數(shù) /FibonacciF(0)=0， F(1)=1F(n)=F(n–1)+F(n–2) n1由上述公式，我們得到：F(2)=1， F(3)=2， F(4)=3，F(xiàn)(5)=5， F(6)=8， ……利用菲波那契數(shù)可以推算出兔子繁衍規(guī)律。 Example 2Date 30推理與證明方法推理與證明方法Example6（ PP.205），f3=2?,f4=3?2,(歸納基礎(chǔ)）fn1?n3,fn?n2(n3)(歸納假設(shè)）fn+1=fn1+fn?n2+?n3=?n3(1+?)=?n3?2=?n1(歸納證明 ）Date 31推理與證明方法推理與證明方法利用 Fibonacci數(shù)列研究 Euclid算法的計算復(fù)雜性。a=r0,b=r1ri=ri+1qi+1+ri+2(0≦ ri+2ri+1,0≦ In2)rn1=rnqnrn≧ 1=f2,rn1≧ 2rn≧ 2f2=f3,假設(shè) ri+1≧ fn+1i， ri+2≧ fniri≧ ri+1+ri+2≧ fn+1i+fni=fn+2i(0≦ in2)因此b=r1≧ fn+1?n1,㏒ 10b(n1)㏒ 10?(n1)/5hence,n5㏒ 10b+1Date 32推理與證明方法推理與證明方法遞歸定義的集合：遞歸定義的集合： 3?S X?SY?S→ X+Y?SS是能夠被 3整除的正整數(shù)集合。Example 4∧ Date 33推理與證明方法推理與證明方法Wellformedformulae 命題公式的定義謂詞公式的定義數(shù)集上的 {+， ， *， /， ?}數(shù)學(xué)表達(dá)式的定義Example 5Date 34推理與證明方法推理與證明方法遞歸算法和迭代算法建立在遞歸函數(shù)上的算法稱為遞歸算法，即要求解一個有參數(shù) n的 函數(shù)可以調(diào)用含有更小參數(shù)的同樣的函數(shù)。任何一個遞歸算法都有一個迭代算法與之對應(yīng)。遞歸算法要保存和計算一系列中間過步驟，而迭代算法只須保存最新結(jié)果，因此其計算量與存貯量都比遞歸算法好，但是從邏輯結(jié)構(gòu)上講，遞歸算法更加緊湊簡潔。Date 35推理與證明方法推理與證明方法小 結(jié)數(shù)學(xué)歸納方法基礎(chǔ)，步驟一般 /強(qiáng)，無限 /有限 遞歸方法基礎(chǔ)，步驟Date 36推理與證明方法推理與證明方法進(jìn)一步的思考以可數(shù)集為對象的應(yīng)用 與算法的關(guān)系 遞歸算法（ recursive)與迭代算法 (iterative)Date 37推理與證明方法推理與證明方法練 習(xí) 4 572(b),(d)、 25Date 3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1