c語言第02章算法.ppt

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