第4章循環(huán)控制

1、程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 1重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 2v 格式：格式：forfor（表達(dá)式（表達(dá)式1 1；表達(dá)式；表達(dá)式2 2；表達(dá)式；表達(dá)式3 3） 語句語句v執(zhí)行過程：執(zhí)行過程：1.1.執(zhí)行表達(dá)式執(zhí)行表達(dá)式1 12.2.執(zhí)行表達(dá)式執(zhí)行表達(dá)式2 23.3.如果表達(dá)式如果表達(dá)式2 2的結(jié)果為的結(jié)果為“truetrue”，則執(zhí)行循環(huán)體，則執(zhí)行循環(huán)體和表達(dá)式和表達(dá)式3 3，然后回到，然后回到2 2，否則，否則forfor語句執(zhí)行結(jié)

2、束語句執(zhí)行結(jié)束循環(huán)體循環(huán)體循環(huán)控制行循環(huán)控制行程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 3v作為計(jì)數(shù)循環(huán)，可以理解為作為計(jì)數(shù)循環(huán)，可以理解為for(for(循環(huán)變量賦初值；循環(huán)條件；循環(huán)變量增值循環(huán)變量賦初值；循環(huán)條件；循環(huán)變量增值) ) 符合循環(huán)條件時(shí)的執(zhí)行語句符合循環(huán)條件時(shí)的執(zhí)行語句v循環(huán)體所有語句的一次完全執(zhí)行稱為一個(gè)循循環(huán)體所有語句的一次完全執(zhí)行稱為一個(gè)循環(huán)周期環(huán)周期v循環(huán)體可以是復(fù)合語句或空語句循環(huán)體可以是復(fù)合語句或空語句程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 4v格式：表達(dá)式格式：表達(dá)式1，表達(dá)式，表達(dá)式2，,表達(dá)式表達(dá)式n v執(zhí)行過程：先執(zhí)行表達(dá)式執(zhí)行過程：

3、先執(zhí)行表達(dá)式1，再執(zhí)行表達(dá)式，再執(zhí)行表達(dá)式2， ，再執(zhí)行表達(dá)式，再執(zhí)行表達(dá)式n，整個(gè)表達(dá)式的計(jì)算，整個(gè)表達(dá)式的計(jì)算結(jié)果為最后一個(gè)表達(dá)式的值結(jié)果為最后一個(gè)表達(dá)式的值v逗號(hào)運(yùn)算符的優(yōu)先級(jí)是所有運(yùn)算符中最低的逗號(hào)運(yùn)算符的優(yōu)先級(jí)是所有運(yùn)算符中最低的 如如a的初值為的初值為0，則表達(dá)式，則表達(dá)式 a += 1, a += 2, a += 3, a += 4, a += 5的結(jié)果為的結(jié)果為 15 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 5v有了逗號(hào)表達(dá)式，從有了逗號(hào)表達(dá)式，從1加到加到100的問題就的問題就可以只用一個(gè)語句：可以只用一個(gè)語句：for (i=1, s=0; i=100; +i)

4、s += i; 或?qū)⑺械某跏蓟挤旁谘h(huán)外，即或?qū)⑺械某跏蓟挤旁谘h(huán)外，即i=1； s=0；for ( ； i=100; +i) s += i;v建議還是用建議還是用 s=0;s=0; for (i=1; i=100; +i) s += i; for (i=1; i=100; +i) s += i;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 6v表達(dá)式表達(dá)式2也不一定是關(guān)系表達(dá)式。它可以是邏輯也不一定是關(guān)系表達(dá)式。它可以是邏輯表達(dá)式，甚至可以是算術(shù)表達(dá)式。當(dāng)表達(dá)式表達(dá)式，甚至可以是算術(shù)表達(dá)式。當(dāng)表達(dá)式2是是算術(shù)表達(dá)式時(shí)，只要表達(dá)式的值為非算術(shù)表達(dá)式時(shí)，只要表達(dá)式的值為非0，就執(zhí)行

5、，就執(zhí)行循環(huán)體，表達(dá)式的值為循環(huán)體，表達(dá)式的值為0時(shí)退出循環(huán)。時(shí)退出循環(huán)。v如果表達(dá)式如果表達(dá)式2省略，即不判斷循環(huán)條件，循環(huán)將省略，即不判斷循環(huán)條件，循環(huán)將無終止地進(jìn)行下去。無終止地進(jìn)行下去。v無終止的循環(huán)稱為無終止的循環(huán)稱為“死循環(huán)死循環(huán)” v最簡單的死循環(huán)是最簡單的死循環(huán)是 for (;); v要結(jié)束一個(gè)無限循環(huán)，必須從鍵盤上輸入特殊的要結(jié)束一個(gè)無限循環(huán)，必須從鍵盤上輸入特殊的命令以中斷程序執(zhí)行并強(qiáng)制退出命令以中斷程序執(zhí)行并強(qiáng)制退出 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 7v表達(dá)式表達(dá)式3也可以是任何表達(dá)式，一般為賦值表也可以是任何表達(dá)式，一般為賦值表達(dá)式或逗號(hào)表達(dá)式。表達(dá)

6、式達(dá)式或逗號(hào)表達(dá)式。表達(dá)式3是在每個(gè)循環(huán)周是在每個(gè)循環(huán)周期結(jié)束后對(duì)循環(huán)變量的修正。表達(dá)式期結(jié)束后對(duì)循環(huán)變量的修正。表達(dá)式3也可以也可以省略，此時(shí)做完循環(huán)體后直接執(zhí)行表達(dá)式省略，此時(shí)做完循環(huán)體后直接執(zhí)行表達(dá)式2。v如從如從1加到加到100，可以寫為，可以寫為 s=0; for (i=1; i=100; ) s += i, i+; 或或 s=0; for (i=1; i=100; s += i, i+) ;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 8v求函數(shù)求函數(shù) 在區(qū)間在區(qū)間a, b之間的定積分之間的定積分v實(shí)現(xiàn)思想：函數(shù)與實(shí)現(xiàn)思想：函數(shù)與x軸圍成的區(qū)域的面積。定積分軸圍成的區(qū)域的面積

7、。定積分可以通過將這塊面積分解成一連串的小矩形，計(jì)可以通過將這塊面積分解成一連串的小矩形，計(jì)算各小矩形的面積的和而得到算各小矩形的面積的和而得到 15)(2xxxf15)(2xxxfab程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 9int main()double a, b, dlt, integral = 0;cout a b; cout dlt; for (double x = a + dlt / 2; x b; x += dlt) integral += (x * x + 5 * x + 1) * dlt; cout 積分值為：積分值為： integral 0.000001) w

8、hile (p0.000001) ex += p; ex += p; 計(jì)算新的計(jì)算新的p p； 問題：如何計(jì)算p？計(jì)算第i個(gè)p，需要兩個(gè)i次的循環(huán)。第一個(gè)循環(huán)計(jì)算xi，第二個(gè)循環(huán)計(jì)算i！解決方案：從前一項(xiàng)計(jì)算后一項(xiàng)。如果p是第i項(xiàng)的值，則第i+1項(xiàng)的值為 p*x/(i+1) 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 13int main()int main()double ex, x, p;/exdouble ex, x, p;/ex存儲(chǔ)存儲(chǔ)e ex x的值，的值，p p保存當(dāng)前項(xiàng)的值保存當(dāng)前項(xiàng)的值 int i;int i; cout cout x; cin x; ex=0; p=1

9、; i=0; ex=0; p=1; i=0; while (p 1e-6) while (p 1e-6) ex += p; ex += p; +i; +i; p = p p = p * * x / i; x / i; cout e cout e的的 x x 次方等于次方等于： ex endl; ex endl; return 0;return 0;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 14重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 15v格式：格式： do

10、do 語句語句 while (while (表達(dá)式表達(dá)式) ) v執(zhí)行過程：先執(zhí)行循環(huán)體，然后判斷循環(huán)條件。如條執(zhí)行過程：先執(zhí)行循環(huán)體，然后判斷循環(huán)條件。如條件成立，繼續(xù)循環(huán)，直到條件為假件成立，繼續(xù)循環(huán)，直到條件為假v如將若干個(gè)輸入數(shù)相加，直到輸入如將若干個(gè)輸入數(shù)相加，直到輸入0 0為止。為止。 total = 0;total = 0; do cout do cout value ; cin value ; total += value; total += value; while (value != 0); while (value != 0);程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)

11、計(jì) - 16v計(jì)算方程計(jì)算方程f(x)在區(qū)間在區(qū)間a, b之間的根之間的根 。注意，。注意，f(a)和和f(b)必須異號(hào)必須異號(hào)v假設(shè)方程為假設(shè)方程為 ，區(qū)間為，區(qū)間為-1, 1 015223xxx程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 17v令令x1 = a, x2 = bv連接連接(x1, f(x1)和和(x2, f(x2)的弦交與的弦交與x軸的坐標(biāo)點(diǎn)可軸的坐標(biāo)點(diǎn)可用如下公式求出用如下公式求出 v若若f(x)與與f(x1)同符號(hào)，則方程的根在同符號(hào)，則方程的根在(x, x2)之間，將之間，將x作為新的作為新的x1。否則根在。否則根在(x1, x)之間，將之間，將x設(shè)為新的設(shè)為新

12、的x2。v重復(fù)步驟和，直到重復(fù)步驟和，直到f(x)小于某個(gè)指定的精度為小于某個(gè)指定的精度為止。此時(shí)的止。此時(shí)的x為方程為方程f(x)=0的根。的根。) 1()2() 1(*2)2(*1xfxfxfxxfxx程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 18int main()double x, x1 = -1, x2 = 1, fx1, fx2, fx;do fx1 = x1 * x1 * x1 + 2 * x1 * x1 + 5 * x1 -1;fx2 = x2 * x2 * x2 + 2 * x2 * x2 + 5 * x2 -1;x = (x1 * fx2 - x2 * fx1)

13、/ (fx2 - fx1);fx = x * x * x + 2 * x * x + 5 * x -1;if (fx * fx1 0) x1 = x; else x2 = x; while (fabs( fx ) 1e-7);cout 方程的根為：方程的根為： x endl; return 0;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 19重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 20v考慮一個(gè)讀入數(shù)據(jù)直到讀到標(biāo)志值的問題。考慮一個(gè)讀入數(shù)據(jù)直到讀到標(biāo)志值的問題

14、。如用自然語言描述，基于標(biāo)志的循環(huán)的結(jié)構(gòu)如用自然語言描述，基于標(biāo)志的循環(huán)的結(jié)構(gòu)由以下步驟組成：由以下步驟組成：讀入一個(gè)值讀入一個(gè)值如果讀入值與標(biāo)志值相等，則退出循環(huán)如果讀入值與標(biāo)志值相等，則退出循環(huán)執(zhí)行在讀入那個(gè)特定值情況下需要執(zhí)行的語句執(zhí)行在讀入那個(gè)特定值情況下需要執(zhí)行的語句v當(dāng)一個(gè)循環(huán)中有一些操作必須在條件測試之當(dāng)一個(gè)循環(huán)中有一些操作必須在條件測試之前執(zhí)行時(shí)，稱為循環(huán)的中途退出問題。前執(zhí)行時(shí)，稱為循環(huán)的中途退出問題。 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 21v由于循環(huán)語句是先判斷條件再?zèng)Q定是否執(zhí)行循環(huán)由于循環(huán)語句是先判斷條件再?zèng)Q定是否執(zhí)行循環(huán)體，循環(huán)的中途退出將使得循環(huán)體中

15、的某些語句體，循環(huán)的中途退出將使得循環(huán)體中的某些語句必須重復(fù)出現(xiàn)。必須重復(fù)出現(xiàn)。v基于標(biāo)志的循環(huán)結(jié)構(gòu)被改為：基于標(biāo)志的循環(huán)結(jié)構(gòu)被改為：讀入一個(gè)值讀入一個(gè)值While （讀入值與標(biāo)志值不相等）（讀入值與標(biāo)志值不相等） 執(zhí)行在讀入那個(gè)特定值情況下需要執(zhí)行的語句執(zhí)行在讀入那個(gè)特定值情況下需要執(zhí)行的語句 讀入一個(gè)值讀入一個(gè)值 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 22vbreak語句：跳出循環(huán)語句：跳出循環(huán)v上述問題可以用下列方案解決：上述問題可以用下列方案解決：while (true) 提示用戶并讀入數(shù)據(jù)提示用戶并讀入數(shù)據(jù) if (value=標(biāo)志標(biāo)志) break; 根據(jù)數(shù)據(jù)作出處理

16、根據(jù)數(shù)據(jù)作出處理 vcontinue語句：跳出當(dāng)前循環(huán)周期語句：跳出當(dāng)前循環(huán)周期程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 23重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 24v對(duì)所有可能的情況一種一種去嘗試，直對(duì)所有可能的情況一種一種去嘗試，直到找到正確的答案。到找到正確的答案。v枚舉法的實(shí)現(xiàn)基礎(chǔ)是循環(huán)。枚舉法的實(shí)現(xiàn)基礎(chǔ)是循環(huán)。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 25v用用50元錢買了三種水果。各種水果加起來一共元錢買了三種水果。各種水果加起來一

17、共100個(gè)。西個(gè)。西瓜瓜5元一個(gè)，蘋果元一個(gè)，蘋果1元一個(gè)，桔子元一個(gè)，桔子1元元3個(gè)，設(shè)計(jì)一程序輸個(gè)，設(shè)計(jì)一程序輸出每種水果各買了幾個(gè)出每種水果各買了幾個(gè) v它有兩個(gè)約束條件：它有兩個(gè)約束條件：第一是三種水果一共第一是三種水果一共100個(gè)；個(gè)；第二是三種水果一共花了第二是三種水果一共花了50元元v可以按一個(gè)約束條件列出所有可行的情況，然后對(duì)每個(gè)可以按一個(gè)約束條件列出所有可行的情況，然后對(duì)每個(gè)可能解檢查它是否滿足第二個(gè)約束條件可能解檢查它是否滿足第二個(gè)約束條件 。也可以用第二。也可以用第二個(gè)約束條件列出所有情況，然后對(duì)每個(gè)可能解檢查它是個(gè)約束條件列出所有情況，然后對(duì)每個(gè)可能解檢查它是否滿足第一

18、個(gè)約束條件否滿足第一個(gè)約束條件 。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 26#include using namespace std;int main() int mellon, apple, orange; /分別表示西瓜數(shù)、蘋果數(shù)和桔子數(shù)分別表示西瓜數(shù)、蘋果數(shù)和桔子數(shù) for (mellon=1; mellon10; +mellon) / 對(duì)每種可能的西瓜數(shù)對(duì)每種可能的西瓜數(shù) for ( apple=1; apple 50 - 5 * mellon; +apple) /當(dāng)西瓜數(shù)給定后可能的蘋果數(shù)當(dāng)西瓜數(shù)給定后可能的蘋果數(shù) orange = 3*(50-5*mellon-app

19、le); / 剩下的錢全買了桔子剩下的錢全買了桔子 if (mellon+apple+orange = 100) / 三種水果數(shù)之和是否為三種水果數(shù)之和是否為100 cout mellon: mellon ; cout apple: apple ; cout orange: orange endl; return 0; 程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 27Mellon：1 apple：18 orange：81Mellon：2 apple：11 orange：87Mellon：3 apple：4 orange：93程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 28上地理

20、課時(shí)，四個(gè)學(xué)生回答我國四大湖的大小時(shí)分別說：上地理課時(shí)，四個(gè)學(xué)生回答我國四大湖的大小時(shí)分別說： 甲：洞庭最大，洪澤最小，鄱陽第三甲：洞庭最大，洪澤最小，鄱陽第三 乙：洪澤最大，洞庭最小，鄱陽第二，太湖第三乙：洪澤最大，洞庭最小，鄱陽第二，太湖第三 丙：洪澤最小，洞庭第三丙：洪澤最小，洞庭第三 ?。痕蛾栕畲螅钚?，洪澤第二，洞庭第三?。痕蛾栕畲?，太湖最小，洪澤第二，洞庭第三對(duì)于每個(gè)湖的大小，每個(gè)人僅答對(duì)一個(gè)，設(shè)計(jì)一程序讓對(duì)于每個(gè)湖的大小，每個(gè)人僅答對(duì)一個(gè)，設(shè)計(jì)一程序讓計(jì)算機(jī)通過這些信息去判別四個(gè)湖的大小。計(jì)算機(jī)通過這些信息去判別四個(gè)湖的大小。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) -

21、 29v如果如果用用a,b,c,d分別表示四個(gè)湖的排序。分別表示四個(gè)湖的排序。a表示洞庭湖，表示洞庭湖，b表示洪澤湖，表示洪澤湖，c表示鄱陽湖，表示鄱陽湖，d表示太湖。我們可以表示太湖。我們可以假設(shè)：假設(shè)：洞庭最大，洪澤第二，鄱陽第三，太湖第四，洞庭最大，洪澤第二，鄱陽第三，太湖第四，然后檢查每位同學(xué)是否都講對(duì)了一個(gè)。如果不是，再然后檢查每位同學(xué)是否都講對(duì)了一個(gè)。如果不是，再嘗試下一種情況：洞庭最大，洪澤第二，鄱陽第四，嘗試下一種情況：洞庭最大，洪澤第二，鄱陽第四，太湖第三，再檢查每位同學(xué)是否都講對(duì)了一個(gè)。嘗試太湖第三，再檢查每位同學(xué)是否都講對(duì)了一個(gè)。嘗試所有可能的情況，直到滿足每位同學(xué)都講對(duì)

22、一個(gè)為止。所有可能的情況，直到滿足每位同學(xué)都講對(duì)一個(gè)為止。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 30v為了嘗試所有情況，我們需要假設(shè)洞庭為了嘗試所有情況，我們需要假設(shè)洞庭湖可能是最大，也可能是第二、第三或湖可能是最大，也可能是第二、第三或第四。因此，第四。因此，a的值可能從的值可能從1變到變到4。同。同樣，樣，b, c ,d的值也都可能從的值也都可能從1變到變到4。為。為此，我們需要一個(gè)控制結(jié)構(gòu)，使此，我們需要一個(gè)控制結(jié)構(gòu)，使a, b, c, d的值能自動(dòng)從的值能自動(dòng)從1變到變到4。這種結(jié)構(gòu)就是。這種結(jié)構(gòu)就是循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) -

23、31main() int a, b, c, d; for (a=1; a=4; +a) for (b=1; b=4; +b) if ( a = b) continue; else for (c=1; c=4; +c) if (c=a|c=b) continue; else d=10 a b - c; if (a=1)+(b=4)+(c=3)=1 &(b=1)+(a=4)+(c=2)+(d=3)=1 &(b=4)+(a=3)=1 &(c=1)+(d=4)+(b=2)+(a=3)=1) cout a b c d;問題：效率差解決方法：一旦找到答案就應(yīng)該結(jié)束程序設(shè)計(jì) cs.s

24、jtu 2011.9程序設(shè)計(jì) - 32main() int a, b, c, d; bool flag = false; for (a=1; a=4; +a) for (b=1; b=4; +b) if ( a = b) continue; else for (c=1; c=4; +c) if (c=a|c=b) continue; else d=10 a b - c; if (a=1)+(b=4)+(c=3)=1 &(b=1)+(a=4)+(c=2)+(d=3)=1 &(b=4)+(a=3)=1 &(c=1)+(d=4)+(b=2)+(a=3)=1) cout a b

25、 c d; flag = true; break; if (flag) break; if (flag) break;改進(jìn)版1：程序不夠簡練程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 33main() int a, b, c, d; bool flag = false; for (a=1; a=4 & !flag; +a) for (b=1; b=4 & !flag; +b) if ( a = b) continue; else for (c=1; c=4 ; +c) if (c=a|c=b) continue; else d=10 a b - c; if (a=1)+

26、(b=4)+(c=3)=1 &(b=1)+(a=4)+(c=2)+(d=3)=1 &(b=4)+(a=3)=1 &(c=1)+(d=4)+(b=2)+(a=3)=1) cout a b c d; flag = true; break; 改進(jìn)版2程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 34v解題思路：解題思路：讓第一個(gè)位置的值從讓第一個(gè)位置的值從A依次變到依次變到C讓第一個(gè)位置的值從讓第一個(gè)位置的值從A依次變到依次變到C讓第一個(gè)位置的值從讓第一個(gè)位置的值從A依次變到依次變到C注意三個(gè)位置的值不能相同注意三個(gè)位置的值不能相同v可以用一個(gè)三層的嵌套循環(huán)實(shí)現(xiàn)，循環(huán)變

27、量可以用一個(gè)三層的嵌套循環(huán)實(shí)現(xiàn)，循環(huán)變量是字符類型是字符類型程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 35int main() char c1, c2, c3; for (c1 = A; c1 = C; +c1) for (c2 = A; c2 = C; +c2) if (c1 = c2) continue; else for (c3 = A; c3 = C; +c3) if (c3 = a1 | c3 = c2) continue; else cout c1 c2 c3 endl;程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 36重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do

28、while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 37v在求解過程的每一步都選取一個(gè)局部最優(yōu)在求解過程的每一步都選取一個(gè)局部最優(yōu)的策略，把問題規(guī)模縮小，最后把每一步的策略，把問題規(guī)?？s小，最后把每一步的結(jié)果合并起來形成一個(gè)全局解。的結(jié)果合并起來形成一個(gè)全局解。v基本步驟：基本步驟：從某個(gè)初始解出發(fā)從某個(gè)初始解出發(fā)采用迭代的過程，當(dāng)可以向目標(biāo)前進(jìn)一步時(shí)，采用迭代的過程，當(dāng)可以向目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局最優(yōu)策略，得到一個(gè)部分解，縮小就根據(jù)局最優(yōu)策略，得到一個(gè)部分解，縮小問題規(guī)模。問題規(guī)模。將所有解綜合起來將所有解綜合起來程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 38v對(duì)于一種貨幣，有面值為對(duì)于一種貨幣，有面值為1分分, 2分分, 5分分和和1角的硬幣，最少需要多少個(gè)硬幣來角的硬幣，最少需要多少個(gè)硬幣來找出找出K分錢的零錢。分錢的零錢。程序設(shè)計(jì) cs.sjtu 2011.9程序設(shè)計(jì) - 39v不斷地使用面值最大的硬幣。如要找零不斷地使用面值最大的硬幣。如要找零的值