c語(yǔ)言第02章算法.ppt

第二章 算 法,一、教學(xué)內(nèi)容 1 算法的概念與簡(jiǎn)單實(shí)例 2 算法的特性 3 算法的描述 4 結(jié)構(gòu)化程序設(shè)計(jì)方法介紹 二、教學(xué)重點(diǎn)與難點(diǎn) 1 算法的概念及算法的描述算法的流程圖表示法； 2 編寫實(shí)際問(wèn)題的算法 三、教學(xué)方法與課時(shí)數(shù) 方法：講授法 課時(shí)數(shù)：4節(jié),四、 教學(xué)過(guò)程 (一) 算法的概念與簡(jiǎn)單實(shí)例 1 算法的概念 一個(gè)程序應(yīng)包括兩方面內(nèi)容： 對(duì)數(shù)據(jù)的描述：即數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)類型，組織形式） 對(duì)操作的描述，即操作步驟。 計(jì)算機(jī)科學(xué)家WIRTH提出：程序=數(shù)據(jù)結(jié)構(gòu)+算法 詳細(xì)描述：程序=數(shù)據(jù)結(jié)構(gòu)+算法+程序設(shè)計(jì)方法+語(yǔ)言工具和環(huán)境 算法：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。 計(jì)算機(jī)算法分為兩大類別：數(shù)值算法和非數(shù)值算法 2 簡(jiǎn)單算法舉例 例1：求1X2X3X4X5的積 算法：S1：令P=1 S2：令i=2 S3：使PXi，積仍放在變量P中，即PX i=P S4：使i的值加1，即i+1=I S5：如果i的值不大于5，返回重新執(zhí)行步驟S3以及S4，S5，否則，算法結(jié)束，得到計(jì)算結(jié)果。,例2：有50個(gè)學(xué)生，要求將成績(jī)?cè)?0分以上者打印出來(lái)，用n 表示學(xué)生的學(xué)號(hào)，n1代表第一個(gè)學(xué)生的學(xué)號(hào)，ni代表第i個(gè)學(xué)生學(xué)號(hào)，g代表學(xué)生成績(jī)，gi代表第i個(gè)學(xué)生成績(jī)， 算法：S1：1=i S2：如果gi 80，打印ni和gi ，否則不打印 S3：i+1=i S4：如果i50，返回S2，繼續(xù)執(zhí)行，否則算法結(jié)束。 例3,例4,例5見教材P16-17 （二） 算法的特性 一個(gè)算法有以下特點(diǎn)： 1 有窮性:僅有有限的操作步驟 2 確定性:算法的每一個(gè)步驟應(yīng)當(dāng)是確定的， 即無(wú)“二義性”。 3 有零個(gè)或多個(gè)輸入 4 有一個(gè)可多外輸出 5 有效性:算法中的每一個(gè)步驟都應(yīng)當(dāng)有效執(zhí)行,（三）算法描述 常用的描述方法有：自然語(yǔ)言，流程圖，偽代碼，PAD圖等 1、用自然語(yǔ)言表示算法 用人們?nèi)粘Ｊ褂玫恼Z(yǔ)言（漢語(yǔ)，英語(yǔ)，日語(yǔ)等）來(lái)描述一個(gè)問(wèn)題的求解過(guò)程，對(duì)人而言易理解，但不易寫成計(jì)算機(jī)執(zhí)行的程序。 2、用流程圖表示算法 流程圖是用一些圖框表示各種操作。用圖形表示算法直觀形象，易于理解。常用的圖框有： 起止框： 輸入輸出框： 判斷框： 處理框： 流程線： 連接點(diǎn)： 注釋框：-,【例2.3】判定2000 2500年中的每一年是否閏年，將結(jié)果輸出。 潤(rùn)年的條件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份； 設(shè)y為被檢測(cè)的年份，則算法可表示如下： S1: 2000y S2:若y不能被4整除，則輸出y“不是閏年”，然后轉(zhuǎn)到S6 S3:若y能被4整除，不能被100整除，則輸出y“是閏年”，然后轉(zhuǎn)到S6 S4:若y能被100整除，又能被400整除，輸出y“是閏年” 否則輸出y“不是閏年”，然后轉(zhuǎn)到S6 S5:輸出y“不是閏年”。 S6:y+1y S7:當(dāng)y2500時(shí), 返回S2繼續(xù)執(zhí)行，否則，結(jié)束。,三種基本結(jié)構(gòu)和改進(jìn)的流程圖,三種基本結(jié)構(gòu)的共同特點(diǎn)： 1.只有一個(gè)入口； 2.只有一個(gè)出口； 3. 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到； 4. 結(jié)構(gòu)內(nèi)不存在“死循環(huán)”。,順序結(jié)構(gòu)：,2.選擇結(jié)構(gòu)：,3.循環(huán)結(jié)構(gòu),用偽代碼表示算法 偽代碼使用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。,用計(jì)算機(jī)語(yǔ)言表示算法 我們的任務(wù)是用計(jì)算機(jī)解題，就是用計(jì)算機(jī)實(shí)現(xiàn)算法； 用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵循所用語(yǔ)言的語(yǔ)法規(guī)則。,（四）結(jié)構(gòu)化程序設(shè)計(jì)方法 1971年，Wirth基于其開發(fā)程序設(shè)計(jì)語(yǔ)言和編程的實(shí)踐經(jīng)驗(yàn)，首次提出了“結(jié)構(gòu)化程序計(jì)”(structured programming)的概念。 這個(gè)概念的要點(diǎn)是:不要求一步就編制成可執(zhí)行的程序，而是分若干步進(jìn)行，逐步求精。 第一步編出的程序抽象度最高，第二步編出的程序抽象度有所降低最后一步編出的程序即為可執(zhí)行的程序。用這種方法編程，似乎復(fù)雜，實(shí)際上優(yōu)點(diǎn)很多，可使程序易讀、易寫、易調(diào)試、易維護(hù)、易保證其正確性及驗(yàn)證其正確性。結(jié)構(gòu)化程序設(shè)計(jì)方法又稱為“自頂向下”或“逐步求精”法，在程序設(shè)計(jì)領(lǐng)域引發(fā)了一場(chǎng)革命，成為程序開發(fā)的一個(gè)標(biāo)準(zhǔn)方法，尤其是在后來(lái)發(fā)展起來(lái)的軟件工程中獲得廣泛應(yīng)用。有人評(píng)價(jià)說(shuō)沃思的結(jié)構(gòu)化程序設(shè)計(jì)概念“完全改變了人們對(duì)程序設(shè)計(jì)的思維方式”，這是一點(diǎn)也不夸張的。,結(jié)構(gòu)化程序設(shè)計(jì)的基本思想是：任何程序都可以用三種基本結(jié)構(gòu)的組合來(lái)實(shí)現(xiàn)。這三種基本結(jié)構(gòu)是：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。這三種結(jié)構(gòu)都具有一個(gè)入口和一個(gè)出口。 結(jié)構(gòu)化程序設(shè)計(jì)方法的四條原則是：1. 自頂向下；2. 逐步求精；3.模塊化；4.限制使用goto語(yǔ)句。 “自頂向下”是說(shuō)，程序設(shè)計(jì)時(shí)，應(yīng)先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)