ch2 程序的靈魂-算法課件

1、C 語(yǔ)言第二講主講教師：謝本亮CH2 程序設(shè)計(jì)的靈魂-算法內(nèi)容提要： 算法及其算法的表示方法 結(jié)構(gòu)化程序設(shè)計(jì)方法 程序、程序設(shè)計(jì)和程序設(shè)計(jì)語(yǔ)言著名計(jì)算機(jī)科學(xué)家沃思（Nikilaus Wirth)提出：數(shù)據(jù)結(jié)構(gòu)+算法=程序描述數(shù)據(jù)的類型、組織形式描述對(duì)數(shù)據(jù)的操作步驟2.1 算法概念 做事情都有-方法、步驟（順序）-決定事情成敗1.算法：計(jì)算機(jī)求解某一問(wèn)題而采用的具體方法、步驟2.兩大類計(jì)算算法：數(shù)值運(yùn)算算法 與 非數(shù)值運(yùn)算算法 （求數(shù)值解、成熟） (事務(wù)管理、廣泛）3.算法的特性（P.21）：有窮性、確定性、有效性等4.算法描述：描述算法的方法有多種 歸納為二大類：文字 圖形（符號(hào)）2.2 算法

2、的描述方法 常用的算法描述方法： 帶序號(hào)的自然語(yǔ)言描述（例2.1-例2.5） 易懂卻不直觀，不嚴(yán)格 N-S圖（盒圖）：特點(diǎn)：完全去掉了帶簡(jiǎn)裝箭頭的流程線，算法的所有步驟都寫(xiě)在一個(gè)大矩形框（表示簡(jiǎn)單、符合結(jié)構(gòu)化思想）APTFABPAPA處理判斷循環(huán)偽代碼：用介于自然語(yǔ)言與計(jì)算機(jī)語(yǔ)言之間的文字及符號(hào)來(lái)描述 （方便、易懂、便于向計(jì)算機(jī)語(yǔ)言過(guò)渡） 流程圖：靈活、自由、形象、直觀，可表示任何算法輸入/輸出處理判斷連接點(diǎn)流程線起止例1：計(jì)算 ，寫(xiě)出其算法。 自然語(yǔ)言描述：1.0=S單元2.1 =n單元3.S+n =S4.n+1 =n5.判斷 是，轉(zhuǎn)3；否則轉(zhuǎn)66.輸出S的值流程圖描述：0=S輸出S開(kāi)始1=

3、nS+n =Sn+1 =n結(jié)束FTN-S圖描述：0=S1=nS+n =Sn+1 =n輸出S的值偽代碼描述：0=S1 =nIf S+n =S n+1 =nprint S順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu) 根據(jù)條件P決定是否重復(fù)執(zhí)行循環(huán)體中的操作APFT當(dāng)P為真A先判斷，后執(zhí)行APFT直到P為真A先執(zhí)行，后判斷sum=0;i=1;while(i=100) sum+=i; i+; sum=0;i=1;do sum+=i; i+;while(i=100);2.3 結(jié)構(gòu)化程序設(shè)計(jì)方法二、三種基本結(jié)構(gòu)的共同特點(diǎn) 單入單出口 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行 不存在“死循環(huán)”三、結(jié)構(gòu)化程序設(shè)計(jì)的優(yōu)點(diǎn) 用三種基本結(jié)構(gòu)組成

4、和程序是結(jié)構(gòu)化程序 優(yōu)點(diǎn)：易編、易讀、易懂、易維護(hù) 強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化 核心思想：自頂向下，逐步細(xì)化，模塊化設(shè)計(jì)，結(jié)構(gòu)化編碼 如：學(xué)校辦公自動(dòng)化系統(tǒng)舉例：張丘建算經(jīng)是提出“百雞問(wèn)題”：雞翁一值錢(qián)五，雞母一值錢(qián)三，雞雛三值錢(qián)一。百錢(qián)買百雞，問(wèn)雞翁、母、雛各幾何？（體會(huì)編程步驟）1、分析：cocks + hens + chicks =100 5 * cocks + 3 * hens + chicks/3=100 其中：0 cocks 19 ,0 hens 33, 0 chicks 100 思想：依次取cocks的值域中的值，然后求其余兩數(shù)，看是否合乎題意算法描述： cocks=0

5、當(dāng)cocks 19時(shí) 找滿足題意的 hens,chicks數(shù) cocks加1 cocks=0當(dāng)cocks 19時(shí) hens=0 當(dāng)hens 33時(shí) 找滿足題意的chicks數(shù) hens加1 cocks加1 累試法 枚舉法細(xì)化算法描述： cocks=0 當(dāng)cocks 19時(shí) 找滿足題意的 hens,chicks數(shù) cocks加1 cocks=0當(dāng)cocks 19時(shí) hens=0 當(dāng)hens 33時(shí) 找滿足題意的chicks數(shù) hens加1 cocks加1 細(xì)化細(xì)化cocks=0當(dāng)cocks 19時(shí) hens=0 當(dāng)hens 33時(shí) chicks=100-cocks-hens 如果（5 * cocks + 3 * hens + chicks/3=100）則輸出 hens加1 cocks加1 2、用計(jì)算機(jī)語(yǔ)言寫(xiě)出程序 void main() int cocks=0,hens,chicks; while(cocks=19) hens=0; while(hens=33) chicks=100-cocks-hens; if (5.0*cocks+3.0*hens+chicks/3.0=100.0) printf(“%d %d %dn”,cocks,hens,chicks); he