普及層次第三講遞歸遞推分治教學(xué)課件

遞歸、遞推、分治南京第三十九中學(xué)林暉例3.1.1背包問題問題一:給定背包容量W和物體種類N,以及每種物體的重量W;,每種物體只有問是否能將背包裝滿。請統(tǒng)計(jì)箱裝滿的方案數(shù)樣例輸入:54234樣例輸出:2分析對第n個(gè)物體只有兩種情況,即取或者不取。若取原問題就轉(zhuǎn)化為search(wan]n1若不取,則轉(zhuǎn)化為search(w,n-1)若w=0則說明能夠裝滿proceduresearchw,n:integer)beginifw=0thenp:=p+1;ifn>=1thenbeginsearch(w-a[nl,n-1)search(w,n-1)end:end:遞歸轉(zhuǎn)化為非遞歸遞歸是算法設(shè)計(jì)中的一種重要方法它的優(yōu)勢在于能用有限的語句來定義對象的無限集合。對于某些問題,用遞歸處理起來簡單明了,/程序結(jié)構(gòu)清晰精練,但是由于遞歸處理的過程需占用大量的機(jī)時(shí)和空間,因而程序的效率低,在必要的時(shí)候,需要將遞歸轉(zhuǎn)化為非遞歸來處理。非遞歸算法一般要比遞歸算法效率高得多求斐波那契數(shù)列中的第n個(gè)數(shù)用遞歸的方法用非遞歸的方法beginfunctionfib(ninteger)integer;/f[O]:=0beginf1]:=1;ifn=othenfib:=0elseifn=1thenfib=1readIn(n);fib:=fib(n-1)+fib(n-2)form:=1tondoendfm]:=fm-1]+fm-2]writeIn(f[',n,=,fnDend.遞推遞推算法:對于一個(gè)有規(guī)律的數(shù)列,我們可以借助已知的項(xiàng)利用特定的關(guān)系逐項(xiàng)推算出它的后繼項(xiàng)的,…如此反復(fù),直到找到所需的那一項(xiàng)為止,這樣的方法稱為遞推算法。遞推算法的首要問題是得到相鄰的數(shù)據(jù)項(xiàng)間的關(guān)系(即遞推關(guān)系)。解決遞推問題的一般步驟●建立遞推關(guān)系式●確定邊界條件遞推求解例3.2.1NICOMACHUS(尼克馬庫斯)定理[問題描述]COMACHUS定理:任何一個(gè)整數(shù)的立方都可以表示成一串奇數(shù)的和,例如23=3+5=833=7+9+11=27=13+15+17+19=64表示的規(guī)律分析:用Fm)表示n的3次方的數(shù)n為奇數(shù):F3)=(32-2)+32+(32+2)=3*3227n為偶數(shù):F4)■■■■口■■■■■■■■■■■■■■■■■■=4+42=64例322:切煎餅●王小二自夸刀工不錯,有人放—張大的煎餅在砧板上,問他:“餅不許離開砧板,切100刀最多能分成多少塊?”找規(guī)律,如下圖:切一刀切二刀切三刀切四刀令q(n)為切n刀能分成的塊數(shù),從圖中可見:q(1)=1+12q(2)=1+1+2=4(3)=1+1+2+3=7q(4)=1+1+2+