算法第4章-第1講-迭代法、蠻力法_1

1、 計算機科學學院 王小明 （博士博士/ /教授教授/ /博士生導師博士生導師） Email: 每節(jié)一經典每節(jié)一經典用算法的視覺處理問題：用算法的視覺處理問題：有窮性，確定性，可行性，輸入輸出有窮性，確定性，可行性，輸入輸出 迭代算法迭代算法迭代法迭代法(iteration): (iteration): 用變量的舊值不斷遞推出新值的解決用變量的舊值不斷遞推出新值的解決 問題的方法。通常用于數值計算。問題的方法。通常用于數值計算。例例4.1 S=04.1 S=0 i=1 i=1 FOR (i100;i+1) FOR (i100;i+1) S=S+i; S=S+i; 第4講 基本算法策略例例4.24

2、.2 設方程為設方程為f(x)=0f(x)=0，用某種數學方法導出等價，用某種數學方法導出等價 的形式的形式x=g(x)x=g(x)，然后按以下步驟執(zhí)行：，然后按以下步驟執(zhí)行：Step 1 Step 1 選一個方程的近似根，賦給變量選一個方程的近似根，賦給變量x0 x0；Step 2 Step 2 將將x0 x0的值保存于變量的值保存于變量x1x1，然后計算，然后計算g(x1)g(x1)， 并將結果存于變量并將結果存于變量x0 x0； Step 3 Step 3 當當x0 x0與與x1x1的差的絕對值不小于指定的精度的差的絕對值不小于指定的精度 要求時，重復步驟（要求時，重復步驟（2 2）的計

3、算。）的計算。 即當即當x1-x0 x1-x0Epsilon) while ( fabs(x0-x1)Epsilon)； printf(“printf(“方程的近似根是方程的近似根是%fn”%fn”，x0)x0)； 第4講 基本算法策略具體使用迭代法求根時應注意以下兩種可能發(fā)生的情況具體使用迭代法求根時應注意以下兩種可能發(fā)生的情況:（1）如果方程無解，算法求出的近似根序列）如果方程無解，算法求出的近似根序列 就不會收斂，迭代過程會變成死循環(huán)，因此就不會收斂，迭代過程會變成死循環(huán)，因此 在使用迭代算法前應先考察方程是否有解，在使用迭代算法前應先考察方程是否有解， 并在程序中對迭代的次數給予限制；

4、并在程序中對迭代的次數給予限制；（2）方程雖然有解，但迭代公式選擇不當，或）方程雖然有解，但迭代公式選擇不當，或 迭代的初始近似根選擇不合理，也會導致迭迭代的初始近似根選擇不合理，也會導致迭 代失敗。代失敗。 第4講 基本算法策略（1） 遞推法遞推法迭代法迭代法 倒推法倒推法 第4講 基本算法策略1 1）遞推法）遞推法 遞推法是利用問題本身所具有的一種遞推關系求問題解的一遞推法是利用問題本身所具有的一種遞推關系求問題解的一種方法。種方法。 例如，求解規(guī)模為例如，求解規(guī)模為n n的問題，當的問題，當n=1n=1時，解或為已知，或能非時，解或為已知，或能非常方便地得到。能采用遞推法構造算法的問題具

5、有重要的遞推常方便地得到。能采用遞推法構造算法的問題具有重要的遞推性質，即當得到問題規(guī)模為性質，即當得到問題規(guī)模為i-1i-1的解后，由問題的遞推性質，能的解后，由問題的遞推性質，能從已求得的規(guī)模為從已求得的規(guī)模為1 1，2 2，i-1i-1的一系列解，構造出問題規(guī)模的一系列解，構造出問題規(guī)模為為i i的解。這樣，程序可從的解。這樣，程序可從i=0i=0或或i=1i=1出發(fā)，重復地，由已知至出發(fā)，重復地，由已知至i-i-1 1規(guī)模的解，通過遞推，獲得規(guī)模為規(guī)模的解，通過遞推，獲得規(guī)模為i i的解，直至得到規(guī)模為的解，直至得到規(guī)模為n n的的解。解。 第4講 基本算法策略例例4.24.2 mai

6、n() main() int i,a=1,b=1;int i,a=1,b=1; print(a,b); print(a,b); for(i=1;i=5;i=i+1) for(i=1;i=1;i=i-1) for (i=9;i=1;i=i-1) a=2 a=2* *( (a a+1)+1) print(a); print(a); 第4講 基本算法策略 課外習題：課外習題： p128,p128,例例5 5：穿越沙漠問題：穿越沙漠問題第4講 基本算法策略 迭代法解方程：迭代法解方程： 閱讀閱讀p130-133,p130-133,例例6 6，例，例7 7，例，例8 8第4講 基本算法策略 作業(yè)：作業(yè)：

7、 預習預習p133-138: p133-138: 蠻力法蠻力法第4講 基本算法策略Thats all for todayThats all for todaySee you next timeSee you next timeGood bye! Good bye! 計算機科學學院 王小明 （博士博士/ /教授教授/ /博士生導師博士生導師） Email: 每節(jié)一經典每節(jié)一經典用用9 9以內的實例理解問題：以內的實例理解問題：手工模擬計算過程手工模擬計算過程 蠻力法蠻力法：把問題的所有情況或所有過程交給計算：把問題的所有情況或所有過程交給計算 機去一一嘗試，從中找出問題的解。機去一一嘗試，從中找

8、出問題的解。例例4.4 4.4 順序查找，選擇排序，冒泡排序，插入排順序查找，選擇排序，冒泡排序，插入排序等等。序等等。 從序列從序列 2 2，5 5，8 8，9 9，1212，1717中查找中查找2323，需要從，需要從第一個數第一個數2 2開始，逐一向后查，直到末尾數開始，逐一向后查，直到末尾數1717，才斷定此序列中沒有這個數。才斷定此序列中沒有這個數。 第4講 蠻力法 枚舉法枚舉法(enumerate)(enumerate)：蠻力策略的一種具體表現形式。根據問題：蠻力策略的一種具體表現形式。根據問題中的條件將可能的情況一一列舉出來，逐一嘗試從中找出滿足中的條件將可能的情況一一列舉出來，

9、逐一嘗試從中找出滿足問題條件的解。問題條件的解。 缺點：當問題情況數目太多時，太費時間。缺點：當問題情況數目太多時，太費時間。 改進策略：忽略一些明顯不可能的情況，以減少列舉的可能解改進策略：忽略一些明顯不可能的情況，以減少列舉的可能解數目。數目。 方法：方法：1 1）找出枚舉范圍：分析問題各種情況。）找出枚舉范圍：分析問題各種情況。 2 2）找出約束條件：分析問題的解需要滿足的條件，并用）找出約束條件：分析問題的解需要滿足的條件，并用 邏輯表達式表示。邏輯表達式表示。 第4講 蠻力法 例例4.54.5 百錢百雞問題。如何用百錢百雞問題。如何用100100元買元買100100只雞？只雞？ 雞翁

10、雞翁1 1，值錢，值錢5 5，雞母，雞母1 1，值錢，值錢3 3，雞仔，雞仔3 3，值錢，值錢1 1。問題分析：問題分析：用用100100元恰好買元恰好買100100只雞；設只雞；設x,y,zx,y,z表示公雞、母雞、雞表示公雞、母雞、雞 仔數量。仔數量。數學模型：數學模型：1 1）枚舉范圍：）枚舉范圍：0 x100/5; 0 x100/5; 0y100/3; 0y100/3; 0z3 0z3* *100;100;2) 2) 約束條件：約束條件：x+y+z=100;x+y+z=100; 5x+3y+z/3=100 5x+3y+z/3=100 第4講 蠻力法計算模型計算模型: : （試探法，即枚

11、舉法）（試探法，即枚舉法）0=x=100/5; 0=x=100/5; 0=y=100/3; 0=y=100/3; 0=z=3 0=z=3* *100;100; 如果如果 x+y+z=100 x+y+z=100并且并且 5x+3y+z/3=1005x+3y+z/3=100 那么那么 此時的此時的x,y,zx,y,z值正好是問題答案值正好是問題答案 否則否則 繼續(xù)試探。繼續(xù)試探。 第4講 蠻力法 算法描述算法描述(3(3重循環(huán)重循環(huán)) )：main()main() int x,y,z; int x,y,z; for(x=0;x=20 for(x=0;x=20；x=x+1)x=x+1) for(y=

12、0;y=33;y=y+1) for(y=0;y=33;y=y+1) for(z=0;z=300;z=z+1) for(z=0;z=300;z=z+1) if x+y+z=100 and 5 if x+y+z=100 and 5* *x+3x+3* *y+z/3=100y+z/3=100 print(x,y,z) print(x,y,z) 第4講 蠻力法 算法分析算法分析：上述算法共枚舉嘗試：上述算法共枚舉嘗試2020* *3333* *300=198000300=198000次次缺點：缺點：時間效率低時間效率低改進策略：改進策略：1 1）當公雞和母雞數量確定之后，小雞數量為）當公雞和母雞數量確

13、定之后，小雞數量為 100-x-y, 100-x-y,不需要對小雞數量進行枚舉。不需要對小雞數量進行枚舉。 2 2）只有當）只有當z z值被值被3 3整除時，解才可能有意義。整除時，解才可能有意義。 約束條件：約束條件：z z modmod 3=0; 5x+3y+z/3=100 3=0; 5x+3y+z/3=100 第4講 蠻力法 優(yōu)化算法（優(yōu)化算法（3 3重循環(huán)變重循環(huán)變2 2重循環(huán)）重循環(huán)）：main()main() int x,y,z; int x,y,z; for(x=0;x=20 for(x=0;x=20；x=x+1)x=x+1) for(y=0;y=33;y=y+1) for(y=

14、0;y=33;y=y+1) if z if z modmod 3=0 and 5 3=0 and 5* *x+3x+3* *y+z/3=100y+z/3=100 print(x,y,z) print(x,y,z) 第4講 蠻力法 算法分析：算法分析：上述算法共枚舉嘗試上述算法共枚舉嘗試2020* *33=66033=660次次 優(yōu)點：優(yōu)點：時間效率高（和第一個算法相比）時間效率高（和第一個算法相比）思考與實踐驗證問題：思考與實踐驗證問題：1 1）如果把上述算法中的循環(huán)順序）如果把上述算法中的循環(huán)順序 改變，結果一樣嗎？改變，結果一樣嗎？ 2 2）如果把上述算法中的循環(huán)順序）如果把上述算法中的循

15、環(huán)順序 改變，共枚舉的次數是否相同？改變，共枚舉的次數是否相同？課堂練習課堂練習：P134,P134,例例1010。 第4講 蠻力法 例例1212 獄吏問題：誰能從監(jiān)獄獲得自由？獄吏問題：誰能從監(jiān)獄獲得自由？ 國王對囚犯進行大赦，游戲規(guī)則是：讓一個獄吏國王對囚犯進行大赦，游戲規(guī)則是：讓一個獄吏n n次通過一排鎖次通過一排鎖著的牢房，每通過一次，按規(guī)則轉動著的牢房，每通過一次，按規(guī)則轉動n n間牢房中某些門鎖，每轉間牢房中某些門鎖，每轉一次，原來鎖著的被打開，原來開著的被鎖上；通過一次，原來鎖著的被打開，原來開著的被鎖上；通過n n次后，門次后，門鎖開著的牢房中的犯人獲得釋放。鎖開著的牢房中的犯

16、人獲得釋放。規(guī)則：規(guī)則：1 1）第一次通過時：每間房門鎖被打開；）第一次通過時：每間房門鎖被打開； 2 2）第二次通過時：從第二間開始轉動，每隔）第二次通過時：從第二間開始轉動，每隔1 1間轉動一次間轉動一次 3) 3) 第三次通過時：從第三間開始轉動，每隔第三次通過時：從第三間開始轉動，每隔2 2間轉動一次間轉動一次 k) k) 第第k k次通過時：從第次通過時：從第k k間開始轉動，每隔間開始轉動，每隔k-1k-1間轉動一次間轉動一次 第4講 蠻力法 在在“9”9”以內理解以內理解獄吏問題：以獄吏問題：以6 6個牢房為例。個牢房為例。145632牢房 Y Y Y Y Y Y Y X Y X

17、 Y X Y X X X Y Y Y X X Y Y Y Y X X Y X Y Y X X Y Y X X X X X X X 問題分析：第問題分析：第1 1次轉動門鎖房號：次轉動門鎖房號：1 1，2 2，,n,n 第第2 2次轉動門鎖房號：次轉動門鎖房號：2 2，4,6,4,6, 第第3 3次轉動門鎖房號：次轉動門鎖房號：3 3，6,9,6,9, 第第i i次轉動門鎖房號：次轉動門鎖房號：i i，2i2i，3i,3i, 即：它們是起點為即：它們是起點為i,i,公差為公差為i i的等差數列。的等差數列。 最后一次只轉動第最后一次只轉動第n n號門鎖一次。號門鎖一次。算法設計思想：算法設計思想

18、：1 1）數組元素）數組元素ai(i=1,2,n)ai(i=1,2,n)的初值均的初值均 （計算模型）（計算模型） 為為1 1表示所有門鎖著，門號與鎖號相表示所有門鎖著，門號與鎖號相 同。同。ajaj為為0 0時表示鎖號為時表示鎖號為j j的鎖鎖著。的鎖鎖著。 2 2）當第）當第j j號門鎖被轉動時，號門鎖被轉動時，aj=1-ajaj=1-aj 3) 3) 每趟用每趟用i i表示，表示，1=i=n1=i=n 4) 4) 每趟從第每趟從第j j個（個（j=ij=i）鎖開起，每隔）鎖開起，每隔i i個個 鎖轉動一次，表示為鎖轉動一次，表示為j=j+i,i=j=nj=j+i,i=j=n例如例如，當，

19、當aj=1aj=1時，則時，則aj=1-aj=1-1=0aj=1-aj=1-1=0； 當當aj=0aj=0時，則時，則aj=1-aj=1-0=1aj=1-aj=1-0=1算法設計算法設計: : ( (共三個階段：初始階段，反復開共三個階段：初始階段，反復開- -關鎖階段，放人判定哪些鎖開著關鎖階段，放人判定哪些鎖開著) )Main()Main() 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=i+1)for(i

20、=1;i=n;i=i+1) ai=1; ai=1; for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1) for(j=i;j=n;j=j+i) for(j=i;j=n;j=j+i) aj=1-aj; aj=1-aj; for(i=1;i=n;i=i+1)for(i=1;i=n;i=i+1) if (ai=0) if (ai=0) print(i,”is free”); print(i,”is free”); 初始化，給數組初始化，給數組a分分配配n+1個內存空間個內存空間使使n個門鎖標志全為個門鎖標志全為1，表示門都鎖著表示門都鎖著獄吏走獄吏走n趟，每趟用趟，每趟用i標記，

21、標記，每趟轉動的門鎖號用每趟轉動的門鎖號用j表示表示輸出鎖開著的牢房號（鎖號）輸出鎖開著的牢房號（鎖號）算法分析算法分析：1)1)仔細分析算法可以看出，模擬獄吏開鎖的仔細分析算法可以看出，模擬獄吏開鎖的 語句語句aj=1-ajaj=1-aj是關鍵語句，所以選擇該是關鍵語句，所以選擇該 語句執(zhí)行的總次數衡量算法復雜度。語句執(zhí)行的總次數衡量算法復雜度。 該語句執(zhí)行的總次數為：該語句執(zhí)行的總次數為： f(n)=n+n/2+n/3+1 f(n)=n+n/2+n/3+1 則時間復雜度為則時間復雜度為O(nlongO(nlongn n) ) 2)2)共用了共用了n+1n+1個數組空間，所以空間復雜度為個數

22、組空間，所以空間復雜度為 S(n)=S(n+1)=S(n), S(n)=S(n+1)=S(n),表示隨著問題規(guī)模表示隨著問題規(guī)模n n的增大，算法的增大，算法執(zhí)行所需存儲空間的增長率與執(zhí)行所需存儲空間的增長率與n n的增長率相同的增長率相同. .課堂練習課堂練習：閱讀理解算法：閱讀理解算法2 2和算法和算法3 3算法算法2 2關鍵點關鍵點：求一個數的不同的因數個數：求一個數的不同的因數個數算法思想算法思想：第：第1 1次被轉動門鎖的編號是次被轉動門鎖的編號是1 1的倍數；的倍數； 第第2 2次被轉動門鎖的編號是次被轉動門鎖的編號是2 2的倍數；的倍數； 第第3 3次被轉動門鎖的編號是次被轉動門

23、鎖的編號是3 3的倍數；的倍數； 第第i i次被轉動門鎖的編號是次被轉動門鎖的編號是i i的倍數；的倍數；總結上述規(guī)律總結上述規(guī)律：獄吏問題轉化為數的因子個數問題獄吏問題轉化為數的因子個數問題用用n n表示數，用表示數，用d(n)d(n)表示表示n n的因子個數的因子個數例如：例如： n 1 2 3 4 5 6 n 1 2 3 4 5 6 因數因數 11 1,21,2 1,31,3 1,2,41,2,4 1,51,51,2,3,61,2,3,6 d(n) 1 2 2 3 2 4 d(n) 1 2 2 3 2 4 建立數學模型：由于牢房開始是關閉著的，所以如果建立數學模型：由于牢房開始是關閉著的

24、，所以如果d(i)d(i)是奇數，則編號為是奇數，則編號為i i的牢房最后是開著的。的牢房最后是開著的。看下頁圖來初步驗證數學模型的正確性。看下頁圖來初步驗證數學模型的正確性。 在在“9”9”以內理解以內理解獄吏問題：以獄吏問題：以6 6牢房為例。牢房為例。145632牢房 Y Y Y Y Y Y Y X Y X Y X Y X X X Y Y Y X X Y Y Y Y X X Y X Y Y X X Y Y X X X X X X X 算法算法2 2：Main2()Main2() int s,I,j,n;int s,I,j,n; input(n); input(n); for(i=1;i=

25、n;i=i+1) for(i=1;i=n;i=i+1) s=1; s=1; for(j=2;j=i;j=j+1) for(j=2;j=i;j=j+1) if(i mod j)=0; if(i mod j)=0; s=s+1; s=s+1; if(s mod 2=1) if(s mod 2=1) print(i,”is free”); print(i,”is free”); 用枚舉法（蠻力法）用枚舉法（蠻力法）求求i的因子個數的因子個數輸出鎖開著的牢房號（鎖號）輸出鎖開著的牢房號（鎖號）1是每個數的因子，因此每個數至少有一個因子，是每個數的因子，因此每個數至少有一個因子，s表示表示i的因子個數的因子個數算法算法2 2：Main2()Main2() int s,I,j,n;int s,I,j,n; input(n); input(n); for(i=1;i=n;i=i+1) for(i=1;i=n;i=i+1) s=1; s=1; for(j=2;j=i;j=j+1) for(j=2;j=i;j=j+1) if(i mod j)=0; if(i mod j)=0; s=s+1; s=s+1; if(s mod 2=1) if(s mod 2=1) print(i,”is free”); print(i,”is free”); 時間復雜度：執(zhí)行頻次最高的語句是時間復雜度