數(shù)據(jù)結(jié)構(gòu)與算法分析lecture4(棧)-資料下載頁(yè)
2025-10-10 19:46本頁(yè)面
【正文】 n n n 返回 1 β 2 3 β 1 4 β Currptr Currptr Currptr n n 2021825 Lecture notes 22 遞歸算法 1 (n=0,1) n! = n(n1)！ ( n1 ) 2021825 Lecture notes 23 ? 例：用棧實(shí)現(xiàn)遞歸 Long fact(int n,Stackintamp。 S) { //pute n! //to fit n! in a long variable,require n=12 Assert((n=0) amp。amp。 (n=12),”Input out of range”)。 while(n1) (n)。//load up the stack long result=1。//holds final result int val。//holds current value while((val)) result = result*val。//pute return result。 } 2021825 Lecture notes 24 以求 4的階乘為例： fac(4)=4*fac(3) fac(3)=3*fac( 2) fac(2)=2*fac( 1) fac(1)=1 fac(4)=4*3*2*1 fac(2)=2*1 fac(3)=3*2*1 下 推 回 代 2021825 Lecture notes 25 利用棧實(shí)現(xiàn)遞歸調(diào)用 主程序 (1)輸出 f(4)。 …… 4 f (4)。 top (2) s=4*f(3) n (1 ) 4 3 f (3)。 （ 2） n=3 （ 1） n=4 top (3) s=3*f(2) n 2 f (2)。 （ 3） n=2 （ 2） n=3 （ 1） n=4 top (4)s=2*f(1) n 1 （ 4） n=1 （ 3） n=2 （ 2） n=3 （ 1） n=4 top s s=3*2*1。(2) 3 (1) 4 1 (3) 2 (2) 3 (1) 4 （ 1） n=4 s=4*3*2*1 返回 (3) 2 (2) 3 (1) 4 (4) 1 結(jié)束 輸出 2
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1