第3和4章控制結(jié)構(gòu).ppt

1、第三章 控制結(jié)構(gòu),LOGO,控制語句,一般，程序中的語句是按書寫的順序逐條執(zhí)行。這種執(zhí)行方式稱為順序執(zhí)行。但是，程序設(shè)計語言也允許程序員自己指定接下去要執(zhí)行的語句，該語句也許不是順序的下一條。這種執(zhí)行方式稱為控制轉(zhuǎn)移。 結(jié)構(gòu)化編程的3種控制結(jié)構(gòu) 1 順序結(jié)構(gòu) 2 選擇結(jié)構(gòu) 3 循環(huán)結(jié)構(gòu) C+標準文檔將其稱為：控制語句,LOGO,控制語句,選擇結(jié)構(gòu)（條件分支） if if else switch 循環(huán)和重復(fù) for 循環(huán): 確定的循環(huán)次數(shù)，循環(huán)計數(shù) while 循環(huán): 不確定的循環(huán)次數(shù) do while 循環(huán):至少執(zhí)行一次,LOGO,選擇結(jié)構(gòu),用法： if（表達式1） 語句1 else if（表

2、達式2） 語句2 else if（表達式3） 語句3 。 。 。 else if（表達式m） 語句m else 語句n,用法： if（表達式） 語句1 else 語句2,用法： if（表達式） 語句,LOGO,邏輯思維及分支程序設(shè)計,關(guān)系表達式 邏輯表達式 if 語句 switch語句,LOGO,關(guān)系表達式,關(guān)系表達式用來實現(xiàn)比較 關(guān)系運算符 , =, =, =, , != 優(yōu)先級：高于賦值運算符，低于算術(shù)運算符。 關(guān)系運算符內(nèi)部：=和 ！=較低 關(guān)系表達式 用關(guān)系運算符將二個表達式連接起來稱為關(guān)系表達式 關(guān)系表達式的結(jié)果是： true 或 false,eg. x y a b = c d 是合

3、法的關(guān)系表達式,-3 -2 -1 不合法,應(yīng)寫成：（-3 -2） (m=34) 執(zhí)行后m,n的值分別為多少？,0 10,eg. int m=5,n=10; (m=34) 執(zhí)行后m,n的值分別為多少？,1 0,LOGO,邏輯思維及分支程序設(shè)計,關(guān)系表達式 邏輯表達式 if語句 switch語句,任意表達式,0，非0,假，真,0，1,LOGO,條件檢查與if語句,if語句的格式 if （條件測試） 語句 if （條件測試） 語句1 else 語句2 條件測試為true時所執(zhí)行的程序塊叫做then子句，條件為false時執(zhí)行的語句叫做else子句。 eg. if (grade = 60) cout

4、= 60) cout “passed”; else cout “failed”;,LOGO,條件語句使用注意,if （條件測試） 語句1 else 語句2 條件的結(jié)果值應(yīng)該是 true 或 false，它們是C+中bool類型的值 事實上，條件可為任意表達式，不一定是關(guān)系表達式。0 為false，非 0 為true。 合理的縮排，使程序結(jié)構(gòu)更加清晰,LOGO,分支程序的例子,判斷某一年是否為閏年 要求： 用戶輸入任意一個年份數(shù) 檢查是否為閏年。 輸出結(jié)果,被4整除而不能被100整除或 被400整除,LOGO,判斷閏年的程序,#include using namespace std; int m

5、ain() int year; bool result; cout year; result = (year % 4 = 0 ,cout year (result ? “是閏年” : “不是閏年 ) endl;,LOGO,條件表達式,？：運算符 ：問號冒號運算符 作用：更加簡練的用來表達條件執(zhí)行的機制 形式 ： (條件) ? 表達式1 : 表達式2 執(zhí)行過程：首先計算條件值。如果條件結(jié)果為true，則計算表達式1的值，并將它作為整個表達式的值。如果條件結(jié)果為false，則整個表達式的值為表達式2的值。,LOGO,實例,例如將x和y中值較大的一個賦值給max，可以用下列語句： max = (x

6、y) ? x : y; ？：運算符用于輸出。 例如，想輸出一個布爾變量flag的值，如果直接用 cout flag; 那么當flag為“真”時，輸出為1；當flag為“假”時，輸出為0。 如果我們想讓flag為“真”時輸出true，為“假”時輸出false。 可以用if 語句 if (flag) cout “true”; else cout “false”; 如果用？：運算符只需要一行 cout ( flag ? true : flase ) endl;,計算表達式的值,表達式的值為真（非0）時，max=x; 表達式的值為假（0）時，max=y;,LOGO,if語句的嵌套,if 語句的then

7、子句或else子句是 if 語句時，稱為if 語句的嵌套 歧義性：if 語句可以沒有else子句，如 if (x =90) 語句1 else if (x=80) 語句2 else 語句3 else 語句4； 配對原則：每個else子句是和在它之前最近的一個沒有else子句的if語句配對。,LOGO,縮進對齊,可以清晰地表示出層次 ，便于程序員閱讀,if (x = 90) 語句1 else if (x=80) 語句2 else 語句3 else 語句4；,【x=50，x=95分別執(zhí)行哪個語句？】,X=100,X=90,X=80,語句1,語句3,語句4,語句2,Y,Y,Y,N,N,N,每個else

8、子句是和在它之前最近的一個沒有else子句的if語句配對。,if (x = 90) 語句1 else if (x=80) 語句2 else 語句3 else 語句4；,可以用把then子句和else子句括起來。注意的匹配,LOGO,邏輯思維及分支程序設(shè)計,關(guān)系表達式 邏輯表達式 if語句 switch語句,LOGO,switch語句,格式： switch （表達式） case 常量表達式1：語句1 case 常量表達式2：語句2 . . case 常量表達式n：語句n default：語句n+1 ,執(zhí)行過程： 當表達式值為常量表達式1時，執(zhí)行語句1到語句n+1； 當表達式值為常量表達式2時，執(zhí)

9、行語句2到語句n+1； 。 。 當表達式值為常量表達式n時，執(zhí)行語句n到語句n+1； 否則，執(zhí)行語句n+1,用于多分支的情況,LOGO,Break語句,作用：跳出當前的switch語句,switch （表達式） case 常量表達式1：語句1；break； case 常量表達式2：語句2 ；break； . . case 常量表達式n：語句n ；break； default：語句n+1 ,執(zhí)行過程： 當表達式值為常量表達式1時，執(zhí)行語句1； 當表達式值為常量表達式2時，執(zhí)行語句2； 。 。 當表達式值為常量表達式n時，執(zhí)行語句n； 否則，執(zhí)行語句n+1,LOGO,eg1. 按下表將百分制成績轉(zhuǎn)

10、換成5 級記分制。,switch(score) case score = 90: cout = 80: cout = 70: cout = 60: cout D; break; default: cout E; ,case后面必須是一個常量,LOGO,表達式=成績/10,switch(score / 10) case 10: case 9: cout A; break; case 8: cout B; break; case 7: cout C; break; case 6: cout D; break; default: cout E; ,LOGO,計算機自動出四則運算計算題,生成題目 sw

11、itch(題目類型) case 加法：顯示題目，輸入和的值，判斷正確與否 case 減法：顯示題目，輸入差的值，判斷正確與否 case 乘法：顯示題目，輸入積的值，判斷正確與否 case 除法：顯示題目，輸入商和余數(shù)的值，判斷正確與否 ,要求自動出0-10之間的四則運算題，并批改結(jié)果,LOGO,關(guān)鍵問題,如何讓程序每次執(zhí)行的時候都出不同的題目(不同的運算符、不同的數(shù)字)？ 隨機數(shù)生成器：能隨機生成0到RAND_MAX之間的整型數(shù) 將生成的隨機數(shù)映射到0-10之間：rand() % 11。 運算符的生成：用編碼0-3表示四個運算符。因此題目的生成就是生成0-3之間的隨機數(shù)： rand() % 4

12、。 要生成a,b之間的隨機數(shù)怎么寫？ a+rand()%(b-a+1);,LOGO,隨機數(shù)的種子,計算機產(chǎn)生的隨機數(shù)稱為偽隨機數(shù)，它是根據(jù)一個算法計算出來的。 系統(tǒng)為每個程序、每次執(zhí)行指定的隨機數(shù)的種子都是相同的，因此程序每次執(zhí)行生成的隨機數(shù)序列都是相同的。,LOGO,改變隨機數(shù)的種子,設(shè)置種子的函數(shù)srand ： srand （種子） 如何讓程序每次執(zhí)行時選擇的種子都不一樣呢：每次執(zhí)行時選擇的種子要不一樣 選擇系統(tǒng)時間為種子：time(NULL) 取當前的系統(tǒng)時間。,LOGO,/四則運算聯(lián)系程序 #include /包含偽隨機數(shù)生成函數(shù) #include /包含取系統(tǒng)時間的函數(shù) #inclu

13、de using namespace std; int main() int num1, num2, op, result1, result2; /num1,num2:操作數(shù)，op:運算符，result1,result2: 結(jié)果 srand(time(NULL); /隨機數(shù)種子初始化 num1=rand() % 10; / 生成運算數(shù)(0-9) num2=rand() % 10 ; /生成運算數(shù)(0-9) op=rand() % 4; / 生成運算符 0-+， 1- -， 2-*，3- /,LOGO,switch (op) case 0: cout result1; if (num1 + nu

14、m2 = result1) cout result1; if (num1 - num2 = result1) cout you are rightn; else cout you are wrongn; break;,LOGO,case 2: cout result1; if (num1 * num2 = result1) cout result1; cout result2; if (num1 / num2 = result1) ,LOGO,該程序的缺陷,每次執(zhí)行只能出一道題 減法可能出現(xiàn)負值 除法可能出現(xiàn)除0 結(jié)果太單調(diào),LOGO,小結(jié),本章主要介紹了計算機實現(xiàn)邏輯思維的機制。主要包括兩個

15、方面： 如何表示一個邏輯判斷 如何根據(jù)邏輯判斷的結(jié)果執(zhí)行不同的處理 邏輯判斷 關(guān)系表達式實現(xiàn) 邏輯表達式 根據(jù)邏輯判斷執(zhí)行不同的處理 if語句 switch語句,LOGO,控制結(jié)構(gòu),一般，程序中的語句是按書寫的順序逐條執(zhí)行。這種執(zhí)行方式稱為順序執(zhí)行。但是，程序設(shè)計語言也允許程序員自己指定接下去要執(zhí)行的語句，該語句也許不是順序的下一條。這種執(zhí)行方式稱為控制轉(zhuǎn)移。C+提供兩種控制轉(zhuǎn)移結(jié)構(gòu)： 分支程序設(shè)計 循環(huán)程序設(shè)計,LOGO,循環(huán)控制,重復(fù)n次循環(huán) while循環(huán) do while循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法,LOGO,重復(fù)n次操作,某一組語句要重復(fù)執(zhí)行n次 “重復(fù)n次”循環(huán)通常用 fo

16、r 語句實現(xiàn)，如將1到100這一百個數(shù)相加可寫為： s=0; for (i=1; i=100; +i) s+=i;,i 稱為循環(huán)變量,LOGO,for循環(huán)語句,格式： for（表達式1；表達式2；表達式3） 語句 作為計數(shù)器循環(huán)，可以理解為 for(循環(huán)變量賦初值；循環(huán)條件；循環(huán)變量增值) 符合循環(huán)條件時的執(zhí)行語句 循環(huán)體可以是復(fù)合語句或空語句 循環(huán)里所有語句的一次完全執(zhí)行稱為一個循環(huán)周期。,循環(huán)體,for (i=1; i=100; +i) S+=i,執(zhí)行過程： 1.執(zhí)行表達式1 2.執(zhí)行表達式2 3.如果表達式2的結(jié)果為“true”，則執(zhí)行循環(huán)體，接著執(zhí)行表達式3，然后回到2，否則for語句

17、執(zhí)行結(jié)束,LOGO,單語句和復(fù)合語句,單個分號組成的語句稱為單語句 用 括起來的一組語句稱為復(fù)合語句。在邏輯上看成一個語句。盡量縮格對齊。 復(fù)合語句可以放在任何單語句出現(xiàn)的地方 在復(fù)合語句中可以定義變量，但必須定義在最前面,LOGO,for循環(huán)的進一步討論,for循環(huán)的三個表達式可以是任意表達式 三個表達式都是可選的 如果循環(huán)不需要任何初始化工作，則表達式1可以缺省。如果循環(huán)前需要做多個初始化工作，可以將多個初始化工作組合成一個逗號表達式，作為表達式1。,for（表達式1；表達式2；表達式3） for (i=1; i=100; +i),LOGO,逗號表達式,格式：表達式1，表達式2，,表達式n

18、 執(zhí)行過程：先執(zhí)行表達式1，再執(zhí)行表達式2， ，再執(zhí)行表達式n，整個表達式的計算結(jié)果為最后一個表達式的值 逗號運算符的優(yōu)先級是所有運算符中最低的 如a的初值為0，則表達式 a += 1, a += 2, a += 3, a += 4, a += 5 的結(jié)果為 15,LOGO,有了逗號表達式，從1加到100的問題就可以只用一個語句： for (i=1, s=0; i=100; +i) s+=i; 或?qū)⑺械某跏蓟挤旁谘h(huán)外，即 i=1； s=0； for ( ； i=100; +i) s+=i; 建議還是用 s=0; for (i=1; i=100; +i) s+=i;,LOGO,for循環(huán)的

19、進一步討論 續(xù),表達式2用來測試循環(huán)條件，也不一定是關(guān)系表達式。它可以是邏輯表達式，甚至可以是算術(shù)表達式。當表達式2是算術(shù)表達式時，只要表達式的值為非0，就執(zhí)行循環(huán)體，表達式的值為0時退出循環(huán)。 如果表達式2省略，即不判斷循環(huán)條件，循環(huán)將無終止地進行下去。 無終止的循環(huán)稱為“死循環(huán)” 最簡單的死循環(huán)是 for (;); 要結(jié)束一個無限循環(huán)，必須從鍵盤上輸入特殊的命令以中斷程序執(zhí)行并強制退出,for（表達式1；表達式2；表達式3） for (i=1; i=100; +i),LOGO,for循環(huán)的進一步討論 續(xù),表達式3也可以是任何表達式，一般為賦值表達式或逗號表達式。表達式3是在每個循環(huán)周期結(jié)束

20、后對循環(huán)變量的修正。表達式3也可以省略，此時做完循環(huán)體后直接執(zhí)行表達式2。 如從1加到100，可以寫為 S=0; for (i=1; i=100; ) s+=i; i+; 或 s=0; for (i=1; i=100; s+=i, i+) ;,for（表達式1；表達式2；表達式3） for (i=1; i=100; +i),LOGO,for循環(huán)實例：打印水仙花數(shù),打印出所有的“水仙花數(shù)”，所謂“水仙花數(shù)”是指一個三位數(shù)，其各位數(shù)字立方和等于該數(shù)本身。 例如：370是一個“水仙花數(shù)”，因為370=3*3*37*7*70*0*0。,程序分析： (1) 循環(huán)變量的初始值 (2) 循環(huán)條件 (3) 利

21、用for循環(huán)控制這些數(shù)，每個數(shù)分解出個位，十位，百位。,LOGO,源代碼,#include using namespace std; int main() ,int i,j,k,n; /定義變量，i,j,k分別記錄百、十、個位數(shù)，n記錄循環(huán)變量 cout水仙花數(shù)是：endl;,for(n=100;n1000;n+) i=n/100; /分解出百位數(shù) j=n/10%10; /分解出10位數(shù) k=n%10; /分解出個位數(shù),if(n=i*i*i+j*j*j+k*k*k) /是否水仙花數(shù)？ coutnendl; ,return 0; ,LOGO,循環(huán)的嵌套,將一個for循環(huán)嵌入到另一個for循環(huán)中

22、內(nèi)層的for循環(huán)在外層循環(huán)的每一個周期中都將執(zhí)行它的所有的周期 每個for循環(huán)都要有一個自己的循環(huán)變量以避免循環(huán)變量間的互相干擾 熟悉書上例子P59：打印乘法表 思考：打印三角形的乘法表，怎么修改原程序？,LOGO,循環(huán)控制,重復(fù)n次循環(huán) while循環(huán) do while循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法,LOGO,while 循環(huán)語句,格式：while （條件表達式） 語句 執(zhí)行過程：先計算出條件表達式的值。如果是false，循環(huán)終止，并接著執(zhí)行在整個while循環(huán)之后的語句。如果是true，整個循環(huán)體將被執(zhí)行，而后又回到while語句的條件表達式行，再次對條件進行檢查。 用途：用于循環(huán)次

23、數(shù)不定的循環(huán)。循環(huán)是否結(jié)束取決于某一個變量的值（標記控制重復(fù)）。,LOGO,例.求 下面公式（ 參看教材）,時結(jié)束。,ex=0; /記錄 和 p = 1; /記錄加數(shù)項 while (p0.000001) 計算新的p； ex += p; ,問題： 如何計算p？計算第i個p，需要兩個i次的循環(huán) 解決方案： 從前一項計算后一項。 如果p是第i項的值， 則第i+1項的值為 p*x/(i+1),LOGO,int main() double ex, x, p;/ex存儲ex的值，p保存當前項的值 int i; /記錄項數(shù) cout x; ex=0; p=1; i=0; while (p1e-6) ex

24、+= p; /求和 p = p * x / i; /求下一項 +i; cout e的 x 次方等于： ex endl; return 0;,LOGO,補充練習(xí)：用while循環(huán)實現(xiàn)下面程序,求s=a+aa+aaa+aaaa+aa.a的值，其中a是一個數(shù)字。 例如2+22+222+2222+22222 此時共有5個數(shù)相加，幾個數(shù)相加由鍵盤控制。 程序分析：(1)用戶輸入兩個變量，a和n (2)關(guān)鍵是計算出每一項的值。 上傳至ftp:/,LOGO,循環(huán)控制,重復(fù)n次循環(huán) while循環(huán) do while循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法,LOGO,dowhile 循環(huán)語句,格式： do 語句 w

25、hile (表達式); 執(zhí)行過程：先執(zhí)行循環(huán)體，然后判斷循環(huán)條件。如條件成立，繼續(xù)循環(huán)，直到條件為假 如將若干個輸入數(shù)相加，直到輸入0為止。 total = 0; do cout value ; total += value; while (value != 0);,LOGO,while 與 dowhile的關(guān)系,while語句和do-while語句一般都可以相互改寫,而while是先判斷后執(zhí)行，如果條件不滿足，則一次循環(huán)體語句也不執(zhí)行。,do-while是先執(zhí)行后判斷，因此do-while至少要執(zhí)行一次循環(huán)體。,LOGO,編程實例,計算方程f(x)在區(qū)間a, b之間的根 。注意，f(a)和f

26、(b)必須異號 假設(shè)方程為 ，區(qū)間為-1, 1,LOGO,計算方法,令x1 = a, x2 = b 連接(x1, f(x1)和(x2, f(x2)的弦交與x軸的坐標點可用如下公式求出 若f(x)與f(x1)同符號，則方程的根在(x, x2)之間，將x作為新的x1。否則根在(x1, x)之間，將x設(shè)為新的x2。 重復(fù)步驟和，直到f(x)小于某個指定的精度為止。此時的x為方程f(x)=0的根。,LOGO,int main() double x, x1 = -1, x2 = 1, fx1, fx2, fx; do fx1 = x1 * x1 * x1 + 2 * x1 * x1 + 5 * x1 -

27、1; fx2 = x2 * x2 * x2 + 2 * x2 * x2 + 5 * x2 -1; x = (x1 * fx2 - x2 * fx1) / (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; ,LOGO,循環(huán)控制,重復(fù)n次循環(huán) while循環(huán) do while循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法,LOGO,循環(huán)的中途退出,考慮一個讀入數(shù)據(jù)直到讀到標

28、志值的問題。如用自然語言描述，基于標志的循環(huán)的結(jié)構(gòu)由以下步驟組成： 讀入一個值 如果讀入值與標志值相等，則退出循環(huán) 執(zhí)行在讀入那個特定值情況下需要執(zhí)行的語句 當一個循環(huán)中有一些操作必須在條件測試之前執(zhí)行時，稱為中途退出問題。,LOGO,解決方案,break語句：跳出循環(huán) 上述問題可以用下列方案解決： while (true) 提示用戶并讀入數(shù)據(jù) if (value=標志) break; 根據(jù)數(shù)據(jù)作出處理 next statement; continue語句：跳出當前循環(huán)周期,LOGO,循環(huán)中途退出的例子,void main() int i; for (i=1; i8; i+) if (i =

29、4) break;cout i“ “; coutendl; for (i=1; i8; i+) if (i = 4) continue; couti“ “; ,因為上面循環(huán)在i4時結(jié)束了所有循環(huán) 所以最后輸出1 2 3,因為上面循環(huán)在i4時結(jié)束了本次循環(huán)，未輸出4所以最后輸出1 2 3 5 6 7,LOGO,循環(huán)控制,重復(fù)n次循環(huán) while循環(huán) do while循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法,LOGO,枚舉法,對所有可能的情況一種一種去嘗試，直到找到正確的答案。 特點：將問題的所有可能的答案一一列舉，然后根據(jù)條件判斷此答案是否合適，合適就保留，不合適就丟棄。 例如：找出1到100之間的

30、素數(shù)。需要將1到100之間的所有整數(shù)進行判斷。 找水仙花數(shù)，需要將100到999的整型數(shù)全部進行判斷 枚舉法的實現(xiàn)基礎(chǔ)是循環(huán)。,LOGO,枚舉法實例一,用50元錢買了三種水果。各種水果加起來一共100個。西瓜5元一個，蘋果1元一個，桔子1元3個，設(shè)計一程序輸出每種水果各買了幾個 它有兩個約束條件： 第一是三種水果一共100個； 第二是三種水果一共花了50元 可以按一個約束條件列出所有可行的情況，然后對每個可能解檢查它是否滿足第二個約束條件 。也可以用第二個約束條件列出所有情況，然后對每個可能解檢查它是否滿足第一個約束條件 。,LOGO,#include using namespace std;

31、 int main() int mellon, apple, orange; /分別表示西瓜數(shù)、蘋果數(shù)和桔子數(shù) for (mellon=1; mellon10; +mellon) / 對每種可能的西瓜數(shù) for ( apple=1; apple 50 - 5 * mellon; +apple) /當西瓜數(shù)給定后可能的蘋果數(shù) orange = 3*(50-5*mellon-apple); / 剩下的錢全買了桔子 if (mellon+apple+orange = 100) / 三種水果數(shù)之和是否為100？ cout mellon: mellon ; cout apple: apple ; cou

32、t orange: orange endl; return 0; ,LOGO,執(zhí)行結(jié)果,Mellon：1 apple：18 orange：81 Mellon：2 apple：11 orange：87 Mellon：3 apple：4 orange：93,LOGO,實例二:四大湖問題,上地理課時，四個學(xué)生回答我國四大湖的大小時分別說： 甲：洞庭最大，洪澤最小，鄱陽第三 乙：洪澤最大，洞庭最小，鄱陽第二，太湖第三 丙：洪澤最小，洞庭第三 ?。痕蛾栕畲螅钚?，洪澤第二，洞庭第三 對于每個湖的大小，每個人僅答對一個，設(shè)計一程序讓計算機通過這些信息去判別四個湖的大小。,LOGO,解題思路,如果用a,

33、b,c,d分別表示四個湖的排序。a表示洞庭湖，b表示洪澤湖，c表示鄱陽湖，d表示太湖。 我們可以假設(shè)：1）洞庭最大，洪澤第二，鄱陽第三，太湖第四，然后檢查每位同學(xué)是否都講對了一個。 如果不是，再嘗試下一種情況：2）洞庭最大，洪澤第二，鄱陽第四，太湖第三，再檢查每位同學(xué)是否都講對了一個。 嘗試所有可能的情況，直到滿足每位同學(xué)都講對一個為止。,LOGO,為了嘗試所有情況，我們需要假設(shè)洞庭湖可能是最大，也可能是第二、第三或第四。 因此，a的值可能從1變到4。同樣，b, c ,d的值也都可能從1變到4。 為此，我們需要一個控制結(jié)構(gòu)，使a, b, c, d的值能自動從1變到4。這種結(jié)構(gòu)就是循環(huán)結(jié)構(gòu)。,L

34、OGO,四大湖排列問題的解,int main() int a, b, c, d; for (a=1; a=4; +a) /洞庭湖的可能排列 for (b=1; b=4; +b) /洪澤湖的可能排列 if ( a = b) continue; /如果兩個相等，本循環(huán)結(jié)束，否則接著考慮鄱陽湖和太湖 else for (c=1; c=4; +c) /鄱陽湖的可能排列 if (c=a|c=b) continue; /如果兩個相等，本循環(huán)結(jié)束，否則接著考慮太湖 else d=10 a b - c; /太湖 if (a=1)+(b=4)+(c=3)=1 ,問題：效率差 解決方法：一旦找到答案就應(yīng)該結(jié)束,L

35、OGO,main() 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 ,改進版1：,程序不夠簡練,LOGO,int main() int a, b, c, d; bool flag = false; /是否已經(jīng)找到答案，初值為假 for (a=1; a=4 ,改進版2,LOGO,

36、實例三：列出ABC三個字母的全排列,解題思路： 讓第一個位置的值從A依次變到C 讓第二個位置的值從A依次變到C 讓第三個位置的值從A依次變到C 注意三個位置的值不能相同 可以用一個三層的嵌套循環(huán)實現(xiàn)，循環(huán)變量是字符類型,LOGO,int 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

37、 endl; ,LOGO,循環(huán)控制,重復(fù)n次循環(huán) while循環(huán) do while循環(huán) 循環(huán)的中途退出 枚舉法 貪婪法,LOGO,貪婪法,用于所求問題的整體最優(yōu)解可以通過一系列的局部最優(yōu)解得到。 在求解過程的每一步都選取一個局部最優(yōu)的策略，把問題規(guī)模縮小，最后把每一步的結(jié)果合并起來形成一個全局解。 基本步驟： 從某個初始解出發(fā) 采用迭代的過程，當可以向目標前進一步時，就根據(jù)局部最優(yōu)策略，得到一個部分解，縮小問題規(guī)模。 將所有解綜合起來,LOGO,貪婪法例子：硬幣找零問題,對于一種貨幣，有面值為1分, 2分, 5分和1角的硬幣，最少需要多少個硬幣來找出k分錢的零錢。,LOGO,貪婪法解題思想,不

38、斷地使用面值最大的硬幣。如要找零的值小于最大的硬幣值，則嘗試第二大的硬幣。依此類推。 不斷嘗試的過程就是循環(huán),LOGO,#include using namespace std; #define ONEFEN 1 #define TWOFEN 2 #define FIVEFEN 5 #define ONEJIAO 10 int main() int money; int onefen = 0, twofen = 0, fivefen = 0, onejiao = 0; /記錄硬幣個數(shù) cout money;,LOGO,/不斷嘗試每一種硬幣 while (money = ONEJIAO) onejiao+; money