第6講 迭代法及蠻力法

1、Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms第四章第四章 基本的算法策略基本的算法策略4.1 4.1 迭代算法迭代算法4.2 4.2 蠻力算法蠻力算法4.3 4.3 分而治之算法分而治之算法4.4 4.4 貪婪算法貪婪算法4.5 4.5 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 4.6 4.6 算法策略間的比較算法策略間的比較Design and Analysis of Computer Algorithms4.1 迭代算法迭代算法4.1.1 4.1.1 遞推法遞推法4.1.2 4.1.2 倒推

2、法倒推法4.1.3 4.1.3 迭代法解方程迭代法解方程大連海事大學(xué)Design and Analysis of Computer Algorithms411 遞推遞推法 【例例1】兔子繁殖問題兔子繁殖問題問題描述：一對(duì)兔子從出生后第三個(gè)月開始，每月生一對(duì)小兔問題描述：一對(duì)兔子從出生后第三個(gè)月開始，每月生一對(duì)小兔子。小兔子到第三個(gè)月又開始生下一代小兔子。假若兔子子。小兔子到第三個(gè)月又開始生下一代小兔子。假若兔子只生不死，一月份抱來一對(duì)剛出生的小兔子，問一年中每只生不死，一月份抱來一對(duì)剛出生的小兔子，問一年中每個(gè)月各有多少只兔子。個(gè)月各有多少只兔子。問題分析：因一對(duì)兔子從出生后第三個(gè)月開始每月生

3、一對(duì)小兔問題分析：因一對(duì)兔子從出生后第三個(gè)月開始每月生一對(duì)小兔子，則每月新下小兔子的對(duì)兒數(shù)子，則每月新下小兔子的對(duì)兒數(shù)(用斜體數(shù)字表示用斜體數(shù)字表示)顯然由顯然由前兩個(gè)月的小兔子的對(duì)兒數(shù)決定。則繁殖過程如下：前兩個(gè)月的小兔子的對(duì)兒數(shù)決定。則繁殖過程如下：大連海事大學(xué)一月一月二月二月三月三月四月四月五月五月六月六月111+1=22+1=33+2=55+3=8Design and Analysis of Computer Algorithms算法算法1 1： main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); f

4、or(i=1;i for(i=1;i=10;i+)=10;i+) c=a+b; c=a+b; print (c); print (c); a=b; a=b; b=c b=c； 大連海事大學(xué)數(shù)學(xué)建模：數(shù)學(xué)建模：y y1 1=y=y2 2=1=1，y yn n=y=yn-1n-1+y+yn-2n-2，n=3n=3，4 4，5 5，。Design and Analysis of Computer Algorithms算法算法2 2： 表表4-1 4-1 遞推迭代表達(dá)式遞推迭代表達(dá)式1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9a b c=a+b a=b+c b=a+c c=a+

5、b a=b+c b=a+c a b c=a+b a=b+c b=a+c c=a+b a=b+c b=a+c 由此歸納出可以用由此歸納出可以用“c=a+b; a=b+c; b=c+a;c=a+b; a=b+c; b=c+a;”做循環(huán)做循環(huán)“不變不變式式”。算法算法2 2如下：如下： main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); for(i=1; i for(i=1; i=4;i+)=4;i+) c=a+b; a=b+c; b=c+a; print(a,b,c); c=a+b; a=b+c; b=c+a;

6、print(a,b,c); 大連海事大學(xué)算法算法2 2，最后輸出的，最后輸出的并不是并不是1212項(xiàng)，而是項(xiàng)，而是2+32+3* *4 4共共1414項(xiàng)。項(xiàng)。 Design and Analysis of Computer Algorithms 表表4-2 4-2 遞推迭代表達(dá)式遞推迭代表達(dá)式1 21 2 3 4 5 6 7 8 93 4 5 6 7 8 9a b a=a+b b=a+b a=a+b b=a+b a b a=a+b b=a+b a=a+b b=a+b 由此歸納出可以用由此歸納出可以用“a=a+b; b=a+b;”a=a+b; b=a+b;”做循環(huán)做循環(huán)“不變式不變式”，從而得到

7、以下算法從而得到以下算法3:3:main( )main( ) int i,a=1,b=1; int i,a=1,b=1; print(a,b); print(a,b); for(i=1; i for(i=1; i=5;i+)=5;i+) a=a+b; b=a+b; print(a,b); a=a+b; b=a+b; print(a,b); 大連海事大學(xué)Design and Analysis of Computer Algorithms【例例2 2】求兩個(gè)整數(shù)的最大公約數(shù)。求兩個(gè)整數(shù)的最大公約數(shù)。數(shù)學(xué)建模：輾轉(zhuǎn)相除法是根據(jù)遞推策略設(shè)計(jì)的。數(shù)學(xué)建模：輾轉(zhuǎn)相除法是根據(jù)遞推策略設(shè)計(jì)的。不妨設(shè)兩個(gè)整數(shù)不

8、妨設(shè)兩個(gè)整數(shù)abab且且a a除以除以b b商商x x余余c c；則；則a-bx=ca-bx=c，不難看出，不難看出a a、b b的最大公約數(shù)也是的最大公約數(shù)也是c c的約數(shù)（一個(gè)數(shù)能整除等式左邊就一定能整除的約數(shù)（一個(gè)數(shù)能整除等式左邊就一定能整除等式的右邊），則等式的右邊），則a a、b b的最大公約數(shù)與的最大公約數(shù)與b b、c c的最大公約數(shù)相同。的最大公約數(shù)相同。同樣方法推出同樣方法推出b b、c c的最大公約數(shù)與的最大公約數(shù)與，直到余數(shù)為，直到余數(shù)為0 0時(shí)，除數(shù)即時(shí)，除數(shù)即為所求的最大公約數(shù)。為所求的最大公約數(shù)。算法設(shè)計(jì)：循環(huán)算法設(shè)計(jì)：循環(huán)“不變式不變式”第一次是求第一次是求a a、

9、b b相除的余數(shù)相除的余數(shù)c c，第二，第二次還是求次還是求“a a”“b b” 相除的余數(shù)，經(jīng)相除的余數(shù)，經(jīng)a=b,b=ca=b,b=c操作，就實(shí)現(xiàn)了第二次操作，就實(shí)現(xiàn)了第二次還是求還是求“a a”“b b” 相除的余數(shù)，這就找到了循環(huán)不變式。循環(huán)在余相除的余數(shù)，這就找到了循環(huán)不變式。循環(huán)在余數(shù)數(shù)c c為為0 0時(shí)結(jié)束。時(shí)結(jié)束。 大連海事大學(xué)Design and Analysis of Computer Algorithms大連海事大學(xué)算法如下：算法如下：mainmain（）（） int a, b; int a, b; input(a,b); input(a,b); if(b=0) if(b

10、=0) print(“data error”); return; else else c = a mod b; c = a mod b; while c0 while c0 a=b; a=b; b=c; b=c; c=a mod b; c=a mod b; print(b); print(b); Design and Analysis of Computer Algorithms4.1.2 4.1.2 倒推法倒推法 大連海事大學(xué) 所謂倒推法：是對(duì)某些特殊問題所采用的違反通常習(xí)慣的，從所謂倒推法：是對(duì)某些特殊問題所采用的違反通常習(xí)慣的，從 后向前推解問題的方法。如下面的例題，因不同方面的需求而采

11、后向前推解問題的方法。如下面的例題，因不同方面的需求而采用了倒推策略。用了倒推策略。例例1在不知前提條件的情況下，經(jīng)過從后向前遞推，從而求解問在不知前提條件的情況下，經(jīng)過從后向前遞推，從而求解問題。即由結(jié)果倒過來推解它的前提條件。又如例題。即由結(jié)果倒過來推解它的前提條件。又如例2由于存儲(chǔ)的要由于存儲(chǔ)的要求，而必須從后向前進(jìn)行推算。另外，在對(duì)一些問題進(jìn)行分析或求，而必須從后向前進(jìn)行推算。另外，在對(duì)一些問題進(jìn)行分析或建立數(shù)學(xué)模型時(shí)，從前向后分析問題感到比較棘手，而采用倒推建立數(shù)學(xué)模型時(shí)，從前向后分析問題感到比較棘手，而采用倒推法（如例法（如例3），則問題容易理解和解決。下面分別看這幾個(gè)例子：），則

12、問題容易理解和解決。下面分別看這幾個(gè)例子：Design and Analysis of Computer Algorithms大連海事大學(xué)【例例1 1】猴子吃桃問題猴子吃桃問題一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個(gè)，一只小猴子摘了若干桃子，每天吃現(xiàn)有桃的一半多一個(gè)，到第到第1010天時(shí)就只有一個(gè)桃子了，求原有多少個(gè)桃？天時(shí)就只有一個(gè)桃子了，求原有多少個(gè)桃？數(shù) 學(xué) 模 型 ： 每 天 的 桃 子 數(shù) 為 ：數(shù) 學(xué) 模 型 ： 每 天 的 桃 子 數(shù) 為 ： a a1 01 0= 1 , a= 1 , a9 9= ( 1 + a= ( 1 + a1 01 0) ) * * 2 , 2 ,

13、 a a8 8=(1+a=(1+a9 9) )* *2,2,a a1010=1=1， 遞推公式為：遞推公式為：a ai i=(1+a=(1+ai+1i+1) )* *2 I = 9,8,7,62 I = 9,8,7,61 1算法如下算法如下 ： main( )main( ) int i,s; int i,s; s=1; s=1; for (i=9 ;i=1;i=i-1) for (i=9 ;i=1;i=i-1) s=(s+1) s=(s+1)* *2 2 print (s) print (s)； Design and Analysis of Computer Algorithms【例例2 2】

14、 輸出如圖輸出如圖4-14-1的楊輝三角形（限定的楊輝三角形（限定用一個(gè)一維數(shù)組完成）。用一個(gè)一維數(shù)組完成）。數(shù)學(xué)模型：上下層規(guī)律較明顯，中間的數(shù)等數(shù)學(xué)模型：上下層規(guī)律較明顯，中間的數(shù)等于上行左上、右上兩數(shù)之和。于上行左上、右上兩數(shù)之和。問題分析：題目中要求用一個(gè)一維數(shù)組即完問題分析：題目中要求用一個(gè)一維數(shù)組即完成。數(shù)組空間一定是由下標(biāo)從小到大利用成。數(shù)組空間一定是由下標(biāo)從小到大利用的，這樣其實(shí)楊輝三角形是按下圖的，這樣其實(shí)楊輝三角形是按下圖4-24-2形形式存儲(chǔ)的。若求式存儲(chǔ)的。若求n n層，則數(shù)組最多存儲(chǔ)層，則數(shù)組最多存儲(chǔ)n n個(gè)個(gè)數(shù)據(jù)。數(shù)據(jù)。大連海事大學(xué)1 11 11 11 2 11 2

15、 11 3 3 11 3 3 11 14 6 4 14 6 4 1圖圖4-2楊輝三角形存儲(chǔ)格式楊輝三角形存儲(chǔ)格式 算法設(shè)計(jì)：算法設(shè)計(jì)： A1 = Ai=1A1 = Ai=1Aj = Aj + Aj-1 j=i-1Aj = Aj + Aj-1 j=i-1，i-2i-2，2 2i i行行 i-1i-1行行 i-1i-1行行Design and Analysis of Computer Algorithms算法如下：算法如下：main( ) int n,i,j,a100;input(n); print(“1”); print(“換行符換行符”);a1=a2=1;print(a1,a2); print

16、(“換行符換行符”);for (i=3;i1，j=j-1) aj=aj+aj-1; for (j=1;j=i;j=j+1) print(aj); print(“換行符換行符”); 大連海事大學(xué)Design and Analysis of Computer Algorithms【例例3 3】穿越沙漠問題穿越沙漠問題 用一輛吉普車穿越用一輛吉普車穿越10001000公里的沙漠。吉普車的總裝油量為公里的沙漠。吉普車的總裝油量為500500加侖，耗油率為加侖，耗油率為1 1加侖加侖/ /公里。由于沙漠中沒有油庫(kù)，公里。由于沙漠中沒有油庫(kù)，必須先用這輛車在沙漠中建立臨時(shí)油庫(kù)。該吉普車以最少必須先用這輛車

17、在沙漠中建立臨時(shí)油庫(kù)。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫(kù)，以及各處的貯的耗油量穿越沙漠，應(yīng)在什么地方建油庫(kù)，以及各處的貯油量。油量。 大連海事大學(xué)問題分析：?jiǎn)栴}分析： 1 1）先看一簡(jiǎn)單問題：有一位探險(xiǎn)家用）先看一簡(jiǎn)單問題：有一位探險(xiǎn)家用5 5天的時(shí)間徒步天的時(shí)間徒步 橫穿橫穿A A、B B兩村，兩村間是荒無人煙的沙漠，如果一兩村，兩村間是荒無人煙的沙漠，如果一 個(gè)人只能擔(dān)負(fù)個(gè)人只能擔(dān)負(fù)3 3天的食物和水，那么這個(gè)探險(xiǎn)家至天的食物和水，那么這個(gè)探險(xiǎn)家至 少雇幾個(gè)人才能順利通過沙漠。少雇幾個(gè)人才能順利通過沙漠。 Design and Analysis of Computer Al

18、gorithms A A城雇用一人與探險(xiǎn)家同帶城雇用一人與探險(xiǎn)家同帶3 3天食物同行一天，然后被雇天食物同行一天，然后被雇 人帶一天食物返回，并留一天食物給探險(xiǎn)家，這樣探險(xiǎn)人帶一天食物返回，并留一天食物給探險(xiǎn)家，這樣探險(xiǎn) 家正好有家正好有3 3天的食物繼續(xù)前行，并于第三天打電話雇天的食物繼續(xù)前行，并于第三天打電話雇B B城城 人帶人帶3 3天食物出發(fā)，第四天會(huì)面他們會(huì)面，探險(xiǎn)家得到一天食物出發(fā)，第四天會(huì)面他們會(huì)面，探險(xiǎn)家得到一 天的食物赴天的食物赴B B城。如圖城。如圖4-34-3主要表示了被雇用二人的行程。主要表示了被雇用二人的行程。 A BA B 圖圖4-3 4-3 被雇用二人的行程被雇用

19、二人的行程 大連海事大學(xué)2 2）貯油點(diǎn)問題要求要以最少的耗油量穿越沙漠，即到達(dá)終）貯油點(diǎn)問題要求要以最少的耗油量穿越沙漠，即到達(dá)終 點(diǎn)時(shí)，沙漠中的各臨時(shí)油庫(kù)和車的裝油量均為點(diǎn)時(shí)，沙漠中的各臨時(shí)油庫(kù)和車的裝油量均為0 0。這樣只。這樣只 能從終點(diǎn)開始向前倒著推解貯油點(diǎn)和貯油量。能從終點(diǎn)開始向前倒著推解貯油點(diǎn)和貯油量。Design and Analysis of Computer Algorithms數(shù)學(xué)模型：根據(jù)耗油量最少目標(biāo)的分析，下面從后向前分段數(shù)學(xué)模型：根據(jù)耗油量最少目標(biāo)的分析，下面從后向前分段討論。討論。第一段長(zhǎng)度為第一段長(zhǎng)度為500500公里且第一個(gè)加油點(diǎn)貯油為公里且第一個(gè)加油點(diǎn)貯油為

20、500500加侖。加侖。第二段中為了貯備油，吉普車在這段的行程必須有往返。下第二段中為了貯備油，吉普車在這段的行程必須有往返。下面討論怎樣走效率高：面討論怎樣走效率高：1 1）首先不計(jì)方向這段應(yīng)走奇數(shù)次（保證最后向前走）。）首先不計(jì)方向這段應(yīng)走奇數(shù)次（保證最后向前走）。2 2）每次向前行進(jìn)時(shí)吉普車是滿載。）每次向前行進(jìn)時(shí)吉普車是滿載。3 3）要能貯存夠下一加油點(diǎn)的貯油量，路上耗油又最少。）要能貯存夠下一加油點(diǎn)的貯油量，路上耗油又最少。大連海事大學(xué)Design and Analysis of Computer Algorithms下圖是滿足以上條件的最佳方案，此段共走下圖是滿足以上條件的最佳方案

21、，此段共走3 3次：第一、二次：第一、二次來回耗油次來回耗油2/32/3貯油貯油1/31/3，第三次耗油，第三次耗油1/31/3貯油貯油2/32/3，所以第，所以第二個(gè)加油點(diǎn)貯油為二個(gè)加油點(diǎn)貯油為10001000加侖。由于每公里耗油率為加侖。由于每公里耗油率為1 1加侖，加侖，則此段長(zhǎng)度為則此段長(zhǎng)度為500/3500/3公里。公里。第三段與第二段思路相同。下圖是一最佳方案此段共走第三段與第二段思路相同。下圖是一最佳方案此段共走5 5次：次：第一、二次來回耗油第一、二次來回耗油2/52/5貯油貯油3/53/5，第三、四次來回耗油，第三、四次來回耗油2/52/5貯油貯油3/53/5，第五次耗油，第

22、五次耗油1/51/5貯油貯油4/54/5，第三個(gè)加油點(diǎn)貯油，第三個(gè)加油點(diǎn)貯油為為15001500加侖。此段長(zhǎng)度為加侖。此段長(zhǎng)度為500/5500/5。 500/5500/5公里公里 第二第二 第三第三 終點(diǎn)終點(diǎn)貯油點(diǎn)（貯油點(diǎn)（500500）貯油點(diǎn)（貯油點(diǎn)（10001000）貯油點(diǎn)（貯油點(diǎn)（15001500）圖圖4-4 4-4 貯油點(diǎn)及貯油量示意貯油點(diǎn)及貯油量示意大連海事大學(xué)Design and Analysis of Computer Algorithms綜上分析，從終點(diǎn)開始分別間隔綜上分析，從終點(diǎn)開始分別間隔 500500，500/3500/3，500/5500/5，500/7500/7，（

23、公里）設(shè)立貯油點(diǎn)，直到總距離超過（公里）設(shè)立貯油點(diǎn)，直到總距離超過10001000公里。每個(gè)貯油點(diǎn)的油量為公里。每個(gè)貯油點(diǎn)的油量為500500，10001000，15001500，。 算法設(shè)計(jì)：由模型知道此問題并不必用倒推算法解決（只算法設(shè)計(jì)：由模型知道此問題并不必用倒推算法解決（只是分析過程用的是倒推法），只需通過累加算法就能解決。是分析過程用的是倒推法），只需通過累加算法就能解決。變量說明：變量說明：disdis表示距終點(diǎn)的距離，表示距終點(diǎn)的距離，1000- dis1000- dis則表示距起則表示距起點(diǎn)的距離，點(diǎn)的距離，k k表示貯油點(diǎn)從后到前的序號(hào)。表示貯油點(diǎn)從后到前的序號(hào)。大連海事大

24、學(xué)Design and Analysis of Computer Algorithmsdesertdesert（ ） int dis int dis，k k，oil,k;oil,k; dis=500;k=1;oil=500; dis=500;k=1;oil=500; do do print(print(“storepointstorepoint”,k,k,”distancedistance”,1000-dis,1000-dis,”oilquantityoilquantity”,oil),oil)； k=k+1;k=k+1; dis=dis+500/(2 dis=dis+500/(2* *k-1

25、);k-1); oil= 500 oil= 500* *k;k; while ( dis1000) while ( dis1000) oil=500*(k-1)+(1000-dis)*( 2*k-1); print(print(“storepointstorepoint”,k,k,”distancedistance”,0,0,”oilquantityoilquantity”,oil),oil)； 大連海事大學(xué)Design and Analysis of Computer Algorithms4.1.3 4.1.3 迭代法解方程迭代法解方程迭 代 法 解 方 程 的 實(shí) 質(zhì)迭 代 法 解 方 程

26、 的 實(shí) 質(zhì) 是 按 照 下 列 步 驟 構(gòu) 造 一 個(gè) 序 列是 按 照 下 列 步 驟 構(gòu) 造 一 個(gè) 序 列x x0 0,x,x1 1, ,x,xn n, ,來逐步逼近方程來逐步逼近方程f(x)=0f(x)=0的解：的解： 1 1）選取適當(dāng)?shù)某踔颠x取適當(dāng)?shù)某踔祒 x0 0； 2 2）確定迭代格式，即建立迭代關(guān)系，需要將方程確定迭代格式，即建立迭代關(guān)系，需要將方程f(x)=0f(x)=0改寫為改寫為x=(x)x=(x)的等價(jià)形式；的等價(jià)形式； 構(gòu)造序列構(gòu)造序列x0，x1，xn，即先求得，即先求得x1=(x0)，再求再求 x2=(x1)，如此反復(fù)迭代，就得到一個(gè)數(shù)列如此反復(fù)迭代，就得到一個(gè)數(shù)

27、列x0，x1，xn，若這個(gè)數(shù)列收斂，即存在極值，且函數(shù)，若這個(gè)數(shù)列收斂，即存在極值，且函數(shù)(x)連續(xù)，則很容易得到這個(gè)極限值連續(xù)，則很容易得到這個(gè)極限值 x*就是方程就是方程f(x)=0的根。的根。 大連海事大學(xué)Design and Analysis of Computer Algorithms【例例1 1】迭代法求方程組根迭代法求方程組根算法說明：算法說明：方程組解的初值方程組解的初值X=X=（x0 x0，x1x1，xn-1xn-1）, ,迭代關(guān)迭代關(guān)系方程組為：系方程組為：xi=gi(X)(i=0,1,n-1),wxi=gi(X)(i=0,1,n-1),w為解的精度為解的精度, ,則則算法

28、算法如下：如下： forfor(i=0;in;i+)(i=0;in;i+)xi=xi=初始近似根初始近似根; ;do k=k+1;do k=k+1; for for(i=0;in;i (i=0;in;i yi=xi;yi=xi; forfor(i=0;in;i+) (i=0;in;i+) xi=gi(X);xi=gi(X); forfor(i=0;in;i+) c=c+fabs(yi-xi)(i=0;iw and kw and kmaxn )；forfor(i=0;in;i+)(i=0;in;i+) print(iprint(i，“變量的近似根是變量的近似根是”，xi)xi)； 大連海事大學(xué)D

29、esign and Analysis of Computer Algorithms【例例2 2】牛頓迭代法牛頓迭代法 牛頓迭代法又稱為切線法，它比一般的迭代法有更高的收斂速度，牛頓迭代法又稱為切線法，它比一般的迭代法有更高的收斂速度，如圖如圖4-54-5所示。首先所示。首先, , 選擇一個(gè)接近函數(shù)選擇一個(gè)接近函數(shù)f(x)f(x)零點(diǎn)的零點(diǎn)的x0, x0, 計(jì)算相應(yīng)計(jì)算相應(yīng)的的f(x0)f(x0)和切線斜率和切線斜率f f(x0)(x0)（這里（這里f f表示函數(shù)表示函數(shù)f f的導(dǎo)數(shù)）。然后我的導(dǎo)數(shù)）。然后我們計(jì)算穿過點(diǎn)們計(jì)算穿過點(diǎn)(x0,f(x0)(x0,f(x0)且斜率為且斜率為f f(x0

30、)(x0)的直線方程為：的直線方程為：和和x x軸的交點(diǎn)的軸的交點(diǎn)的x x坐標(biāo)坐標(biāo), , 也就是求如下方程的解：也就是求如下方程的解：大連海事大學(xué))()(000 xxxfxfy0000)()(xxxfxf圖圖4-5 4-5 牛頓迭代法牛頓迭代法示意圖示意圖Design and Analysis of Computer Algorithms迭代公式可化簡(jiǎn)為：迭代公式可化簡(jiǎn)為：此公式就是有名的牛頓迭代公式此公式就是有名的牛頓迭代公式。已經(jīng)證明。已經(jīng)證明, , 如果如果f f是連是連續(xù)的續(xù)的, , 并且待求的零點(diǎn)并且待求的零點(diǎn)x x是孤立的是孤立的, , 那么在零點(diǎn)那么在零點(diǎn)x x周圍存在周圍存在一

31、個(gè)區(qū)域一個(gè)區(qū)域, , 只要初始值只要初始值x0 x0位于這個(gè)鄰近區(qū)域內(nèi)位于這個(gè)鄰近區(qū)域內(nèi), , 那么牛頓那么牛頓法必定收斂。法必定收斂。 下面給出用牛頓迭代法，求形如下面給出用牛頓迭代法，求形如ax3+bx2+cx+d=0方程方程根的算法，系數(shù)根的算法，系數(shù)a、b、c、d的值依次為的值依次為1、2、3、4，由，由主函數(shù)輸入。求主函數(shù)輸入。求x在在1附近的一個(gè)實(shí)根。求出根后由主函數(shù)輸附近的一個(gè)實(shí)根。求出根后由主函數(shù)輸出。出。 大連海事大學(xué)Design and Analysis of Computer Algorithmsmain( ) float a , b, c, d, fx; p r i n

32、 t ( 輸 入 系 數(shù)輸 入 系 數(shù) a,b,c,d:); input(a,b,c,d); fx=f(a,b,c,d); printf(方程的根為：方程的根為：,fx);大連海事大學(xué)Design and Analysis of Computer Algorithms 令令a0,b0=a,ba0,b0=a,b，c0=(a0+b0)/2c0=(a0+b0)/2，若，若f(c0)=0f(c0)=0，則，則c0c0為方為方程程 f ( x ) = 0f ( x ) = 0 的 根 ； 否 則 ， 若的 根 ； 否 則 ， 若 f ( a 0 )f ( a 0 ) 與與 f ( c 0 )f ( c

33、0 ) 異 號(hào) ， 即異 號(hào) ， 即 f(a0)f(a0)* *f(c0)0f(c0)0，則令，則令a1,b1=a0,c0a1,b1=a0,c0；若；若f(b0)f(b0)與與f(c0)f(c0)異號(hào)，異號(hào)，即即 f(b0)f(b0)* *f(c0)0f(c0)0，則令，則令a1,b1=c0,b0a1,b1=c0,b0。 依此做下去，當(dāng)發(fā)現(xiàn)依此做下去，當(dāng)發(fā)現(xiàn)f(cn)=0時(shí)，或區(qū)間時(shí)，或區(qū)間an,bn足夠足夠小，比如小，比如| an-bn |0.0001時(shí)，就認(rèn)為找到了方程的根。時(shí)，就認(rèn)為找到了方程的根。 用二分法求一元非線性方程用二分法求一元非線性方程f(x)= x3/2+2x2-8=0（其

34、中（其中表示冪運(yùn)算）在區(qū)間表示冪運(yùn)算）在區(qū)間0，2上的近似實(shí)根上的近似實(shí)根r，精確到，精確到0.0001.算法如下：算法如下：大連海事大學(xué)圖圖4-6 4-6 二分法二分法求求解解方程方程示意示意Design and Analysis of Computer Algorithmsmain( )main( ) float x,x1=0,x2=2,f1,f2,f; float x,x1=0,x2=2,f1,f2,f; print( print(“input a,b (f(a)input a,b (f(a)* *f(b)0)f(b)0) printf(No root); return;f20) pri

35、ntf(No root); return; do do x=(x1+x2)/2; x=(x1+x2)/2; f=x f=x* *x x* *x/2+2x/2+2* *x x* *x-8;x-8; if(f=0) break; if(f=0) break; if(f1 if(f1* *f0.0) x1=x; f1=x1f0.0) x1=x; f1=x1* *x1x1* *x1/2+2x1/2+2* *x1x1* *x1-8;x1-8; else x2=x; else x2=x;while(fabs(f)=1e-4);while(fabs(f)=1e-4);print(root=,x); prin

36、t(root=,x); 大連海事大學(xué)Design and Analysis of Computer Algorithms4.2 蠻力法蠻力法4.2.1 4.2.1 枚舉法枚舉法4.2.2 4.2.2 其它范例其它范例大連海事大學(xué) 蠻力法是基于計(jì)算機(jī)運(yùn)算速度快這一特性，在解決問題時(shí)采蠻力法是基于計(jì)算機(jī)運(yùn)算速度快這一特性，在解決問題時(shí)采取的一種取的一種“ “懶惰懶惰” ”的策略。這種策略不經(jīng)過（或者說是經(jīng)過很少的）的策略。這種策略不經(jīng)過（或者說是經(jīng)過很少的）思考，把問題的所有情況或所有過程交給計(jì)算機(jī)去一一嘗試，從思考，把問題的所有情況或所有過程交給計(jì)算機(jī)去一一嘗試，從中找出問題的解。蠻力策略的應(yīng)用

37、很廣，具體表現(xiàn)形式各異，數(shù)中找出問題的解。蠻力策略的應(yīng)用很廣，具體表現(xiàn)形式各異，數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)的：選擇排序、冒泡排序、插入排序、順序查據(jù)結(jié)構(gòu)課程中學(xué)習(xí)的：選擇排序、冒泡排序、插入排序、順序查找、樸素的字符串匹配等，都是蠻力策略具體應(yīng)用。比較常用還找、樸素的字符串匹配等，都是蠻力策略具體應(yīng)用。比較常用還有有枚舉法枚舉法、盲目搜索算法等，本節(jié)介紹、盲目搜索算法等，本節(jié)介紹枚舉法枚舉法和其它一些小的范和其它一些小的范例，第五章介紹盲目搜索算法。例，第五章介紹盲目搜索算法。Design and Analysis of Computer Algorithms4 42 21 1 枚舉法枚舉法 大連海事

38、大學(xué)枚舉（枚舉（ enumerate）法（窮舉法）是蠻力策略的一種表現(xiàn)形式，）法（窮舉法）是蠻力策略的一種表現(xiàn)形式，也是一種使用非常普遍的思維方法。它是根據(jù)問題中的條件將可能也是一種使用非常普遍的思維方法。它是根據(jù)問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有的情況一一列舉出來，逐一嘗試從中找出滿足問題條件的解。但有時(shí)一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，時(shí)一一列舉出的情況數(shù)目很大，如果超過了我們所能忍受的范圍，則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題則需要進(jìn)一步考慮，排除一些明顯不合理的情況，盡可能減少問題可能解的列舉數(shù)目?？?/p>

39、能解的列舉數(shù)目。用枚舉法解決問題，通?？梢詮膬蓚€(gè)方面進(jìn)行算法設(shè)計(jì)：用枚舉法解決問題，通常可以從兩個(gè)方面進(jìn)行算法設(shè)計(jì)： 1）找出枚舉范圍：分析問題所涉及的各種情況。找出枚舉范圍：分析問題所涉及的各種情況。 2 2）找出約束條件：分析問題的解需要滿足的條件，并用邏輯）找出約束條件：分析問題的解需要滿足的條件，并用邏輯表達(dá)式表示。表達(dá)式表示。Design and Analysis of Computer Algorithms大連海事大學(xué)【例例1 1】百錢百雞問題。中國(guó)古代數(shù)學(xué)家張丘建在他的百錢百雞問題。中國(guó)古代數(shù)學(xué)家張丘建在他的算經(jīng)算經(jīng)中提出了著名的中提出了著名的“百錢百雞問題百錢百雞問題”：雞翁一

40、，值錢五；雞母一，：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何? ?算法設(shè)計(jì)算法設(shè)計(jì)1：通過對(duì)問題的理解，讀者可能會(huì)想到列出兩個(gè)三元一次方程，通過對(duì)問題的理解，讀者可能會(huì)想到列出兩個(gè)三元一次方程，去解這個(gè)不定解方程，就能找出問題的解。這確實(shí)是一種辦法，去解這個(gè)不定解方程，就能找出問題的解。這確實(shí)是一種辦法，但這里我們要用但這里我們要用“懶惰懶惰”的枚舉策略進(jìn)行算法設(shè)計(jì)：的枚舉策略進(jìn)行算法設(shè)計(jì)： 設(shè)設(shè)x，y，z分別為公雞、母雞、小雞的數(shù)量。分別為公雞、母雞、小雞的數(shù)量。 嘗試范圍：由嘗試范圍：由題意給定共題意給

41、定共100錢要買百雞，若全買公雞最多錢要買百雞，若全買公雞最多買買100/5=100/5=20只，顯然只，顯然x的取值范圍的取值范圍120之間；同理，之間；同理，y的取值范的取值范圍在圍在133之間，之間，z z的取值范圍的取值范圍在在11001100之間之間。 約束條件：約束條件： x+y+z=100 x+y+z=100 且且 5 5* *x+3x+3* *y+z/3=100y+z/3=100 Design and Analysis of Computer Algorithms大連海事大學(xué)算法算法1如下：如下：main( )main( ) int x,y,z; int x,y,z;for(x

42、=1;x=20;x=x+1)for(x=1;x=20;x=x+1) for(y=1;y=34;y=y+1) for(y=1;y=34;y=y+1) for(z=1;z=100;z=z+1) for(z=1;z=100;z=z+1) if(100=x+y+z and 100=5 if(100=x+y+z and 100=5* *x+3x+3* *y+z/3)y+z/3) print(the cock number is,x)print(the cock number is,x)； print(the hen number is, y)print(the hen number is, y)；pri

43、nt(the chick number is z);print(the chick number is z); Design and Analysis of Computer Algorithms大連海事大學(xué)算法分析：以上算法需要枚舉嘗試算法分析：以上算法需要枚舉嘗試20*34*100=68000次。次。算法的效率顯然太低算法的效率顯然太低算法設(shè)計(jì)算法設(shè)計(jì)2：在公雞（在公雞（x x）、母雞（）、母雞（y y）的數(shù)量確定后，小雞）的數(shù)量確定后，小雞的數(shù)量的數(shù)量z就固就固定為定為100-x-y，無需再進(jìn)行枚舉了，無需再進(jìn)行枚舉了此時(shí)此時(shí)約束條件只有一個(gè)：約束條件只有一個(gè)： 5*x+3*y+z/3=

44、100算法算法2如下：如下： Design and Analysis of Computer Algorithmsmain( )main( ) int x,y,z; int x,y,z;for(x=1;x=20;x=x+1)for(x=1;x=20;x=x+1) for(y=1;y=33;y=y+1)for(y=1;y=33;y=y+1) z=100-x-y;z=100-x-y; if(z mod 3=0 and 5if(z mod 3=0 and 5* *x+3x+3* *y+z/3=100)y+z/3=100)print(the cock number is,x)print(the coc

45、k number is,x)； print(the hen number is, y)print(the hen number is, y)；print(the chick number is z);print(the chick number is z); 算法分析：以上算法只需要枚舉嘗試算法分析：以上算法只需要枚舉嘗試20*33=660次。實(shí)現(xiàn)時(shí)約次。實(shí)現(xiàn)時(shí)約束條件又限定束條件又限定Z能被能被3整除時(shí)，才會(huì)判斷整除時(shí)，才會(huì)判斷“5 5* *x+3x+3* *y+z/3=100y+z/3=100”。這。這樣省去了樣省去了z z不整除不整除3 3時(shí)的算術(shù)計(jì)算和條件時(shí)的算術(shù)計(jì)算和條件判斷，判斷，

46、進(jìn)一步提高了算法進(jìn)一步提高了算法的效率。的效率。 大連海事大學(xué)Design and Analysis of Computer Algorithms【例例2 2】解數(shù)字迷：解數(shù)字迷： A B C A BA B C A B A A D D D D D D D D D D D D算法設(shè)計(jì)算法設(shè)計(jì)1 1：按乘法枚舉按乘法枚舉1)1)枚舉范圍為：枚舉范圍為： A A：3 39 9（A=1A=1，2 2時(shí)積不會(huì)得到六位數(shù)）時(shí)積不會(huì)得到六位數(shù)）,B,B：0 09,9, C C：0 09 9 六位數(shù)表示為六位數(shù)表示為A A* *10000+B10000+B* *1000+C1000+C* *100+A100+

47、A* *10+B10+B， 共嘗試共嘗試800800次。次。2)2)約束條件為：約束條件為： 每次嘗試，先求六位數(shù)與每次嘗試，先求六位數(shù)與A A的積，再測(cè)試積的各位是否相的積，再測(cè)試積的各位是否相 同，若相同則找到了問題的解。同，若相同則找到了問題的解。 測(cè)試積的各位是否相同比較簡(jiǎn)單的方法是，從低位開始，測(cè)試積的各位是否相同比較簡(jiǎn)單的方法是，從低位開始， 每次都取數(shù)據(jù)的個(gè)位，然后整除每次都取數(shù)據(jù)的個(gè)位，然后整除1010，使高位的數(shù)字不斷變，使高位的數(shù)字不斷變 成個(gè)位，并逐一比較。成個(gè)位，并逐一比較。 大連海事大學(xué)Design and Analysis of Computer Algorithm

48、s算法算法1 1如下：如下：main（ ） int A,B,C,D,E,E1,F,G1,G2,i; for(A=3; A=9; A+) for(B=0; B=9; B+) for(C=0; C=9; C+) F=A*10000+B*1000+C*100+A*10+B; E=F*A； E1=E; G1=E1 mod 10; for(i=1; i=5; i+) G2=G1; E1=E1/10; G1= E1 mod 10; if(G1G2 ) break; if(i=6) print( F，”*”，A，”=”，E); 大連海事大學(xué)Design and Analysis of Computer Al

49、gorithms大連海事大學(xué)算法中對(duì)枚舉出的每一個(gè)五位數(shù)與算法中對(duì)枚舉出的每一個(gè)五位數(shù)與A A相乘，結(jié)果相乘，結(jié)果存儲(chǔ)在變量存儲(chǔ)在變量E E中。然后，測(cè)試得到的六位數(shù)中。然后，測(cè)試得到的六位數(shù)E E是否各個(gè)位的數(shù)是否各個(gè)位的數(shù)字都相同。鑒于要輸出結(jié)果，所以不要改變計(jì)算結(jié)果，而另字都相同。鑒于要輸出結(jié)果，所以不要改變計(jì)算結(jié)果，而另設(shè)變量設(shè)變量E1E1，用于測(cè)試運(yùn)算。，用于測(cè)試運(yùn)算。算法設(shè)計(jì)算法設(shè)計(jì)2 2：將算式變形為除法：將算式變形為除法：DDDDDD/A=ABCABDDDDDD/A=ABCAB。此時(shí)。此時(shí)只需枚舉只需枚舉A A：3 39 D9 D：1 19 9，共嘗試，共嘗試7 7* *9=6

50、39=63次。每次次。每次嘗試，測(cè)試商的萬位、十位與除數(shù)是否相同，千位與個(gè)位嘗試，測(cè)試商的萬位、十位與除數(shù)是否相同，千位與個(gè)位是否相同，都相同時(shí)為解。是否相同，都相同時(shí)為解。算法算法2 2如下如下: :Design and Analysis of Computer Algorithms大連海事大學(xué)mainmain（）（）int A,B,C,D,E,F;int A,B,C,D,E,F; for(A=3;A=9;A+) for(A=3;A=9;A+) for(D=1;D=9;D+) for(D=1;D=9;D+) E = D E = D* *100000+D100000+D* *10000+D10

51、000+D* *1000+D1000+D* *100+D100+D* *10+D;10+D; if(E mod A=0) F=EA; if(E mod A=0) F=EA; if(F10000=A and (F mod 100)10=A) if(F10000=A and (F mod 100)10=A) if(F1000=F mod 10) if(F1000=F mod 10) print( F print( F，”* *”，A A，”=”=”，E);E); Design and Analysis of Computer Algorithms4 42 22 2 其它范例其它范例大連海事大學(xué) 蠻

52、力法的表現(xiàn)形式非常多，如第三章蠻力法的表現(xiàn)形式非常多，如第三章3.2.4例題、例題、3.2.5例例1及本章下一節(jié)及本章下一節(jié)4.3.3例例4的算法的算法1等。本節(jié)將通過蠻力策略，用等。本節(jié)將通過蠻力策略，用算法模擬問題中所描述的全部過程和全部狀態(tài)，來找出問題的解，算法模擬問題中所描述的全部過程和全部狀態(tài)，來找出問題的解，并與經(jīng)過數(shù)學(xué)建模后的算法進(jìn)行效率上的比較。并與經(jīng)過數(shù)學(xué)建模后的算法進(jìn)行效率上的比較。Design and Analysis of Computer Algorithms【例例3 3】獄吏問題獄吏問題 某國(guó)王對(duì)囚犯進(jìn)行大赦，讓一獄吏某國(guó)王對(duì)囚犯進(jìn)行大赦，讓一獄吏n n次通過一排鎖

53、著的次通過一排鎖著的n n間牢房，每通過一次，按所定規(guī)則轉(zhuǎn)動(dòng)間牢房，每通過一次，按所定規(guī)則轉(zhuǎn)動(dòng)n n間牢房中的某些門間牢房中的某些門鎖鎖, , 每轉(zhuǎn)動(dòng)一次每轉(zhuǎn)動(dòng)一次, , 原來鎖著的被打開原來鎖著的被打開, , 原來打開的被鎖上；原來打開的被鎖上；通過通過n n次后，門鎖開著的，牢房中的犯人放出，否則犯人不次后，門鎖開著的，牢房中的犯人放出，否則犯人不得獲釋。得獲釋。 轉(zhuǎn)動(dòng)門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動(dòng)每轉(zhuǎn)動(dòng)門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動(dòng)每一把門鎖，即把全部鎖打開；第二次通過牢房時(shí)，從第二間一把門鎖，即把全部鎖打開；第二次通過牢房時(shí)，從第二間開始轉(zhuǎn)動(dòng)，每隔一間轉(zhuǎn)動(dòng)一次；

54、第開始轉(zhuǎn)動(dòng)，每隔一間轉(zhuǎn)動(dòng)一次；第k k次通過牢房，從第次通過牢房，從第k k間開間開始轉(zhuǎn)動(dòng)，每隔始轉(zhuǎn)動(dòng)，每隔k-1 k-1 間轉(zhuǎn)動(dòng)一次；問通過間轉(zhuǎn)動(dòng)一次；問通過n n次后，那些牢房的次后，那些牢房的鎖仍然是打開的？鎖仍然是打開的？大連海事大學(xué)Design and Analysis of Computer Algorithms算法設(shè)計(jì)算法設(shè)計(jì)1 1：1 1）用用n n個(gè)空間的一維數(shù)組個(gè)空間的一維數(shù)組an,an,每個(gè)元素每個(gè)元素記錄一個(gè)鎖的狀記錄一個(gè)鎖的狀 態(tài)，態(tài)，1 1為為被鎖上，被鎖上，0 0為被打開。為被打開。2 2）用數(shù)學(xué)運(yùn)算方便模擬開關(guān)鎖的技巧，對(duì)）用數(shù)學(xué)運(yùn)算方便模擬開關(guān)鎖的技巧，對(duì)i

55、i號(hào)鎖的一次開號(hào)鎖的一次開 關(guān)鎖可以轉(zhuǎn)化為算術(shù)運(yùn)算：關(guān)鎖可以轉(zhuǎn)化為算術(shù)運(yùn)算：ai=1-aiai=1-ai。3 3）第一次轉(zhuǎn)動(dòng)的是）第一次轉(zhuǎn)動(dòng)的是1 1，2 2，3 3，n n號(hào)牢房；號(hào)牢房； 第二次轉(zhuǎn)動(dòng)的是第二次轉(zhuǎn)動(dòng)的是2 2，4 4，6 6，號(hào)牢房；號(hào)牢房； 第三次轉(zhuǎn)動(dòng)的是第三次轉(zhuǎn)動(dòng)的是3 3，6 6，9 9，號(hào)牢房；號(hào)牢房； 第第i i次轉(zhuǎn)動(dòng)的是次轉(zhuǎn)動(dòng)的是i i，2i2i，3i3i，4i4i，號(hào)牢房，是起號(hào)牢房，是起點(diǎn)為點(diǎn)為i i，公差為，公差為i i的等差數(shù)列。的等差數(shù)列。 4 4）不做其它的優(yōu)化，用蠻力法通過循環(huán)模擬獄吏的開關(guān)）不做其它的優(yōu)化，用蠻力法通過循環(huán)模擬獄吏的開關(guān) 鎖過程，最

56、后當(dāng)?shù)阪i過程，最后當(dāng)?shù)趇號(hào)牢房對(duì)應(yīng)的數(shù)組元素號(hào)牢房對(duì)應(yīng)的數(shù)組元素aiai為為0 0時(shí)，時(shí)， 該牢房的囚犯得到大赦。算法該牢房的囚犯得到大赦。算法1如下：如下： 大連海事大學(xué)Design and Analysis of Computer Algorithmsmain1( )main1( )int int * *a,i,j,n;a,i,j,n; input(n); input(n); a=calloc(n+1,sizeof(int); a=calloc(n+1,sizeof(int); for (i=1; i=n;i+) for (i=1; i=n;i+) ai=1; ai=1; for (i=1

57、; i=n;i+) for (i=1; i=n;i+) for (j=i; j=n;j=j+i) for (j=i; j=n;j=j+i) ai=1-ai; ai=1-ai; for (i=1; i=n;i+) for (i=1; i=n;i+) if (ai=0) print(i, if (ai=0) print(i,”is free.is free.”);); 算法分析：算法分析：以一次開關(guān)鎖計(jì)算，算法的時(shí)間復(fù)雜度為以一次開關(guān)鎖計(jì)算，算法的時(shí)間復(fù)雜度為n(1+1/2+1/3+n(1+1/2+1/3+1/n)=O(nlogn)+1/n)=O(nlogn)。大連海事大學(xué)Design and Analysis of Computer Algorithms問題分析：?jiǎn)栴}分析：轉(zhuǎn)動(dòng)門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動(dòng)轉(zhuǎn)動(dòng)門鎖的規(guī)則可以有另一種理解，第一次轉(zhuǎn)動(dòng)的是編號(hào)為的是編號(hào)為1 1的倍數(shù)的牢房；第二次轉(zhuǎn)動(dòng)的是編號(hào)為的倍數(shù)的牢房；第二次轉(zhuǎn)動(dòng)的是編號(hào)為2 2的倍的倍數(shù)的牢房；第三次轉(zhuǎn)動(dòng)的是編號(hào)為數(shù)的牢房；第三次轉(zhuǎn)動(dòng)的是編號(hào)為3 3的倍數(shù)的牢房；的倍數(shù)的牢房；則則獄吏問題是一個(gè)關(guān)于因子個(gè)數(shù)的獄吏問題是一個(gè)關(guān)于因子個(gè)數(shù)的問題。令問題。令d(n)d(n)為自然數(shù)為自然數(shù)n n的因子個(gè)數(shù)，這里不計(jì)重復(fù)的因子，如的因子個(gè)數(shù)，這里不計(jì)重復(fù)的因子，如4 4的因子為的因子為1 1，2