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

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

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

3、法的關(guān)系表達(dá)式,-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è)計(jì),關(guān)系表達(dá)式 邏輯表達(dá)式 if語(yǔ)句 switch語(yǔ)句,任意表達(dá)式,0，非0,假，真,0，1,LOGO,條件檢查與if語(yǔ)句,if語(yǔ)句的格式 if （條件測(cè)試） 語(yǔ)句 if （條件測(cè)試） 語(yǔ)句1 else 語(yǔ)句2 條件測(cè)試為true時(shí)所執(zhí)行的程序塊叫做then子句，條件為false時(shí)執(zhí)行的語(yǔ)句叫做else子句。 eg. if (grade = 60) cout

4、= 60) cout “passed”; else cout “failed”;,LOGO,條件語(yǔ)句使用注意,if （條件測(cè)試） 語(yǔ)句1 else 語(yǔ)句2 條件的結(jié)果值應(yīng)該是 true 或 false，它們是C+中bool類型的值 事實(shí)上，條件可為任意表達(dá)式，不一定是關(guān)系表達(dá)式。0 為false，非 0 為true。 合理的縮排，使程序結(jié)構(gòu)更加清晰,LOGO,分支程序的例子,判斷某一年是否為閏年 要求： 用戶輸入任意一個(gè)年份數(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,條件表達(dá)式,？：運(yùn)算符 ：?jiǎn)柼?hào)冒號(hào)運(yùn)算符 作用：更加簡(jiǎn)練的用來(lái)表達(dá)條件執(zhí)行的機(jī)制 形式 ： (條件) ? 表達(dá)式1 : 表達(dá)式2 執(zhí)行過(guò)程：首先計(jì)算條件值。如果條件結(jié)果為true，則計(jì)算表達(dá)式1的值，并將它作為整個(gè)表達(dá)式的值。如果條件結(jié)果為false，則整個(gè)表達(dá)式的值為表達(dá)式2的值。,LOGO,實(shí)例,例如將x和y中值較大的一個(gè)賦值給max，可以用下列語(yǔ)句： max = (x

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

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

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

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

10、換成5 級(jí)記分制。,switch(score) case score = 90: cout = 80: cout = 70: cout = 60: cout D; break; default: cout E; ,case后面必須是一個(gè)常量,LOGO,表達(dá)式=成績(jī)/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,計(jì)算機(jī)自動(dòng)出四則運(yùn)算計(jì)算題,生成題目 sw

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

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

13、de using namespace std; int main() int num1, num2, op, result1, result2; /num1,num2:操作數(shù)，op:運(yùn)算符，result1,result2: 結(jié)果 srand(time(NULL); /隨機(jī)數(shù)種子初始化 num1=rand() % 10; / 生成運(yùn)算數(shù)(0-9) num2=rand() % 10 ; /生成運(yùn)算數(shù)(0-9) op=rand() % 4; / 生成運(yùn)算符 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)負(fù)值 除法可能出現(xiàn)除0 結(jié)果太單調(diào),LOGO,小結(jié),本章主要介紹了計(jì)算機(jī)實(shí)現(xiàn)邏輯思維的機(jī)制。主要包括兩個(gè)

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

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

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

18、 執(zhí)行過(guò)程：先執(zhí)行表達(dá)式1，再執(zhí)行表達(dá)式2， ，再執(zhí)行表達(dá)式n，整個(gè)表達(dá)式的計(jì)算結(jié)果為最后一個(gè)表達(dá)式的值 逗號(hào)運(yùn)算符的優(yōu)先級(jí)是所有運(yùn)算符中最低的 如a的初值為0，則表達(dá)式 a += 1, a += 2, a += 3, a += 4, a += 5 的結(jié)果為 15,LOGO,有了逗號(hào)表達(dá)式，從1加到100的問(wèn)題就可以只用一個(gè)語(yǔ)句： 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、進(jìn)一步討論 續(xù),表達(dá)式2用來(lái)測(cè)試循環(huán)條件，也不一定是關(guān)系表達(dá)式。它可以是邏輯表達(dá)式，甚至可以是算術(shù)表達(dá)式。當(dāng)表達(dá)式2是算術(shù)表達(dá)式時(shí)，只要表達(dá)式的值為非0，就執(zhí)行循環(huán)體，表達(dá)式的值為0時(shí)退出循環(huán)。 如果表達(dá)式2省略，即不判斷循環(huán)條件，循環(huán)將無(wú)終止地進(jìn)行下去。 無(wú)終止的循環(huán)稱為“死循環(huán)” 最簡(jiǎn)單的死循環(huán)是 for (;); 要結(jié)束一個(gè)無(wú)限循環(huán)，必須從鍵盤上輸入特殊的命令以中斷程序執(zhí)行并強(qiáng)制退出,for（表達(dá)式1；表達(dá)式2；表達(dá)式3） for (i=1; i=100; +i),LOGO,for循環(huán)的進(jìn)一步討論 續(xù),表達(dá)式3也可以是任何表達(dá)式，一般為賦值表達(dá)式或逗號(hào)表達(dá)式。表達(dá)式3是在每個(gè)循環(huán)周期結(jié)束

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

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

22、內(nèi)層的for循環(huán)在外層循環(huán)的每一個(gè)周期中都將執(zhí)行它的所有的周期 每個(gè)for循環(huán)都要有一個(gè)自己的循環(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)語(yǔ)句,格式：while （條件表達(dá)式） 語(yǔ)句 執(zhí)行過(guò)程：先計(jì)算出條件表達(dá)式的值。如果是false，循環(huán)終止，并接著執(zhí)行在整個(gè)while循環(huán)之后的語(yǔ)句。如果是true，整個(gè)循環(huán)體將被執(zhí)行，而后又回到while語(yǔ)句的條件表達(dá)式行，再次對(duì)條件進(jìn)行檢查。 用途：用于循環(huán)次

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

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

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

26、(b)必須異號(hào) 假設(shè)方程為 ，區(qū)間為-1, 1,LOGO,計(jì)算方法,令x1 = a, x2 = b 連接(x1, f(x1)和(x2, f(x2)的弦交與x軸的坐標(biāo)點(diǎn)可用如下公式求出 若f(x)與f(x1)同符號(hào)，則方程的根在(x, x2)之間，將x作為新的x1。否則根在(x1, x)之間，將x設(shè)為新的x2。 重復(fù)步驟和，直到f(x)小于某個(gè)指定的精度為止。此時(shí)的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)的中途退出,考慮一個(gè)讀入數(shù)據(jù)直到讀到標(biāo)

28、志值的問(wèn)題。如用自然語(yǔ)言描述，基于標(biāo)志的循環(huán)的結(jié)構(gòu)由以下步驟組成： 讀入一個(gè)值 如果讀入值與標(biāo)志值相等，則退出循環(huán) 執(zhí)行在讀入那個(gè)特定值情況下需要執(zhí)行的語(yǔ)句 當(dāng)一個(gè)循環(huán)中有一些操作必須在條件測(cè)試之前執(zhí)行時(shí)，稱為中途退出問(wèn)題。,LOGO,解決方案,break語(yǔ)句：跳出循環(huán) 上述問(wèn)題可以用下列方案解決： while (true) 提示用戶并讀入數(shù)據(jù) if (value=標(biāo)志) break; 根據(jù)數(shù)據(jù)作出處理 next statement; continue語(yǔ)句：跳出當(dāng)前循環(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“ “; ,因?yàn)樯厦嫜h(huán)在i4時(shí)結(jié)束了所有循環(huán) 所以最后輸出1 2 3,因?yàn)樯厦嫜h(huán)在i4時(shí)結(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,枚舉法,對(duì)所有可能的情況一種一種去嘗試，直到找到正確的答案。 特點(diǎn)：將問(wèn)題的所有可能的答案一一列舉，然后根據(jù)條件判斷此答案是否合適，合適就保留，不合適就丟棄。 例如：找出1到100之間的

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

31、 int main() int mellon, apple, orange; /分別表示西瓜數(shù)、蘋果數(shù)和桔子數(shù) for (mellon=1; mellon10; +mellon) / 對(duì)每種可能的西瓜數(shù) for ( apple=1; apple 50 - 5 * mellon; +apple) /當(dāng)西瓜數(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,實(shí)例二:四大湖問(wèn)題,上地理課時(shí)，四個(gè)學(xué)生回答我國(guó)四大湖的大小時(shí)分別說(shuō)： 甲：洞庭最大，洪澤最小，鄱陽(yáng)第三 乙：洪澤最大，洞庭最小，鄱陽(yáng)第二，太湖第三 丙：洪澤最小，洞庭第三 丁：鄱陽(yáng)最大，太湖最小，洪澤第二，洞庭第三 對(duì)于每個(gè)湖的大小，每個(gè)人僅答對(duì)一個(gè)，設(shè)計(jì)一程序讓計(jì)算機(jī)通過(guò)這些信息去判別四個(gè)湖的大小。,LOGO,解題思路,如果用a,

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

34、OGO,四大湖排列問(wèn)題的解,int main() int a, b, c, d; for (a=1; a=4; +a) /洞庭湖的可能排列 for (b=1; b=4; +b) /洪澤湖的可能排列 if ( a = b) continue; /如果兩個(gè)相等，本循環(huán)結(jié)束，否則接著考慮鄱陽(yáng)湖和太湖 else for (c=1; c=4; +c) /鄱陽(yáng)湖的可能排列 if (c=a|c=b) continue; /如果兩個(gè)相等，本循環(huán)結(jié)束，否則接著考慮太湖 else d=10 a b - c; /太湖 if (a=1)+(b=4)+(c=3)=1 ,問(wèn)題：效率差 解決方法：一旦找到答案就應(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 ,改進(jìn)版1：,程序不夠簡(jiǎn)練,LOGO,int main() int a, b, c, d; bool flag = false; /是否已經(jīng)找到答案，初值為假 for (a=1; a=4 ,改進(jìn)版2,LOGO,

36、實(shí)例三：列出ABC三個(gè)字母的全排列,解題思路： 讓第一個(gè)位置的值從A依次變到C 讓第二個(gè)位置的值從A依次變到C 讓第三個(gè)位置的值從A依次變到C 注意三個(gè)位置的值不能相同 可以用一個(gè)三層的嵌套循環(huán)實(shí)現(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,貪婪法,用于所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列的局部最優(yōu)解得到。 在求解過(guò)程的每一步都選取一個(gè)局部最優(yōu)的策略，把問(wèn)題規(guī)?？s小，最后把每一步的結(jié)果合并起來(lái)形成一個(gè)全局解。 基本步驟： 從某個(gè)初始解出發(fā) 采用迭代的過(guò)程，當(dāng)可以向目標(biāo)前進(jìn)一步時(shí)，就根據(jù)局部最優(yōu)策略，得到一個(gè)部分解，縮小問(wèn)題規(guī)模。 將所有解綜合起來(lái),LOGO,貪婪法例子：硬幣找零問(wèn)題,對(duì)于一種貨幣，有面值為1分, 2分, 5分和1角的硬幣，最少需要多少個(gè)硬幣來(lái)找出k分錢的零錢。,LOGO,貪婪法解題思想,不

38、斷地使用面值最大的硬幣。如要找零的值小于最大的硬幣值，則嘗試第二大的硬幣。依此類推。 不斷嘗試的過(guò)程就是循環(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; /記錄硬幣個(gè)數(shù) cout money;,LOGO,/不斷嘗試每一種硬幣 while (money = ONEJIAO) onejiao+; money