《C程序設(shè)計(jì)華中科技大學(xué)課件第二章.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《C程序設(shè)計(jì)華中科技大學(xué)課件第二章.ppt（106頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

C 程序設(shè)計(jì) 授課教師 李戰(zhàn)春18995621070lizhanchunwh 第二章基本控制結(jié)構(gòu)程序設(shè)計(jì) 結(jié)構(gòu)化程序設(shè)計(jì)的特點(diǎn)是任何程序都可由三種基本結(jié)構(gòu)及其組合來(lái)描述 本章將介紹C 分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的設(shè)計(jì)方法 教學(xué)目標(biāo) 編寫選擇和循環(huán)結(jié)構(gòu)的程序考核方式 要求基本 1 獨(dú)立編寫并運(yùn)行2 2 2 3 2 獨(dú)立編寫并運(yùn)行2 8 2 9 2 10 2 7 2 12較高要求 獨(dú)立編寫并運(yùn)行2 5 2 6 2 13 2 15 2 16 利用海倫公式計(jì)算三角形面積 輸入a 3 b 4 c 5后 結(jié)果是多少 輸入a 1 b 1 c 3呢 為什么 怎么辦 2 1算法的概念與表示方法 2 1 1算法的概念 2 1 3算法描述的三種基本結(jié)構(gòu) 2 1 2算法的表示 2 1 1算法的概念 2 1 3算法描述的三種基本結(jié)構(gòu) 3循環(huán)結(jié)構(gòu) 1順序結(jié)構(gòu) 2分支結(jié)構(gòu) 算法的基本結(jié)構(gòu) 對(duì)算法的理論研究和實(shí)踐表明 任何算法的描述都可以分解為三種基本結(jié)構(gòu)或它們的組合 這三種基本結(jié)構(gòu)是順序結(jié)構(gòu) 分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu) num1 15 2 1 3算法描述的三種基本結(jié)構(gòu) 1 順序結(jié)構(gòu) 例2 1 求兩數(shù)之和 顯示結(jié)果 35 num2 20 sum num1 num2 演示算法執(zhí)行過(guò)程 輸出sum 活動(dòng)圖 2 1 3算法描述的三種基本結(jié)構(gòu) 2 分支結(jié)構(gòu) 例2 2 輸入三個(gè)數(shù) 輸出其中的最大數(shù) x 7 y 12 z 10 if x y max x elsemax y if z max max z 輸出max 顯示結(jié)果 12 演示算法執(zhí)行過(guò)程 2 2 1if語(yǔ)句 if語(yǔ)句基本格式 1 if 表達(dá)式 語(yǔ)句1 2 if 表達(dá)式 語(yǔ)句1 else 語(yǔ)句2 例2 4 輸入一個(gè)年份 判斷是否閏年 例2 5 從鍵盤上輸入三個(gè)整數(shù) 輸出其中的最大數(shù) 2 2分支結(jié)構(gòu)程序設(shè)計(jì) if語(yǔ)句 例2 4 例2 4 輸入一個(gè)年份 判斷是否閏年 算法分析 假定年份為year 閏年的條件是 year 4 0 分析 讀入三個(gè)數(shù) 先求出兩個(gè)數(shù)中較大者 再將該大數(shù)與第三個(gè)數(shù)比較 求出最大數(shù) intmain inta b c max cout a b c cout b max a else max b if c max max c cout 最大數(shù)為 max endl return0 if語(yǔ)句 例2 5 例2 5 從鍵盤上輸入三個(gè)整數(shù) 輸出其中的最大數(shù) 邏輯運(yùn)算 邏輯表達(dá)式 邏輯運(yùn)算 用于判斷分析 運(yùn)算符包括關(guān)系和邏輯運(yùn)算符 關(guān)系運(yùn)算符 包括 大于 大于等于 小于 小于等于 等于 和 不等于 關(guān)系運(yùn)算符完成兩個(gè)操作數(shù)大小的比較 結(jié)果為邏輯值true 真 或false 假 邏輯值與整數(shù)的對(duì)應(yīng)關(guān)系是什么 邏輯值能參與運(yùn)算嗎 關(guān)系表達(dá)式 例如 a b c d 等同于 a b c d y a b 計(jì)算a b的值0或1賦給y a b c 等同于 a b c 先求a b的值 再將結(jié)果0或1與c比較大小 由關(guān)系運(yùn)算符連接的表達(dá)式 是一種簡(jiǎn)單的邏輯表達(dá)式 值為true或false 數(shù)學(xué)式a b c 對(duì)應(yīng)的關(guān)系表達(dá)式為什么 設(shè)有定義floata 3 2 intb 5 則 3 a b 結(jié)果是 其運(yùn)算過(guò)程如下 a 5 b 3 2 3 T 即1 T即1 邏輯運(yùn)算符 包括 和 語(yǔ)義見(jiàn)下表 由邏輯運(yùn)算符連接的表達(dá)式 其操作數(shù)和運(yùn)算結(jié)果均為邏輯量 操作數(shù)可以是表達(dá)式 只要其值是邏輯量 如關(guān)系表達(dá)式 由于邏輯值和整數(shù)之間的對(duì)應(yīng)關(guān)系 也允許整型和字符型操作數(shù)進(jìn)行邏輯運(yùn)算 21 0 邏輯與 21與0 結(jié)果 21 0 邏輯或 21或0 結(jié)果 21 邏輯非 21的非 結(jié)果 運(yùn)算結(jié)果同樣可以作為一個(gè)整數(shù)參與其他運(yùn)算 邏輯表達(dá)式 邏輯表達(dá)式計(jì)算時(shí) 邏輯非優(yōu)先級(jí)最高 關(guān)系運(yùn)算其次 邏輯與和邏輯或最低 已知 inta 10 b 20 c 30 floatx 1 8 y 2 4 ay ay a b c t1 1 t2 0 t4 0 t3 0 t5 b t6 1 得整個(gè)表達(dá)式的值為 1 嵌套if語(yǔ)句 if語(yǔ)句中 如果內(nèi)嵌語(yǔ)句又是if語(yǔ)句 嵌套有兩種形式 2 2 2if語(yǔ)句的嵌套 例2 6 用嵌套if語(yǔ)句完成 例2 5 的任務(wù) 方法1 采用if中嵌套形式intmain inta b c max cout a b c coutb if a c max a a b且a celse max c a b且ac max b acelse max c a b且b ccout 最大數(shù)max max return0 if語(yǔ)句 例2 6 例2 6 用嵌套if語(yǔ)句完成 例2 5 的任務(wù) 方法2 采用else中嵌套形式intmain inta b c max cout a b c cout b if語(yǔ)句 例2 6 例2 7 某商場(chǎng)購(gòu)物優(yōu)惠活動(dòng) 例2 8 求一元二次方程的根 配對(duì)關(guān)系實(shí)例 例2 7 某商場(chǎng)優(yōu)惠活動(dòng)規(guī)定 某種商品單價(jià)為80元 一次購(gòu)買5件以上 包含5件 10件以下 不包含10件 打9折 一次購(gòu)買10件以上 包含10件 打8折 設(shè)計(jì)程序根據(jù)客戶的購(gòu)買量計(jì)算總價(jià) 算法1 輸入購(gòu)買件數(shù)count 設(shè)置單價(jià)price 80 元 2 根據(jù)count值確定折扣率discount 3 實(shí)際售價(jià)amount price count discount 4 輸出amount的值 算法細(xì)化 2 1 if count 5 count 10 discount 0 8 if語(yǔ)句 例2 7 intmain floatprice discount amount 單價(jià) 折扣 總價(jià)intcount 購(gòu)買件數(shù)cout price cout count if count 5 discount 1 elseif count 10 discount 0 9 else discount 0 8 amount price count discount cout 單價(jià) price endl cout 購(gòu)買件數(shù) count t 折扣 discount endl cout 總價(jià) amount endl return0 if語(yǔ)句 例2 7 例2 8 求一元二次方程ax2 bx c 0的根 其中系數(shù)a a 0 b c的值由鍵盤輸入 分析 輸入系數(shù)a a 0 b c后 令delta b2 4ac 結(jié)果有三種情況 若delta 0 方程有兩個(gè)相同實(shí)根 若delta 0 方程有兩個(gè)不同實(shí)根 若delta 0 方程無(wú)實(shí)根 if語(yǔ)句 例2 8 include includeusingnamespacestd intmain floata b c floatdelta x1 x2 cout a b c cout a a t b b t c c endl delta b b 4 a c if語(yǔ)句 例2 8 if delta 0 cout0 delta sqrt delta x1 b delta 2 a x2 b delta 2 a cout 方程有兩個(gè)不同實(shí)根 cout x1 x1 t x2 x2 endl elsecout 方程無(wú)實(shí)根 endl delta 0return0 if語(yǔ)句 例2 8 2 2 3條件運(yùn)算符 三元運(yùn)算符條件運(yùn)算符 可以用來(lái)簡(jiǎn)化if語(yǔ)句表達(dá) 其構(gòu)成的表達(dá)式格式為 表達(dá)式1 表達(dá)式2 表達(dá)式3例如 inta 6 b 7 min a b a b min 6 includeusingnamespacestd intmain charch cout ch if ch A 改寫為條件表達(dá)式ch ch A 把輸入字符轉(zhuǎn)換為小寫字母 對(duì)輸入字符進(jìn)行判斷 如果是大寫字母 則轉(zhuǎn)換為小寫字母 否則 不轉(zhuǎn)換 2 2 4switch語(yǔ)句 開(kāi)關(guān)語(yǔ)句 switch語(yǔ)句 用來(lái)實(shí)現(xiàn)多選一 switch 表達(dá)式 case常量表達(dá)式 語(yǔ)句序列 break case常量表達(dá)式n 語(yǔ)句序列n break default 語(yǔ)句序列 條件表達(dá)式 整型字符型布爾型枚舉型 取值為常量的表達(dá)式 switch 表達(dá)式 case常量表達(dá)式1 語(yǔ)句1case常量表達(dá)式2 語(yǔ)句2 case常量表達(dá)式n 語(yǔ)句ndefault 語(yǔ)句n 1 注 表達(dá)式類型為非浮點(diǎn)型 各常量表達(dá)式類型要與之匹配 各常量表達(dá)式要求各不相等 語(yǔ)句標(biāo)號(hào) 2 2 4switch語(yǔ)句 根據(jù)一個(gè)整型表達(dá)式的值決定程序分支 執(zhí)行流程 2 2 4switch語(yǔ)句 includeusingnamespacestd intmain chargrade cout grade switch grade case a cout 85 100 n case b cout 70 84 n case c cout 60 69 n case d cout 60 n default cout error n return0 觀察不同輸入時(shí)的輸出結(jié)果 switch語(yǔ)句 例題根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù)段 includeusingnamespacestd intmain chargrade cout grade switch grade case a cout 85 100 n case b cout 70 84 n case c cout 60 69 n case d cout 60 n default cout error n return0 2 1 2switch語(yǔ)句 例題根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù)段 switch語(yǔ)句 includeusingnamespacestd intmain chargrade cout grade switch grade case a cout 85 100 n case b cout 70 84 n case c cout 60 69 n case d cout 60 n default cout error n return0 2 1 2switch語(yǔ)句 例題根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù)段 switch語(yǔ)句 例題根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù)段 includeusingnamespacestd intmain chargrade cout grade switch grade case a cout 85 100 n case b cout 70 84 n case c cout 60 69 n case d cout 60 n default cout error n return0 switch語(yǔ)句 includeintmain chargrade cout grade switch grade case a cout 85 100 n break case b cout 70 84 n break case c cout 60 69 n break case d cout 60 n break default cout error n return0 跳出switch語(yǔ)句 switch語(yǔ)句 例題根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù)段 例題根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù)段 includeintmain chargrade cout grade switch grade case a cout 85 100 n break case b cout 70 84 n break case c cout 60 69 n break case d cout 60 n break default cout error n return0 switch語(yǔ)句 討論 1 csae和default僅起語(yǔ)句標(biāo)號(hào)作用 不能控制程序流程2 一旦選中一個(gè)case分支后 將繼續(xù)往下順序執(zhí)行語(yǔ)句序列3 添加break語(yǔ)句可以跳出switch語(yǔ)句體 達(dá)到控制流程作用 根據(jù)以上特點(diǎn) 可以寫出多個(gè)case共執(zhí)行一個(gè)語(yǔ)句的形式 2 1 2switch語(yǔ)句 2 2 4switch語(yǔ)句 例根據(jù)考試成績(jī)的等級(jí)打印出百分制分?jǐn)?shù) 允許輸入大寫或小寫字母 includeintmain chargrade cout grade switch grade case a case A cout 85 100 n break case b case B cout 70 84 n break case c case C cout 60 69 n break case d case D cout 60 n break default cout error n retrun0 a 或 A 共同執(zhí)行一個(gè)語(yǔ)句 switch語(yǔ)句 if語(yǔ)句switch語(yǔ)句 形成分支控制流程 不形成程序控制流程 用于復(fù)雜條件判斷 表達(dá)式的值為數(shù)值集合時(shí)作多分支控制 可讀性較好 與if語(yǔ)句比較 2 2 4switch語(yǔ)句 例2 10 設(shè)計(jì)一個(gè)計(jì)算器程序 實(shí)現(xiàn)加 減 乘 除運(yùn)算 分析 讀入兩個(gè)操作數(shù)和運(yùn)算符 根據(jù)運(yùn)算符完成相應(yīng)運(yùn)算 includeusingnamespacestd intmain floatnum1 num2 charop cout num1 op num2 switch op case cout num1 op num2 num1 num2 endl break case cout num1 op num2 num1 num2 endl break case cout num1 op num2 num1 num2 endl break case cout num1 op num2 num1 num2 endl break default cout op 是無(wú)效運(yùn)算符 return0 循環(huán)結(jié)構(gòu) 例2 3 求4個(gè)整數(shù)的和 顯示結(jié)果 60 演示算法執(zhí)行過(guò)程 12 3 14 26 2 16 42 1 18 60 0 count 4 整數(shù)個(gè)數(shù)sum 0 累加和的初值while count 0 x 輸入一個(gè)整數(shù) sum sum x count count 1 輸出sum 循環(huán)控制語(yǔ)句是基本流程控制語(yǔ)句之一 C 提供三種循環(huán)語(yǔ)句 2 3 1while語(yǔ)句 2 3 4循環(huán)的嵌套 2 3 3for語(yǔ)句 2 3 2do while語(yǔ)句 2 3循環(huán)結(jié)構(gòu)程序設(shè)計(jì) 注意 1 循環(huán)開(kāi)始前對(duì)循環(huán)條件進(jìn)行初始化 2 在循環(huán)體語(yǔ)句中要包含修改循環(huán)條件的語(yǔ)句 否則循環(huán)將不能終止而陷入死循環(huán) 2 3 1while語(yǔ)句 while語(yǔ)句也稱為當(dāng)循環(huán) 語(yǔ)句格式為 while 表達(dá)式 循環(huán)體語(yǔ)句 2 3 2do while語(yǔ)句 do while語(yǔ)句稱為直到循環(huán) 格式為 do 循環(huán)體語(yǔ)句 while 表達(dá)式 2 3 3for語(yǔ)句 for循環(huán)語(yǔ)句的格式for 表達(dá)式1 表達(dá)式2 表達(dá)式3 循環(huán)體語(yǔ)句 關(guān)鍵字 初始表達(dá)式 循環(huán)控制邏輯表達(dá)式 循環(huán)后置表達(dá)式 for語(yǔ)句 while語(yǔ)句 do while語(yǔ)句比較 inti 1 sum 0 循環(huán)初始條件while i 4 sum i i 修改循環(huán)條件 inti 1 sum 0 循環(huán)初始條件do sum i i 修改循環(huán)條件 while i 4 inti sum 0 for i 1 i 4 i sum i 習(xí)慣上 表達(dá)式1 循環(huán)初始條件 表達(dá)式2 循環(huán)終止條件 表達(dá)式3 修改循環(huán)條件 includeusingnamespacestd intmain inti 1 sum 0 while i 100 sum sum i i cout sum sum endl return0 想一想 循環(huán)條件是什么 循環(huán)結(jié)束條件是什么 哪一個(gè)語(yǔ)句修改循環(huán)條件 一個(gè)簡(jiǎn)單的循環(huán)跟蹤 求 while語(yǔ)句 例如 用for語(yǔ)句的求和式的程序 includeusingnamespacestd intmain inti sum 0 for i 1 i 100 i sum i cout sum sum endl return0 includeusingnamespacestd intmain inti 1 sum 0 while i 100 sum sum i i cout sum sum endl return0 for循環(huán)語(yǔ)句 例2 14 運(yùn)行結(jié)果 01123581321345589144233377610987159725844181 例2 14 設(shè)計(jì)程序輸出Fibonacii數(shù)列的前20項(xiàng) 要求每行輸出5個(gè)數(shù)據(jù) 2 3 3for語(yǔ)句 Fibonacii數(shù)列定義如下 算法分析 除了第0項(xiàng)和第1項(xiàng)外 每一項(xiàng)都是由類似方法產(chǎn)生 即前兩項(xiàng)之和 所以求當(dāng)前項(xiàng)時(shí) 只需要記住前兩項(xiàng) 程序不需要為每一項(xiàng)設(shè)置專用變量 屬遞推算法 For循環(huán)語(yǔ)句 1 7數(shù)組與字符數(shù)組 數(shù)組定義 數(shù)組是有限個(gè)同類型元素的有序集合 這些元素有一個(gè)共同的名字 每個(gè)元素以其在數(shù)組中的位置區(qū)分 位置用下標(biāo)表示 數(shù)組下標(biāo)的個(gè)數(shù)稱作維數(shù) intm 5 定義數(shù)組m 其中有5個(gè)整數(shù) floatx 3 數(shù)組x中有3個(gè)實(shí)數(shù) 一維數(shù)組 一維數(shù)組的定義格式 存儲(chǔ)類型 數(shù)據(jù)類型數(shù)組名 常量 一維數(shù)組初始化 includeusingnamespacestd intmain intint arr 4 int arr 0 1 int arr 1 1 int arr 2 2 int arr 3 int arr 1 int arr 2 cout int arr 3 n return0 例1 2 使用數(shù)組的簡(jiǎn)單例子 Fibonacii數(shù)列定義如下 For循環(huán)語(yǔ)句 1 定義數(shù)組 2 使用數(shù)組元素循環(huán)求解 程序如下 intmain intfib 20 0 1 n for n 2 n 20 n fib n fib n 2 fib n 1 for n 0 n 20 n cout setw 5 fib n if n 5 4 cout endl return0 For循環(huán)語(yǔ)句 例2 22 輸入一個(gè)小于1的數(shù)x 求sinx的近似值 要求誤差小于0 0001 近似計(jì)算公式如下 應(yīng)用實(shí)例 item item x x 2 n 2 n 1 intmain constdoubleepsilon 0 0001 用epsilon保存誤差doublex sinx item intn 2 sign 1 sign保存符號(hào)cout x sinx x item x x x 6 第一項(xiàng)作為初值 第二項(xiàng)為誤差項(xiàng)while item epsilon sinx sinx item sign 將當(dāng)前項(xiàng)累加進(jìn)結(jié)果 注意符號(hào)作為因子item item x x 2 n 2 n 1 推算新的誤差項(xiàng)sign sign 注意符號(hào)的變換n cout sin x sinx endl return0 例2 15 輸入一個(gè)不超過(guò)9位的整數(shù) 將其反向后輸出 例如輸入247 變成742輸出 算法分析 1 將整數(shù)的各個(gè)數(shù)位逐個(gè)分開(kāi) 用一個(gè)數(shù)組保存各位的值 然后反向組成新的整數(shù) 2 將整數(shù)各位數(shù)字分開(kāi)的方法是 通過(guò)求余得到個(gè)位數(shù) 然后將整數(shù)縮小十倍 再求余 并重復(fù)上述過(guò)程 分別得到十位 百位 直到整數(shù)的值變成0為止 2 3 3for語(yǔ)句 數(shù)據(jù)處理 1 設(shè)置變量num表示輸入的整數(shù) 整型數(shù)組digit 9 用來(lái)存放num的各個(gè)位 變量i用來(lái)表示數(shù)組的當(dāng)前下標(biāo) 算法 1 輸入num 變量初始化 i 0 2 while num 0 num對(duì)10取余 得num的當(dāng)前個(gè)位數(shù)放入digit i num整除10 即去掉個(gè)位數(shù) 十位變個(gè)位 百位變十位 i 數(shù)組digit準(zhǔn)備記錄下一位 3 將數(shù)組元素按下標(biāo)從低到高的順序反向組合 For循環(huán)語(yǔ)句 程序如下 intmain inti num subscript intdigit 9 cout num cout0 digit subscript num 10 num num 10 subscript 修改下標(biāo) for i 0 i subscript i 整數(shù)的反向組合num num 10 digit i cout 反向后整數(shù)為 num endl return0 For循環(huán)語(yǔ)句 2 3 4循環(huán)的嵌套 嵌套循環(huán) 當(dāng)循環(huán)語(yǔ)句中的循環(huán)體中又有循環(huán)語(yǔ)句時(shí) 就構(gòu)成了嵌套循環(huán) 嵌套層次一般不超過(guò)3層 以保證可讀性 例2 16 打印九九表 打印格式為 123456789112243369 991827364554637281 2 3 4循環(huán)的嵌套 算法 1 輸出表頭 用一個(gè)循環(huán)語(yǔ)句即可 2 輸出表體 for i 1 i 10 i cout i 輸出行號(hào)輸出第i行數(shù)據(jù) Acout endl 準(zhǔn)備輸出下一行 3 A行細(xì)化 for j 1 j i j cout setw 4 i j 2 3 4循環(huán)的嵌套 intmain inti j cout setw 3 setw 4 for i 1 i 10 i cout setw 4 i 輸出表頭 乘數(shù) cout endl endl for i 1 i 10 i cout setw 3 i setw 4 輸出行號(hào) 被乘數(shù) for j 1 j i j cout setw 4 i j 輸出表中數(shù)據(jù) 乘積 cout endl 準(zhǔn)備輸出下一行 return0 循環(huán)嵌套 例2 16 打印九九表 循環(huán)嵌套 2 4轉(zhuǎn)向語(yǔ)句 break continuegotoreturn break continue break語(yǔ)句無(wú)條件地結(jié)束switch語(yǔ)句 或循環(huán)語(yǔ)句 轉(zhuǎn)向執(zhí)行語(yǔ)句塊的后續(xù)語(yǔ)句continue語(yǔ)句用于循環(huán)體中 終止當(dāng)前一次循環(huán) while E1 語(yǔ)句1if E2 break 語(yǔ)句2 while E1 語(yǔ)句1if E2 continue 語(yǔ)句2 break continue break與continue語(yǔ)句比較 break continue for I 1 I 100 I if I 3 0 continue I不是3的倍數(shù) 不輸出 繼續(xù)下一個(gè)I 輸出I的值 I是3的倍數(shù)才輸出 if I 3 0 輸出I的值 例 輸出1 100內(nèi)3的倍數(shù) 分析 設(shè)置整型變量I從1變化到100 依次測(cè)試I是否3的倍數(shù) 算法屬于窮舉法 本章重點(diǎn)例題或算法 分段函數(shù)用switch求分?jǐn)?shù)段1 2 n或1 2 n或X X N個(gè)數(shù)求最大值 最小值 平均值求素?cái)?shù)大小寫字母轉(zhuǎn)換求最大公約數(shù)或最小公倍數(shù) break continue 例2 18 給定正整數(shù)m 判定其是否為素?cái)?shù) 分析 如果m 2 m是素?cái)?shù)的條件是不能被2 3 m的平方根取整 整除 因此可以用2 3 k k為m的平方根取整 逐個(gè)去除m 如果被其中某個(gè)數(shù)整除了 則m不是素?cái)?shù) 否則是素?cái)?shù) 算法屬于窮舉法 intmain intm i k cout m if m 2 coutk cout m 是素?cái)?shù) endl 循環(huán)提前終止表示是非素?cái)?shù)elsecout m 不是素?cái)?shù) endl return0 break continue 2 6常用算法的應(yīng)用實(shí)例 例2 20 中國(guó)古代數(shù)學(xué)史上著名的 百雞問(wèn)題 例2 21 用歐基里德算法 也稱輾轉(zhuǎn)法 求兩個(gè)整數(shù)的最大公約數(shù) 例2 23 輸入一個(gè)8位二進(jìn)制數(shù) 將其轉(zhuǎn)換為十進(jìn)制數(shù)輸出 例2 22 輸入一個(gè)小于1的數(shù)x 求sinx的近似值 枚舉 文件 例2 19 求100之內(nèi)的所有素?cái)?shù) 并將這些素?cái)?shù)輸出 每行輸出2個(gè)數(shù)據(jù) 2 6常用算法的應(yīng)用實(shí)例 例2 19 直接法直接法是根據(jù)問(wèn)題給出的條件直接求解 例2 19 求100之內(nèi)的所有素?cái)?shù) 并將這些素?cái)?shù)輸出 每行輸出2個(gè)數(shù)據(jù) 分析算法一窮舉法 1 判斷一個(gè)數(shù)是否素?cái)?shù) 方法窮舉法 2 100之內(nèi)的所有素?cái)?shù) 方法 一個(gè)個(gè)試 綜上所述 得到一個(gè)循環(huán)嵌套的算法 for m 2 m 100 m 窮舉法if m是素?cái)?shù) 按要求的格式輸出m k sqrt m for i 2 ik m是素?cái)?shù) 剛才的for不是由break結(jié)束的 2 枚舉法枚舉法也稱窮舉法 基本思想是 在有限范圍內(nèi)列舉所有可能的結(jié)果 找出其中符合要求的解 枚舉法適合求解的問(wèn)題是 可能的答案是有限個(gè)且答案是可知的 但又難以用解析法描述 這種算法通常用循環(huán)結(jié)構(gòu)來(lái)完成 例2 20 中國(guó)古代數(shù)學(xué)史上著名的 百雞問(wèn)題 雞翁一 值錢五 雞母一 值錢三 雞雛三 值錢一 百錢買百雞 問(wèn)雞翁 母 雛各幾何 分析 設(shè)雞翁 母 雛分別為i j k 根據(jù)題意可得 i 5 j 3 k 3 100 i j k 100 兩個(gè)方程無(wú)法解出三個(gè)變量 只能將各種可能的取值代入 其中能滿足兩個(gè)方程的就是所需的解 因此這是枚舉算法 也叫窮舉法 的應(yīng)用 i j k可能的取值有哪些 分析可知 百錢最多可買雞翁20 雞母33 雞雛300 算法 for i 0 i 20 i for j 0 j 33 j for k 0 k 300 k if i j k 100 這個(gè)算法使用三重循環(huán) 執(zhí)行時(shí)間函數(shù)是立方階 循環(huán)體將執(zhí)行20 33 300 198000次 我們希望在算法上改進(jìn)一下 如能減少一重循環(huán) 將大大縮短運(yùn)行時(shí)間 2 6常用算法的應(yīng)用實(shí)例 例2 20 實(shí)際上 當(dāng)i j確定時(shí) k就可由題目要求確定為100 i j 因此實(shí)際上只要用i j去測(cè)試 用錢數(shù)檢測(cè)就可以了 循環(huán)體將執(zhí)行 20 33 660次 算法改進(jìn)為 for i 0 i 20 for j 0 j 33 if 5 i 3 j 100 i j 3 100 cout i j k 2 6常用算法的應(yīng)用實(shí)例 例2 20 include includeusingnamespacestd intmain inti j k cout 公雞母雞小雞 endl for i 0 i 20 i for j 0 j 33 j k 100 i j if 5 i 3 j k 3 100 2 6常用算法的應(yīng)用實(shí)例 例2 20 注意 窮舉法采用循環(huán) 須剔除的情況 應(yīng)在循環(huán)體內(nèi)用用條件語(yǔ)句實(shí)現(xiàn) 不可放在循環(huán)條件中 請(qǐng)考慮為什么 本例是選合條件的 如去除不合條件用continue語(yǔ)句 改改看 程序運(yùn)行結(jié)果 公雞母雞小雞02575418788118112484 2 6常用算法的應(yīng)用實(shí)例 例2 20 2 6常用算法的應(yīng)用實(shí)例 例2 21 3 遞推法 遞推算法是通過(guò)問(wèn)題的一個(gè)或多個(gè)已知解 用同樣的方法逐個(gè)推算出其他解 如數(shù)列問(wèn)題 近似計(jì)算問(wèn)題等 通常也要借助于循環(huán)結(jié)構(gòu)完成 例2 21 用歐基里德算法 也稱輾轉(zhuǎn)法 求兩個(gè)整數(shù)的最大公約數(shù) 分析 假定兩個(gè)整數(shù)分別為num1和num2 最大公約數(shù)應(yīng)當(dāng)是不超過(guò)其中較小數(shù)的一個(gè)整數(shù) 輾轉(zhuǎn)法 用num1除以num2 求出余數(shù)resd 如果resd 0 則當(dāng)前num2就是最大公約數(shù) 如果resd 0 令num1 num2 num2 resd 重復(fù)以上過(guò)程 直到resd 0為止 1 設(shè)置兩個(gè)整型變量num1和num2代表兩個(gè)數(shù) 輸入num1 num2 2 輾轉(zhuǎn)法 2 1 使num1 num2 2 2 2 2 1 設(shè)置變量resd num1 num2 包含了步驟2 12 2 2 if resd 0 當(dāng)前num2就是最大公約數(shù) else num1 num2 num2 resd 重復(fù)2 2 1和2 2 2 直到resd 0為止 步驟2輾轉(zhuǎn)法可用以下程序段表示 do resd num1 num2 if resd 0 當(dāng)前num2就是最大公約數(shù) else num1 num2 num2 resd while resd 0 3 輸出當(dāng)前的num2 intmain intnum1 num2 resd cout num1 num2 cout num1 和 num2 的最大公約數(shù)為 do resd num1 num2 if resd 0 break num1 num2 num2 resd while resd 0 cout num2 endl return0 例2 22 輸入一個(gè)小于1的數(shù)x 求sinx的近似值 要求誤差小于0 0001 近似計(jì)算公式如下 分析 這個(gè)近似計(jì)算可以看作一個(gè)累加過(guò)程 關(guān)鍵在于累加項(xiàng)數(shù)的確定 該求近似值的奇次多項(xiàng)式各項(xiàng)順序改變符號(hào) 若取前n項(xiàng)累加和作為sin x 的近似值 則第n 1項(xiàng)的絕對(duì)值就是誤差限 因此可以這樣考慮 若公式中第一項(xiàng)作為累加和的初值 則第二項(xiàng)就是誤差 如果誤差不滿足要求 則將該項(xiàng)累加到累加和上 進(jìn)而用該項(xiàng)推出第三項(xiàng) 第三項(xiàng)又是新的累加和的誤差 經(jīng)過(guò)這樣累加 遞推 直至滿足要求為止 如果用item保存第n項(xiàng) 則推出第n 1項(xiàng)的方法為 item item x x 2 n 2 n 1 2 6常用算法的應(yīng)用實(shí)例 例2 22 intmain constdoubleepsilon 0 0001 用epsilon保存誤差doublex sinx item intn 2 sign 1 sign保存符號(hào)cout x sinx x item x x x 6 第一項(xiàng)作為初值 第二項(xiàng)為誤差項(xiàng)while item epsilon sinx sinx item sign 將當(dāng)前項(xiàng)累加進(jìn)結(jié)果 注意符號(hào)作為因子item item x x 2 n 2 n 1 推算新的誤差項(xiàng)sign sign 注意符號(hào)的變換n cout sin x sinx endl return0 2 6常用算法的應(yīng)用實(shí)例 例2 23 例2 23 輸入一個(gè)8位二進(jìn)制數(shù) 將其轉(zhuǎn)換為十進(jìn)制數(shù)輸出 分析 二進(jìn)制轉(zhuǎn)換為十進(jìn)制只要將每位二進(jìn)制數(shù)乘以該位的權(quán)然后相加 實(shí)際上屬于多項(xiàng)式求和問(wèn)題 對(duì)于本例 x 2 多項(xiàng)式的系數(shù)ai即為二進(jìn)制數(shù)的各個(gè)位 可以用數(shù)組保存 如果直接求冪再求和 需要做 n n 1 2 次乘法 現(xiàn)將多項(xiàng)式作如下變形 就變成一個(gè)十分簡(jiǎn)單的計(jì)算 僅做了n次乘法 算法 1 用數(shù)字串存二進(jìn)制數(shù) 數(shù)組bin 8 用來(lái)放各個(gè)二進(jìn)制位 考慮為什么 2 整型變量dec 0 x 2 初始化2 for i 7 i 0 i 系數(shù)從an到a0依次投入運(yùn)算dec dec x bin i 0 bin i 0 數(shù)字字符轉(zhuǎn)換為數(shù)字 2 6常用算法的應(yīng)用實(shí)例 例2 23 程序 constintn 8 intmain charbin n intx 2 a dec i cout 0 i cin bin i 先輸入的是高位dec 0 for i n 1 i 0 i a bin i 0 數(shù)字字符轉(zhuǎn)換為數(shù)字dec dec x a cout 0 i cout bin i cout 的值為 dec endl return0 2 7枚舉類型 2 7 1枚舉類型的定義 2 7 2枚舉變量的使用 枚舉類型 enumerate 是c 中的一種派生數(shù)據(jù)類型 它是用戶定義的若干枚舉常量的集合 枚舉類型的變量 只能取枚舉常量表中所列的值 定義枚舉類型的主要目的是增加程序的可讀性 2 7 1枚舉類型的定義 枚舉類型定義 enum 關(guān)鍵字enum指明其后的標(biāo)識(shí)符是一個(gè)類型的名字 枚舉常量表中列出該類型的所有取值 各枚舉常量之間以 間隔 例 enumcolor set1 RED BLUE WHITE BLACK enumweek Sun Mon Tue Wed Thu Fri Sat 枚舉常量 或稱枚舉成員 是以標(biāo)識(shí)符形式表示的整型量 非法定義實(shí)例 enumletter set a d F s T 枚舉常量只能是標(biāo)識(shí)符enumyear set 2000 2001 2002 2003 2004 2005 改為y2000等則正確 2 7 1枚舉類型的定義 枚舉常量 枚舉常量代表該枚舉類型的變量可能取的值 編譯系統(tǒng)為每個(gè)枚舉常量指定一個(gè)整數(shù)值 缺省狀態(tài)下 這個(gè)整數(shù)就是所列舉元素的序號(hào) 序號(hào)從0開(kāi)始 如上例中RED BLUE WHITE BLACK的值分別為0 1 2 3 用戶也可以在類型定義時(shí)為部分或全部枚舉常量指定整數(shù)值 在第一個(gè)指定值之前的枚舉常量仍按缺省方式取值 而指定值之后的枚舉常量按依次加1的原則取值 各枚舉常量的值可以重復(fù) 但各枚舉常量標(biāo)識(shí)符必須不同 例 enumfruit set apple orange banana 1 peach grape enumweek Sun 7 Mon 1 Tue Wed Thu Fri Sat 枚舉常量apple orange banana peach grape的值分別為0 1 1 2 3 枚舉常量Sun Mon Tue Wed Thu Fri Sat的值分別為7 1 2 3 4 5 6 2 7 1枚舉類型的定義 枚舉型變量定義 定義枚舉類型之后 就可以定義枚舉類型的變量 亦可類型與變量同時(shí)定義 甚至類型名可省 color set1color1 color2 enum Sun Mon Tue Wed Thu Fri Sat weekday1 weekday2 枚舉變量的取值范圍就是整型數(shù)的一個(gè)子集 枚舉變量占用內(nèi)存的大小與整型數(shù)相同 2 7 2枚舉類型的變量的使用 枚舉類型應(yīng)用要點(diǎn) 1 賦值包括將枚舉常量值賦給枚舉變量和兩個(gè)同類型變量之間賦值 不能直接將整型量賦給枚舉變量 兩個(gè)不同類型的枚舉變量之間也不能相互賦值 例如 enumcolor set2 GREEN RED YELLOW WHITE color set2color3 color4 color3 RED 合法color4 color3 合法 color4的值為REDcolor1 1 非法 不能直接將整性常量賦給枚舉變量color2 color3 非法 color2類型是color set1 color3類型是color set2 不能相互賦值 2 7 2枚舉類型的變量的使用 枚舉類型應(yīng)用要點(diǎn) 2 由于枚舉常量本身是一個(gè)整數(shù)值 因此也允許將一個(gè)枚舉量賦給整型變量 但不允許將一個(gè)整型變量賦給枚舉量 即使整型變量取值合適 也必須將整型變量強(qiáng)制轉(zhuǎn)換為枚舉型 例如 inti j i color3 合法 i的值為1j GREEN 合法 j的值為0color3 i 非法3 關(guān)系運(yùn)算可以是同一枚舉類型的兩個(gè)枚舉變量之間或一個(gè)枚舉變量和一個(gè)枚舉常量之間 用它們所取的值 序號(hào) 比較 例如 if color3 color4 cout 相等 if color3 WHITE cout notwhite 4 枚舉變量不能直接輸入 可以直接輸出 但輸出的是變量的整數(shù)值 例如 cin color1 非法cout color3 合法 輸出的是2從程序的合法性和可讀性出發(fā) 枚舉變量的輸入輸出一般都采用switch語(yǔ)句將其轉(zhuǎn)換為字符或字符串 同時(shí) 枚舉類型數(shù)據(jù)的其他處理也往往應(yīng)用switch語(yǔ)句 2 7 2枚舉類型的變量的使用 例2 24 口袋中有紅 黃 藍(lán) 白 黑五種顏色的球若干個(gè) 每次從口袋中取三個(gè)不同顏色的球 統(tǒng)計(jì)并輸出所有的取法 2 8輸入輸出文件簡(jiǎn)介 如果希望程序的運(yùn)行結(jié)果能夠永久保留下來(lái) 供隨時(shí)查閱或取用 則需要將其保存在文件中 文件包括文本文件和二進(jìn)制文件 本小節(jié)只討論文本文件的基本操作和簡(jiǎn)單應(yīng)用 文本文件由字符序列組成 也稱ASCII碼文件 在文本文件中存取的最小信息單位為字符 character 兩個(gè)概念 內(nèi)部文件和外部文件 通常所謂的文件是指磁盤文件 就是在 我的電腦 的目錄中見(jiàn)到的文件 這里稱為外部文件 而在程序中運(yùn)行的文件 稱為內(nèi)部文件 文件流對(duì)象 程序中操作的是內(nèi)部文件 最后保存的是外部文件 算法 枚舉 文件 2 8輸入輸出文件簡(jiǎn)介 使用文件的步驟如下 說(shuō)明一個(gè)文件流對(duì)象 內(nèi)部文件 文件流類型ifstream支持從輸入文件提取數(shù)據(jù)的操作 而文件流類型ofstream完成數(shù)據(jù)寫入輸出文件的各種操作 ifstreamifile 定義輸入文件 ifile為文件名 可用任意標(biāo)識(shí)符ofstreamofile 定義輸出文件 ofile為文件名 可用任意標(biāo)識(shí)符 2 打開(kāi)文件 ifile open d my in file txt ofile open d my out file txt 引號(hào)中的 d my in file txt 和 d my out file txt 為磁盤文件路徑名 這樣在文件流對(duì)象和磁盤文件名之間建立了聯(lián)系 3 對(duì)文件進(jìn)行讀寫操作 最常見(jiàn)的文件讀寫是順序的 所謂 順序 指的是從文件頭開(kāi)始進(jìn)行讀寫 順序讀寫可用C 的提取運(yùn)算符 和插入運(yùn)算符 進(jìn)行 也可以用讀字符的get 和讀字符串的getling 等函數(shù) 讀寫是在文件緩沖區(qū)中進(jìn)行 4 關(guān)閉文件 當(dāng)打開(kāi)一個(gè)文件進(jìn)行讀寫后 應(yīng)該顯式地關(guān)閉該文件 與打開(kāi)文件相對(duì)應(yīng) ifile close ofile close 關(guān)閉文件時(shí) 系統(tǒng)把與該文件相關(guān)聯(lián)的文件緩沖區(qū)中的數(shù)據(jù)寫到磁盤文件中 保證文件的完整 同時(shí)把磁盤文件名與文件流對(duì)象之間的關(guān)聯(lián)斷開(kāi) 可防止誤操作修改了磁盤文件 例2 25 將百雞問(wèn)題計(jì)算結(jié)果存入文件 例2 26 讀出存放百雞問(wèn)題計(jì)算結(jié)果的文件 例2 24 口袋中有紅 黃 藍(lán) 白 黑五種顏色的球若干個(gè) 每次從口袋中取三個(gè)不同顏色的球 統(tǒng)計(jì)并輸出所有的取法 分析 每個(gè)球的顏色都是這五種顏色之一 因此可以使用枚舉類型來(lái)定義球的顏色 假設(shè)所取三個(gè)球的顏色分別為i j k 每個(gè)量都有5種取值 其中i j k就是滿足要求的取法 因此用枚舉算法 窮舉法 可以解決 2 7 2枚舉類型的變量的使用 例2 24 算法 1 定義枚舉類型及相應(yīng)變量 enumcolor red yellow blue white black colori j k col 2 for i red i black i for j red j black j if i j 前兩個(gè)球顏色不同for k red k black k if k i k j 第三個(gè)球不同于前兩個(gè) 滿足要求 找到一種取法3 輸出該取法 注意枚舉量的輸出方法 2 7 2枚舉類型的變量的使用 例2 24 intmain enumcolor set red yellow blue white black color setcolor inti j k counter 0 loop for i red i black i for j red j black j if i j 前兩個(gè)球顏色不同for k red k black k if k i 下面輸出每種取法 一行為一種取法的三個(gè)顏色for loop 1 loop 3 loop switch loop case1 color color set i break 第一個(gè)是icase2 color color set j break 第二個(gè)是jcase3 color color set k break 第三個(gè)是k 注意類型轉(zhuǎn)換不可少switch color casered cout setw 15 red break caseyellow cout setw 15 yellow break caseblue cout setw 15 blue break casewhite cout setw 15 white break caseblack cout setw 15 black break for loopcout endl 輸出一種取法后換行 for k for jcout 共有 counter 種取法 endl return0 運(yùn)行結(jié)果 redyellowblueredyellowwhiteredyellowblackredblueyellow 共有60種取法 intmain inti j k ofstreamofile 定義輸出文件ofile open d myfile txt 作為輸出文件打開(kāi)ofile 公雞母雞小雞 endl for i 0 i 20 i for j 0 j 33 j k 100 i j if 5 i 3 j k 3 100 例2 25 將百雞問(wèn)題計(jì)算結(jié)果存入文件 intmain chara 28 ifstreamifile 定義輸入文件ifile open d myfile txt 作為輸入文件打開(kāi)inti 0 j k ifile getline a 28 讀標(biāo)題 不可用 它不能讀白字符cout i j k 由文件讀入數(shù)據(jù)if ifile eof 0 break 當(dāng)讀到文件結(jié)束時(shí) ifile eof 為真cout setw 6 i setw 10 j setw 10 k endl ifile close 關(guān)閉文件return0 例2 26 讀出存放百雞問(wèn)題計(jì)算結(jié)果的文件 本章重點(diǎn)例題或算法 分段函數(shù)用switch求分?jǐn)?shù)段1 2 n或1 2 n或X X N個(gè)數(shù)求最大值 最小值 平均值求素?cái)?shù)大小寫字母轉(zhuǎn)換求最大公約數(shù)或最小公倍數(shù)