遞推算法分析課件

1、教學(xué)要求了解遞推算法的概念與各類遞推設(shè)計(jì)要領(lǐng)應(yīng)用遞推算法求解實(shí)際問題 第三章 遞 推1. 遞推的概念 遞推是計(jì)算機(jī)數(shù)值計(jì)算中的一個(gè)重要算法。思想是通過數(shù)學(xué)推導(dǎo)，將復(fù)雜的運(yùn)算化解為若干個(gè)重復(fù)的簡(jiǎn)單運(yùn)算，以充分發(fā)揮計(jì)算機(jī)善長重復(fù)處理的特點(diǎn)一、遞推概述 2. 遞推關(guān)系 遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)之間的關(guān)系，即遞推關(guān)系。 遞推關(guān)系是一種高效的數(shù)學(xué)模型，是遞推應(yīng)用的核心。 遞推關(guān)系不僅在各數(shù)學(xué)分支中發(fā)揮著重要的作用，由它所體現(xiàn)出來的遞推思想在各學(xué)科領(lǐng)域中更是顯示出其獨(dú)特的魅力。求解方法 找規(guī)律： a1=1 a2=1 a3=2=1+1=a1+a2 a4=3=1+2=a2+a3 a5=5=2+3=

2、a3+a4 a6=8=3+5=a4+a5 則有： an=an-2+an-1， a1=1,a2=1 有了這個(gè)遞推方程，程序就很簡(jiǎn)單了。例：求斐波那契數(shù)列：1、1、2、3、5、8、的第n項(xiàng)。 3. 遞推的實(shí)施步驟（1）確定遞推變量遞推變量可以是簡(jiǎn)單變量，也可以是一維或多維數(shù)組。 （2）建立遞推關(guān)系遞推關(guān)系是遞推的依據(jù)，是解決遞推問題的關(guān)鍵。（3）確定初始（邊界）條件根據(jù)問題最簡(jiǎn)單情形的數(shù)據(jù)確定遞推變量的初始（邊界）值，這是遞推的基礎(chǔ)。（4）對(duì)遞推過程進(jìn)行控制遞推過程控制：遞推在什么時(shí)候結(jié)束，滿足什么條件結(jié)束。 4. 遞推算法框架描述 （1） 簡(jiǎn)單順推算法 順推即從前往后推，從已求得的規(guī)模為1,2,

3、i-1的一系列解，推出問題規(guī)模為i的解，直至得到規(guī)模為n的解：f(1i-1)=； / 確定初始值 for(k=i;k=n;k+) f(k)=； / 根據(jù)遞推關(guān)系實(shí)施順推 print(f(n)； / 輸出n規(guī)模的解f(n) （2） 簡(jiǎn)單逆推算法 逆推即從后往前推，從已求得的規(guī)模為n,n1,i+1的一系列解，推出問題規(guī)模為i的解，直至得到規(guī)模為1的解：f(ni+1)=； / 確定初始值 for(k=i;k=1;k-) f(k)=； / 實(shí)施逆推 print(f(1)；（3）較復(fù)雜的遞推問題需設(shè)置多重循環(huán)遞推。 例1：求斐波那契數(shù)列：1、1、2、3、5、8、的第n項(xiàng)。問題分析：斐波那契數(shù)列具有下列遞

4、推關(guān)系 an=an-2+an-1， a1=1,a2=1，q且其中n=3算法描述： int fib(int n) int i,f1=1,f2=1,f; for(i=3;i=n;i+) f=f1+f2; f1=f2; f2=f; if(n=1|n=2) return 1; else return f; 二、遞推算法實(shí)例1、輸出斐波那契數(shù)列：1、1、2、3、5、8、的前n項(xiàng)。（ 每行輸出10個(gè)數(shù)）2、求斐波那契數(shù)列：1、1、2、3、5、8、的前n項(xiàng)的和。思考：二、遞推算法實(shí)現(xiàn)實(shí)例例2：求n！。算法描述： int fact(int n) int i,s=1; for(i=1;i=n;i+) s=s*i

5、; return s; 二、遞推算法實(shí)現(xiàn)例3：求n！。算法描述： int fact(int n) int i,s=1; for(i=1;i3）（2） 確定初始條件f(1)=1；即1=1; f(2)=1；即2=1+1; f(3)=2；即3=1+1+1；3=31. 算法分析2. 算法描述 printf(請(qǐng)輸入臺(tái)階總數(shù)n:); scanf(%d,&n); f1=1;f2=1;f3=2; / 賦初值 for(k=4;k=n;k+) fk=fk-1+fk-3; / 實(shí)施遞推 printf(%d,fn); 3.2 水手分椰子 案例提出 五個(gè)水手來到一個(gè)島上，采了一堆椰子。一段時(shí)間后，第一個(gè)水手醒來，悄悄地

6、將椰子等分成五份，多出一個(gè)椰子，便給了旁邊的猴子，然后自己藏起一份，再將剩下的椰子重新合在一起。不久，第二名水手醒來，同樣將椰子等分成五份，恰好也多出一個(gè)，也給了猴子。然后自己也藏起一份，再將剩下的椰子重新合在一起。以后每個(gè)水手都如此分了一次并都藏起一份，也恰好都把多出的一個(gè)給了猴子。第二天，五個(gè)水手醒來，把剩下的椰子分成五份，恰好又多出一個(gè)，給了猴子。 問原來這堆椰子至少有多少個(gè)? 設(shè)置y數(shù)組，第i個(gè)水手藏椰子數(shù)為y(i)(i=1,2,5)個(gè)，第二天5個(gè)水手醒來后各分得椰子為y(6)個(gè)，依題意原來這堆椰子數(shù)為 x=5*y(1)+1 為了求取y(1)，實(shí)施遞推。相鄰兩人所藏椰子數(shù)y(i)與y(

7、i+1)之間的關(guān)系為 4*y(i)=5*y(i+1)+1 (i=1,2,5) （3） 習(xí)慣按時(shí)間順序遞推，從y(i)推出y(i+1)，即 y(i+1)=(4*y(i)-1)/5 (i=1,2,5) （4）1. 算法分析 第二個(gè)問題，遞推何時(shí)結(jié)束？ 問題本身沒有邊界條件限制，只要求上面5個(gè)遞推方程所涉及的6個(gè)量y(i)都是正整數(shù)。也就是說，若有6個(gè)整數(shù)y(i)滿足5個(gè)方程4*y(i)=5*y(i+1)+1，(i=1,2,5)即為一個(gè)解。 首先y(1)賦初值k(取值從1開始遞增)后推出y(2)，由y(2)推出y(3)，依此經(jīng)5次遞推得y(6)。如果某一次推出的不是整數(shù)，則中止繼續(xù)往后推，返回k增1后賦值給y(1)，從頭開始。如果5次遞推都是整數(shù)，則輸出原有椰子數(shù)5*y(1)+1后結(jié)束。 2. 算法描述int i; double k,x,y7;i=1;k=1.0;y1=k;while(i=5) i+;yi=(4*yi-1-1)/5; if(yi!=（int）yi) k=k+1.0;y1=k;i=1; x=5*y1+1;printf(原有椰子至少有：%6.0f個(gè).n,