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