1、4.1 迭代算法,迭代法（Iteration）也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。迭代算法一般用于數(shù)值計算。迭代法應(yīng)該是我們早已熟悉的算法策略，程序設(shè)計語言課程中所學(xué)的累加、累乘都是迭代算法策略的基礎(chǔ)應(yīng)用。 利用迭代算法策略求解問題，設(shè)計工作主要有三步： 1）確定迭代模型 2）建立迭代關(guān)系式 3）對迭代過程進(jìn)行控制,411 遞推法,【例1】兔子繁殖問題 問題描述：一對兔子從出生后第三個月開始，每月生一對小兔子。小兔子到第三個月又開始生下一代小兔子。假若兔子只生不死，一月份抱來一對剛出生的小兔子，問一年中每個月各有多少只兔子。 問題分析：因一對兔子從出生后第三個月開

2、始每月生一對小兔子，則每月新下小兔子的對兒數(shù)(用斜體數(shù)字表示)顯然由前兩個月的小兔子的對兒數(shù)決定。則繁殖過程如下： 一月 二月 三月 四月 五月 六月 1 1 1+1=2 2+1=3 3+2=5 5+3=8 ,算法1：,main( ) int i,a=1,b=1; print(a,b); for(i=1;i=10;i+) c=a+b; print (c); a=b; b=c； ,數(shù)學(xué)建模：y1=y2=1，yn=yn-1+yn-2，n=3，4，5，。,算法2：,表4-1 遞推迭代表達(dá)式 1 2 3 4 5 6 7 8 9 a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a

3、+c 由此歸納出可以用“c=a+b; a=b+c; b=c+a;”做循環(huán)“不變式”。 算法2如下： main( ) int i,a=1,b=1; print(a,b); for(i=1; i=4;i+) c=a+b; a=b+c; b=c+a; print(a,b,c); ,算法2，最后輸出的并不是12項，而是2+3*4共14項。,表4-2 遞推迭代表達(dá)式 1 2 3 4 5 6 7 8 9 a b a=a+b b=a+b a=a+b b=a+b 由此歸納出可以用“a=a+b; b=a+b;”做循環(huán)“不變式”，從而得到以下算法3: main( ) int i,a=1,b=1; print(a,

4、b); for(i=1; i=5;i+) a=a+b; b=a+b; print(a,b); ,算法3：,【例2】求兩個整數(shù)的最大公約數(shù)。 數(shù)學(xué)建模：輾轉(zhuǎn)相除法是根據(jù)遞推策略設(shè)計的。 不妨設(shè)兩個整數(shù)ab且a除以b商x余c；則a-bx=c，不難看出a、b的最大公約數(shù)也是c的約數(shù)（一個數(shù)能整除等式左邊就一定能整除等式的右邊），則a、b的最大公約數(shù)與b、c的最大公約數(shù)相同。同樣方法推出b、c的最大公約數(shù)與，直到余數(shù)為0時，除數(shù)即為所求的最大公約數(shù)。 算法設(shè)計：循環(huán)“不變式”第一次是求a、b相除的余數(shù)c，第二次還是求“a”“b” 相除的余數(shù)，經(jīng)a=b,b=c操作，就實現(xiàn)了第二次還是求“a”“b” 相除

5、的余數(shù)，這就找到了循環(huán)不變式。循環(huán)在余數(shù)c為0時結(jié)束。,算法如下： main（） int a, b; input(a,b); if(b=0) print(“data error”); return; else c = a mod b; while c0 a=b; b=c; c=a mod b; print(b); ,4.1.2 倒推法,所謂倒推法：是對某些特殊問題所采用的違反通常習(xí)慣的，從 后向前推解問題的方法。如下面的例題，因不同方面的需求而采用了倒推策略。 例1在不知前提條件的情況下，經(jīng)過從后向前遞推，從而求解問題。即由結(jié)果倒過來推解它的前提條件。又如例2由于存儲的要求，而必須從后向前進(jìn)行

6、推算。另外，在對一些問題進(jìn)行分析或建立數(shù)學(xué)模型時，從前向后分析問題感到比較棘手，而采用倒推法（如例3），則問題容易理解和解決。下面分別看這幾個例子：,【例1】猴子吃桃問題 一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個， 到第10天時就只有一個桃子了，求原有多少個桃？ 數(shù)學(xué)模型：每天的桃子數(shù)為：a10=1, a9=(1+a10)*2, a8=(1+a9)*2,a10=1， 遞推公式為：ai=(1+ai+1)*2 I = 9,8,7,61 算法如下 ： main( ) int i,s; s=1; for (i=9 ;i=1;i=i-1) s=(s+1)*2 print (s)； ,【例2】 輸

7、出如圖4-1的楊輝三角形（限定用一個一維數(shù)組完成）。 數(shù)學(xué)模型：上下層規(guī)律較明顯，中間的數(shù)等于上行左上、右上兩數(shù)之和。 問題分析：題目中要求用一個一維數(shù)組即完成。數(shù)組空間一定是由下標(biāo)從小到大利用的，這樣其實楊輝三角形是按下圖4-2形式存儲的。若求n層，則數(shù)組最多存儲n個數(shù)據(jù)。,1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 圖4-1 楊輝三角形,1 1 1 1 2 1 1 3 3 1 14 6 4 1 ,圖4-2 楊輝三角形存儲格式,算法設(shè)計：,A1 = Ai=1 Aj = Aj + Aj-1 j=i-1，i-2，2 i行 i-1行 i-1行,算法如下： main( ) int n

8、,i,j,a100; input(n); print(“1”); print(“換行符”); a1=a2=1; print(a1,a2); print(“換行符”); for (i=3;i1，j=j-1) aj=aj+aj-1; for (j=1;j=i;j=j+1) print(aj); print(“換行符”); ,【例3】穿越沙漠問題 用一輛吉普車穿越1000公里的沙漠。吉普車的總裝油量為500加侖，耗油率為1加侖/公里。由于沙漠中沒有油庫，必須先用這輛車在沙漠中建立臨時油庫。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫，以及各處的貯油量。,問題分析： 1）先看一簡單問題：有一位探

9、險家用5天的時間徒步 橫穿A、B兩村，兩村間是荒無人煙的沙漠，如果一 個人只能擔(dān)負(fù)3天的食物和水，那么這個探險家至 少雇幾個人才能順利通過沙漠。,A城雇用一人與探險家同帶3天食物同行一天，然后被雇 人帶一天食物返回，并留一天食物給探險家，這樣探險 家正好有3天的食物繼續(xù)前行，并于第三天打電話雇B城 人帶3天食物出發(fā)，第四天會面他們會面，探險家得到一 天的食物赴B城。如圖4-3主要表示了被雇用二人的行程。 A B 圖4-3 被雇用二人的行程,2）貯油點問題要求要以最少的耗油量穿越沙漠，即到達(dá)終 點時，沙漠中的各臨時油庫和車的裝油量均為0。這樣只 能從終點開始向前倒著推解貯油點和貯油量。,數(shù)學(xué)模型

10、：根據(jù)耗油量最少目標(biāo)的分析，下面從后向前分段討論。 第一段長度為500公里且第一個加油點貯油為500加侖。 第二段中為了貯備油，吉普車在這段的行程必須有往返。下面討論怎樣走效率高： 1）首先不計方向這段應(yīng)走奇數(shù)次（保證最后向前走）。 2）每次向前行進(jìn)時吉普車是滿載。 3）要能貯存夠下一加油點的貯油量，路上耗油又最少。 ,下圖是滿足以上條件的最佳方案，此段共走3次：第一、二次來回耗油2/3貯油1/3，第三次耗油1/3貯油2/3，所以第二個加油點貯油為1000加侖。由于每公里耗油率為1加侖，則此段長度為500/3公里。 第三段與第二段思路相同。下圖是一最佳方案此段共走5次：第一、二次來回耗油2/5

11、貯油3/5，第三、四次來回耗油2/5貯油3/5，第五次耗油1/5貯油4/5，第三個加油點貯油為1500加侖。此段長度為500/5。 500/5公里 第二 第三 終點貯油點（500）貯油點（1000）貯油點（1500） 圖4-4 貯油點及貯油量示意,綜上分析，從終點開始分別間隔 500，500/3，500/5，500/7，（公里）設(shè)立貯油點，直到總距離超過1000公里。每個貯油點的油量為500，1000，1500，。 算法設(shè)計：由模型知道此問題并不必用倒推算法解決（只是分析過程用的是倒推法），只需通過累加算法就能解決。變量說明：dis表示距終點的距離，1000- dis則表示距起點的距離，k表示

12、貯油點從后到前的序號。,desert（ ） int dis，k，oil,k; dis=500;k=1;oil=500; do print(“storepoint”,k,”distance”,1000-dis,”oilquantity”,oil)； k=k+1; dis=dis+500/(2*k-1); oil= 500*k; while ( dis1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(“storepoint”,k,”distance”,0,”oilquantity”,oil)； ,4.1.3 迭代法解方程,迭代法解方程的實質(zhì)是按照下列步驟

13、構(gòu)造一個序列x0,x1,xn,來逐步逼近方程f(x)=0的解： 1）選取適當(dāng)?shù)某踔祒0； 2）確定迭代格式，即建立迭代關(guān)系，需要將方程f(x)=0改 寫為x=(x)的等價形式； 構(gòu)造序列x0，x1，xn，即先求得x1=(x0)，再求 x2=(x1)，如此反復(fù)迭代，就得到一個數(shù)列x0， x1，xn，若這個數(shù)列收斂，即存在極值，且函數(shù) (x)連續(xù)，則很容易得到這個極限值 x*就是方程f(x)=0的根。,【例1】迭代法求方程組根算法說明：方程組解的初值X=（x0，x1，xn-1）,迭代關(guān)系方程組為：xi=gi(X)(i=0,1,n-1),w為解的精度,則算法如下：for(i=0;iw and kma

14、xn )；for(i=0;in;i+) print(i，“變量的近似根是”，xi)；,【例2】牛頓迭代法 牛頓迭代法又稱為切線法，它比一般的迭代法有更高的收斂速度，如圖4-5所示。首先, 選擇一個接近函數(shù)f(x)零點的x0, 計算相應(yīng)的f(x0)和切線斜率f(x0)（這里f 表示函數(shù)f的導(dǎo)數(shù)）。然后我們計算穿過點(x0,f (x0)且斜率為f (x0)的直線方程為： 和x軸的交點的x坐標(biāo), 也就是求如下方程的解：,將新求得交點的x坐標(biāo)命名為x1。如 圖4-5所示，通常x1會比x0更接近方 程f(x) = 0的解。接下來用x1開始下 一輪迭代 .,圖4-5 牛頓迭代法 示意圖,迭代公式可化簡為：

15、 此公式就是有名的牛頓迭代公式。已經(jīng)證明, 如果f是連 續(xù)的, 并且待求的零點x是孤立的, 那么在零點x周圍存在 一個區(qū)域, 只要初始值x0位于這個鄰近區(qū)域內(nèi), 那么牛頓 法必定收斂。 下面給出用牛頓迭代法，求形如ax3+bx2+cx+d=0方程根的算法，系數(shù)a、b、c、d的值依次為1、2、3、4，由主函數(shù)輸入。求x在1附近的一個實根。求出根后由主函數(shù)輸出。,main( ) float a , b, c, d, fx; print(輸入系數(shù) a,b,c,d:); input(a,b,c,d); fx=f(a,b,c,d); printf(方程的根為：,fx); ,float f(a,b,c,d

16、) float a,b,c,d; float x1=1 , x0, f0 , f1; do x0=x1; f0=(a*x0+b)*x0+c)*x0+d; f1=(3*a*x0+2*b)*x0+c; x1=x0-f0/f1; while(fabs(x1-x0)=1e-4); return(x1); ,令a0,b0=a,b，c0=(a0+b0)/2，若f(c0)=0，則c0為方程f(x)=0的根；否則，若f(a0)與f(c0)異號，即 f(a0)*f(c0)0，則令a1,b1=a0,c0；若f(b0)與f(c0)異號，即 f(b0)*f(c0)0，則令a1,b1=c0,b0。 依此做下去，當(dāng)發(fā)現(xiàn)f(cn)=0時，或區(qū)間an,bn足夠小，比如| an-bn |0.0001時，就認(rèn)為找到了方程的根。 用二分法求一元非線性方程f(x)= x3/2+2x2-8=0（其中表示冪運(yùn)算）在區(qū)間0，2上的近似實根r，精確到0.0001.算法如下：,圖4-6 二分法求解 方程示意,【例3】二分法求解方程f(x)=0根 用二分法求解方程f(x)=0根的前提條件是：f(x)在求解的區(qū)間a,b上是連續(xù)的