算法簡(jiǎn)介及程序的基本結(jié)構(gòu)(2)ppt課件

1、第二章第二章 算法簡(jiǎn)介及程序的根本構(gòu)算法簡(jiǎn)介及程序的根本構(gòu)造造本章要點(diǎn)：了解算法的根本概念掌握程序的根本構(gòu)造算法(algorithm)是對(duì)特定問(wèn)題求解步驟的一種描畫。程序=數(shù)據(jù)構(gòu)造+算法+程序設(shè)計(jì)方法+編程言語(yǔ)2.1 算法的概念算法的概念例例1. 有有50個(gè)學(xué)生個(gè)學(xué)生 ，要求將他們之中成果在，要求將他們之中成果在80分以上者打印出來(lái)。分以上者打印出來(lái)。用用n表示學(xué)號(hào)，表示學(xué)號(hào)，n1代表第一個(gè)學(xué)生學(xué)號(hào)，代表第一個(gè)學(xué)生學(xué)號(hào)，ni代表第代表第i個(gè)學(xué)生學(xué)號(hào)。個(gè)學(xué)生學(xué)號(hào)。用用g代表學(xué)生成果，代表學(xué)生成果， gi 代表第代表第i個(gè)學(xué)生成果，算法可表示如下：個(gè)學(xué)生成果，算法可表示如下：S1：1i S2：假設(shè)

2、：假設(shè)gi 80 ，那么打印，那么打印 ni 和和gi ，否那么不打印，否那么不打印S3： i+1 i S4: 假設(shè)假設(shè) i 50, 前往前往S2， 繼續(xù)執(zhí)行；繼續(xù)執(zhí)行； 否那么，算法終了。否那么，算法終了。 2.2 簡(jiǎn)單算法舉例簡(jiǎn)單算法舉例 (用自然言語(yǔ)描畫法用自然言語(yǔ)描畫法例例2 將學(xué)生百分成果按分?jǐn)?shù)段分級(jí)的程序。將學(xué)生百分成果按分?jǐn)?shù)段分級(jí)的程序。 該算法的中心部分是對(duì)輸入的每一個(gè)數(shù)進(jìn)展比較判別，該算法的中心部分是對(duì)輸入的每一個(gè)數(shù)進(jìn)展比較判別，以確定屬于的級(jí)別。假設(shè)學(xué)生成果分布是均勻的，算法描畫以確定屬于的級(jí)別。假設(shè)學(xué)生成果分布是均勻的，算法描畫如下：如下：S1：1i S2: a60 a7

3、0 a80 a90 不及格不及格中等中等良好良好優(yōu)秀優(yōu)秀及格及格YNYNYNYN輸入輸入10000個(gè)數(shù)據(jù)，那么個(gè)數(shù)據(jù)，那么需進(jìn)展需進(jìn)展31500次比較。次比較。S3: i+1 iS4:假設(shè)假設(shè)i 10000, 前往前往S2； 否那么，算法終了。否那么，算法終了。轉(zhuǎn)S3轉(zhuǎn)S3轉(zhuǎn)S3轉(zhuǎn)S3轉(zhuǎn)S3分?jǐn)?shù)分?jǐn)?shù)0596069707980899099比例比例0.050.150.40.30.10 不及格不及格Y a90 a80 a70 aii50輸出gi 和 nii+1=ii50終了YNN輸入ni和gi i+1=igi=80N1=iY2.4.3 2.4.3 程序的三種根本構(gòu)造和程序的三種根本構(gòu)造和改良的流程圖

4、改良的流程圖N-SN-S構(gòu)造流程圖構(gòu)造流程圖一、順序構(gòu)造一、順序構(gòu)造 BA (a)AB (b)先執(zhí)行A操作，再執(zhí)行B操作，兩者是順序執(zhí)行關(guān)系。N-S構(gòu)造流程圖二、選擇構(gòu)造二、選擇構(gòu)造當(dāng)P條件為真時(shí)，執(zhí)行A模塊，否那么執(zhí)行B模塊。APB真假(a)P真假AB(b)三、循環(huán)構(gòu)造三、循環(huán)構(gòu)造當(dāng)P條件成立時(shí)，反復(fù)執(zhí)行A,直到P為假。1.當(dāng)型循環(huán)構(gòu)造PA假真(a)當(dāng)P為真A(b)當(dāng)P為真2.2.直到型循環(huán)構(gòu)造直到型循環(huán)構(gòu)造先執(zhí)行A操作，再判別P能否為假，假設(shè)P為假，再執(zhí)行A，直到P為真為止。AP假真 (a) A直到P為真 (b)1=i輸入ni和gii+1=i直到i501=i gi =80真假輸出ni和gi

5、i+1=i直到i50開(kāi)場(chǎng)1=ii50輸出gi 和 nii+1=ii50終了YNN輸入ni和gi i+1=igi=80N1=iY2.4.5 用偽代碼表示算法：用介于自然言語(yǔ)和計(jì)算機(jī)言語(yǔ)之間用偽代碼表示算法：用介于自然言語(yǔ)和計(jì)算機(jī)言語(yǔ)之間的文字和符號(hào)來(lái)描畫算法的文字和符號(hào)來(lái)描畫算法 BEGIN 1 =i while(i 50) input ni和和gi i+1=I 1 =i while(i 50) if (gi =80) print ni和和gi i+1=i END 2.4.6 用計(jì)算機(jī)言語(yǔ)表示算法 例4：求 1-1/2 + 1/3 1/4 + 1/99 1/100。S1: 1 signS2: 1

6、 sumS3: 2 denoS4: (-1)*sign signS5: sign*(1/deno) termS6: sum+term sumS7: deno+1 denoS8: 假設(shè)deno 100 前往S4；否那么算法終了。main() int sign=1; float deno=2.0 , sum=1.0, term; while (deno=100) sign= -sign; term=sign/deno; sum=sum+term; deno=deno+1; printf(“%f,sum); 2.4 構(gòu)造化程序設(shè)計(jì)方法1. 自頂向下2. 逐漸細(xì)化3. 模塊化設(shè)計(jì)4. 構(gòu)造化編碼產(chǎn)生最佳解產(chǎn)生最佳解得到好輸入得到好輸入讀輸入讀輸入輸出結(jié)果輸出結(jié)果計(jì)算最佳解計(jì)算最佳解顯示結(jié)果顯示結(jié)果編輯輸入編輯輸入結(jié)果格式化結(jié)果格式化好輸入好輸入原始輸入原始輸入原始輸入原始輸入編輯輸入編輯輸入好好輸輸入入解解解解解解格式化解格式化解格式化解格式化解產(chǎn)生最佳解的一般結(jié)構(gòu)產(chǎn)生最佳解的一般結(jié)構(gòu)得到好輸入得到好輸入main()計(jì)算最佳解計(jì)算最佳解輸出結(jié)果輸出結(jié)果得到好輸入得到好輸入讀輸入讀輸入編輯輸入編輯輸入RETURN(編輯好的輸入）編輯好的輸入）讀輸入讀輸入 輸入處置； return 輸入；編輯輸入編輯輸入 編輯輸入處置； return 編輯好的