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

1、程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 1重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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è)計 cs.sjtu 2011.9程序設(shè)計 - 3v作為計數(shù)循環(huán)，可以理解為作為計數(shù)循環(huán)，可以理解為for(for(循環(huán)變量賦初值；循環(huán)條件；循環(huán)變量增值循環(huán)變量賦初值；循環(huán)條件；循環(huán)變量增值) ) 符合循環(huán)條件時的執(zhí)行語句符合循環(huán)條件時的執(zhí)行語句v循環(huán)體所有語句的一次完全執(zhí)行稱為一個循循環(huán)體所有語句的一次完全執(zhí)行稱為一個循環(huán)周期環(huán)周期v循環(huán)體可以是復(fù)合語句或空語句循環(huán)體可以是復(fù)合語句或空語句程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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，整個表達(dá)式的計算，整個表達(dá)式的計算結(jié)果為最后一個表達(dá)式的值結(jié)果為最后一個表達(dá)式的值v逗號運(yùn)算符的優(yōu)先級是所有運(yùn)算符中最低的逗號運(yùn)算符的優(yōu)先級是所有運(yùn)算符中最低的 如如a的初值為的初值為0，則表達(dá)式，則表達(dá)式 a += 1, a += 2, a += 3, a += 4, a += 5的結(jié)果為的結(jié)果為 15 程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 5v有了逗號表達(dá)式，從有了逗號表達(dá)式，從1加到加到100的問題就的問題就可以只用一個語句：可以只用一個語句：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è)計 cs.sjtu 2011.9程序設(shè)計 - 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á)式時，只要表達(dá)式的值為非算術(shù)表達(dá)式時，只要表達(dá)式的值為非0，就執(zhí)行

5、，就執(zhí)行循環(huán)體，表達(dá)式的值為循環(huán)體，表達(dá)式的值為0時退出循環(huán)。時退出循環(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é)束一個無限循環(huán)，必須從鍵盤上輸入特殊的要結(jié)束一個無限循環(huán)，必須從鍵盤上輸入特殊的命令以中斷程序執(zhí)行并強(qiáng)制退出命令以中斷程序執(zhí)行并強(qiáng)制退出 程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 7v表達(dá)式表達(dá)式3也可以是任何表達(dá)式，一般為賦值表也可以是任何表達(dá)式，一般為賦值表達(dá)式或逗號表達(dá)式。表達(dá)

6、式達(dá)式或逗號表達(dá)式。表達(dá)式3是在每個循環(huán)周是在每個循環(huán)周期結(jié)束后對循環(huán)變量的修正。表達(dá)式期結(jié)束后對循環(huán)變量的修正。表達(dá)式3也可以也可以省略，此時做完循環(huán)體后直接執(zhí)行表達(dá)式省略，此時做完循環(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è)計 cs.sjtu 2011.9程序設(shè)計 - 8v求函數(shù)求函數(shù) 在區(qū)間在區(qū)間a, b之間的定積分之間的定積分v實(shí)現(xiàn)思想：函數(shù)與實(shí)現(xiàn)思想：函數(shù)與x軸圍成的區(qū)域的面積。定積分軸圍成的區(qū)域的面積

7、。定積分可以通過將這塊面積分解成一連串的小矩形，計可以通過將這塊面積分解成一連串的小矩形，計算各小矩形的面積的和而得到算各小矩形的面積的和而得到 15)(2xxxf15)(2xxxfab程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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; 計算新的計算新的p p； 問題：如何計算p？計算第i個p，需要兩個i次的循環(huán)。第一個循環(huán)計算xi，第二個循環(huán)計算i！解決方案：從前一項計算后一項。如果p是第i項的值，則第i+1項的值為 p*x/(i+1) 程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 13int main()int main()double ex, x, p;/exdouble ex, x, p;/ex存儲存儲e ex x的值，的值，p p保存當(dāng)前項的值保存當(dā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è)計 cs.sjtu 2011.9程序設(shè)計 - 14重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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如將若干個輸入數(shù)相加，直到輸入如將若干個輸入數(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è)計 cs.sjtu 2011.9程序設(shè)

11、計 - 16v計算方程計算方程f(x)在區(qū)間在區(qū)間a, b之間的根之間的根 。注意，。注意，f(a)和和f(b)必須異號必須異號v假設(shè)方程為假設(shè)方程為 ，區(qū)間為，區(qū)間為-1, 1 015223xxx程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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)同符號，則方程的根在同符號，則方程的根在(x, x2)之間，將之間，將x作為新的作為新的x1。否則根在。否則根在(x1, x)之間，將之間，將x設(shè)為新的設(shè)為新

12、的x2。v重復(fù)步驟和，直到重復(fù)步驟和，直到f(x)小于某個指定的精度為小于某個指定的精度為止。此時的止。此時的x為方程為方程f(x)=0的根。的根。) 1()2() 1(*2)2(*1xfxfxfxxfxx程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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è)計 cs.sjtu 2011.9程序設(shè)計 - 19重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 20v考慮一個讀入數(shù)據(jù)直到讀到標(biāo)志值的問題?？紤]一個讀入數(shù)據(jù)直到讀到標(biāo)志值的問題

14、。如用自然語言描述，基于標(biāo)志的循環(huán)的結(jié)構(gòu)如用自然語言描述，基于標(biāo)志的循環(huán)的結(jié)構(gòu)由以下步驟組成：由以下步驟組成：讀入一個值讀入一個值如果讀入值與標(biāo)志值相等，則退出循環(huán)如果讀入值與標(biāo)志值相等，則退出循環(huán)執(zhí)行在讀入那個特定值情況下需要執(zhí)行的語句執(zhí)行在讀入那個特定值情況下需要執(zhí)行的語句v當(dāng)一個循環(huán)中有一些操作必須在條件測試之當(dāng)一個循環(huán)中有一些操作必須在條件測試之前執(zhí)行時，稱為循環(huán)的中途退出問題。前執(zhí)行時，稱為循環(huán)的中途退出問題。 程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 21v由于循環(huán)語句是先判斷條件再決定是否執(zhí)行循環(huán)由于循環(huán)語句是先判斷條件再決定是否執(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)被改為：讀入一個值讀入一個值While （讀入值與標(biāo)志值不相等）（讀入值與標(biāo)志值不相等） 執(zhí)行在讀入那個特定值情況下需要執(zhí)行的語句執(zhí)行在讀入那個特定值情況下需要執(zhí)行的語句 讀入一個值讀入一個值 程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 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è)計 cs.sjtu 2011.9程序設(shè)計 - 23重復(fù)重復(fù)N次循環(huán)次循環(huán)While循環(huán)循環(huán)Do while循環(huán)循環(huán)循環(huán)的中途退出循環(huán)的中途退出枚舉法枚舉法貪婪法貪婪法程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 24v對所有可能的情況一種一種去嘗試，直對所有可能的情況一種一種去嘗試，直到找到正確的答案。到找到正確的答案。v枚舉法的實(shí)現(xiàn)基礎(chǔ)是循環(huán)。枚舉法的實(shí)現(xiàn)基礎(chǔ)是循環(huán)。程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 25v用用50元錢買了三種水果。各種水果加起來一共元錢買了三種水果。各種水果加起來一

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

18、個約束條件否滿足第一個約束條件 。程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 26#include using namespace std;int main() int mellon, apple, orange; /分別表示西瓜數(shù)、蘋果數(shù)和桔子數(shù)分別表示西瓜數(shù)、蘋果數(shù)和桔子數(shù) for (mellon=1; mellon10; +mellon) / 對每種可能的西瓜數(shù)對每種可能的西瓜數(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è)計 cs.sjtu 2011.9程序設(shè)計 - 27Mellon：1 apple：18 orange：81Mellon：2 apple：11 orange：87Mellon：3 apple：4 orange：93程序設(shè)計 cs.sjtu 2011.9程序設(shè)計 - 28上地理

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

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

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

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è)計 cs.s

24、jtu 2011.9程序設(shè)計 - 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è)計 cs.sjtu 2011.9程序設(shè)計 - 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è)計 cs.sjtu 2011.9程序設(shè)計 - 34v解題思路：解題思路：讓第一個位置的值從讓第一個位置的值從A依次變到依次變到C讓第一個位置的值從讓第一個位置的值從A依次變到依次變到C讓第一個位置的值從讓第一個位置的值從A依次變到依次變到C注意三個位置的值不能相同注意三個位置的值不能相同v可以用一個三層的嵌套循環(huán)實(shí)現(xiàn)，循環(huán)變

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