c程序設(shè)計(jì)第二章ppt課件

1、 C程序設(shè)計(jì)程序設(shè)計(jì)主講人：袁麗主講人：袁麗燕大里仁基礎(chǔ)教學(xué)部第二章：算法第二章：算法程序的靈魂程序的靈魂1 什么是算法什么是算法2 算法的特性算法的特性3 算法的表示算法的表示4 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法一個(gè)程序主要包括兩方面的信息：一個(gè)程序主要包括兩方面的信息：u 對(duì)數(shù)據(jù)的描述：在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)u的類型和數(shù)據(jù)的組織形式。即數(shù)據(jù)結(jié)構(gòu)data structure)u 對(duì)操作的描述：即要求計(jì)算機(jī)進(jìn)行操作的步驟，也就是算法u(algorithm)著名計(jì)算機(jī)科學(xué)家沃思提出的一個(gè)公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序 算法就是解決問題的思路。有好的算法，才會(huì)有好的程序。算法是程序

2、的精髓。算法就是解決問題的思路。有好的算法，才會(huì)有好的程序。算法是程序的精髓。類比于我們平常用的漢語，我們都能看懂普通的文字，但不是每個(gè)會(huì)說普通話的人類比于我們平常用的漢語，我們都能看懂普通的文字，但不是每個(gè)會(huì)說普通話的人都能寫出漂亮的文章。都能寫出漂亮的文章。 數(shù)據(jù)是操作的對(duì)象數(shù)據(jù)是操作的對(duì)象; ;操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工處理，以操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工處理，以得到期望的結(jié)果得到期望的結(jié)果 一個(gè)程序除了算法和數(shù)據(jù)結(jié)構(gòu)這主要要素外，還應(yīng)當(dāng)采用結(jié)一個(gè)程序除了算法和數(shù)據(jù)結(jié)構(gòu)這主要要素外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語言表構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種

3、計(jì)算機(jī)語言表示示 算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語言工具是一個(gè)程序設(shè)計(jì)算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語言工具是一個(gè)程序設(shè)計(jì)人員應(yīng)具備的知識(shí)人員應(yīng)具備的知識(shí)u算法是解決算法是解決“做什么和做什么和“怎么做的問題怎么做的問題u程序中的操作語句，是算法的體現(xiàn)程序中的操作語句，是算法的體現(xiàn)u不了解算法就談不上程序設(shè)計(jì)不了解算法就談不上程序設(shè)計(jì)一、什么是算法一、什么是算法 廣義地講：為解決一個(gè)問題而采取的方法和步驟，就稱為算法。廣義地講：為解決一個(gè)問題而采取的方法和步驟，就稱為算法。例如：描述太極拳動(dòng)作的圖解，就是太極拳的算法。一首歌曲的例如：描述太極拳動(dòng)作的圖解，就是太極拳的算法。一首歌曲的樂譜，也可

4、以稱為該歌曲的算法。樂譜，也可以稱為該歌曲的算法。 計(jì)算機(jī)能執(zhí)行的算法，為計(jì)算機(jī)算法。其可分為兩大類別：計(jì)算機(jī)能執(zhí)行的算法，為計(jì)算機(jī)算法。其可分為兩大類別：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。對(duì)同一個(gè)問題，可以有不同的解題方法和步驟對(duì)同一個(gè)問題，可以有不同的解題方法和步驟為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法法的質(zhì)量，選擇合適的算法數(shù)值運(yùn)算的目的是求數(shù)值解數(shù)值運(yùn)算的目的是求數(shù)值解非數(shù)值運(yùn)算包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域非數(shù)值運(yùn)算包括的面十分廣泛，最常見的是用于事務(wù)管理

5、領(lǐng)域例例1 1、求、求1 1* *2 2* *3 3* *4 4* *5 5。例例2 2、有、有5050個(gè)學(xué)生，要求輸出成績?cè)趥€(gè)學(xué)生，要求輸出成績?cè)?080分以上的學(xué)生的學(xué)號(hào)和成績。分以上的學(xué)生的學(xué)號(hào)和成績。例例3 3、給出一個(gè)大于或等于、給出一個(gè)大于或等于3 3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。二、算法的特性二、算法的特性u(píng)有窮性：一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無限的。有窮性：一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無限的。u有窮性往往指有窮性往往指“在合理的范圍之內(nèi)在合理的范圍之內(nèi)”?！昂侠硐薅扔扇藗兊某ＷR(shí)合理限度由人們的常識(shí)u和需要判定。和需要判定。u

6、確定性：算法的每一個(gè)步驟都應(yīng)當(dāng)是確定的，不應(yīng)當(dāng)含糊和模棱確定性：算法的每一個(gè)步驟都應(yīng)當(dāng)是確定的，不應(yīng)當(dāng)含糊和模棱u兩可。也就是說算法的含義應(yīng)當(dāng)是唯一的，而不可以產(chǎn)生兩可。也就是說算法的含義應(yīng)當(dāng)是唯一的，而不可以產(chǎn)生“歧義性歧義性”u有零個(gè)或多個(gè)輸入：所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得有零個(gè)或多個(gè)輸入：所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得u必要的信息。一個(gè)算法可以有兩個(gè)或多個(gè)輸入，也可以沒有輸入。必要的信息。一個(gè)算法可以有兩個(gè)或多個(gè)輸入，也可以沒有輸入。u有一個(gè)或多個(gè)輸出：算法的目的是為了求解，有一個(gè)或多個(gè)輸出：算法的目的是為了求解，“解就是輸出。解就是輸出。u但算法的輸出并不一定就是計(jì)算

7、機(jī)的打印輸出或屏幕輸出，一個(gè)算法但算法的輸出并不一定就是計(jì)算機(jī)的打印輸出或屏幕輸出，一個(gè)算法u得到的結(jié)果就是算法的輸出，沒有輸出的算法是沒有意義的。得到的結(jié)果就是算法的輸出，沒有輸出的算法是沒有意義的。u有效性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定有效性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定u的結(jié)果。的結(jié)果。三、算法的表示三、算法的表示 用自然語言表示算法 用流程圖表示算法 三種基本結(jié)構(gòu)和改進(jìn)的流程圖 用N-S流程圖表示算法 用偽代碼表示算法 用計(jì)算機(jī)語言表示算法（1用自然語言表示算法用自然語言表示算法n用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)歧義性用自然語言表示通

8、俗易懂，但文字冗長，容易出現(xiàn)歧義性n用自然語言描述包含分支和循環(huán)的算法，不很方便用自然語言描述包含分支和循環(huán)的算法，不很方便n除了很簡單的問題外，一般不用自然語言除了很簡單的問題外，一般不用自然語言 （2用流程圖表示算法用流程圖表示算法流程圖是用一些圖框表示各種操作。流程圖是用一些圖框表示各種操作。x0YN一個(gè)入口一個(gè)入口兩個(gè)出口兩個(gè)出口 菱形框的作用是對(duì)一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件菱形框的作用是對(duì)一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立決定如何執(zhí)行其后的操作。是否成立決定如何執(zhí)行其后的操作。 連接點(diǎn)小圓圈是用于將畫在不同地方的流程線連接起來。連接點(diǎn)小圓圈是用于將畫在不同地方的

9、流程線連接起來。位置不夠位置不夠防止交叉防止交叉例、求例、求1 1* *2 2* *3 3* *4 4* *5 5。將該算法用流程圖表示。將該算法用流程圖表示。開場(chǎng)開場(chǎng)1t2it*iti+1ii5Y終了終了N如果需要將最后結(jié)果輸出如果需要將最后結(jié)果輸出: :開場(chǎng)開場(chǎng)1t2it*iti+1ii5YN輸出輸出t終了終了如果需要將最后結(jié)果輸出如果需要將最后結(jié)果輸出: :例、求例、求1 1* *2 2* *3 3* *4 4* *5 5。將該算法用流程圖表示。將該算法用流程圖表示。例、例、 判定判定2000250020002500年中的每一年是否閏年，將結(jié)果輸出。年中的每一年是否閏年，將結(jié)果輸出。 將

10、該算法用流程圖表示。將該算法用流程圖表示。開場(chǎng)開場(chǎng)year不能不能被被4整除整除2000yearNyear不能不能被被100整除整除Yyear是閏年是閏年Yyear不是閏年不是閏年Nyear不能不能被被400整除整除Yyear不是閏年不是閏年Nyear是閏年是閏年year+1yearyear2500NY終了終了1. 1.通過以上幾個(gè)例子可以看出流程圖是表示算法的較好的工具。通過以上幾個(gè)例子可以看出流程圖是表示算法的較好的工具。2. 2.一個(gè)流程圖包括以下幾部分：一個(gè)流程圖包括以下幾部分：(1) (1) 表示相應(yīng)操作的框表示相應(yīng)操作的框(2) (2) 帶箭頭的流程線帶箭頭的流程線(3) (3)

11、框內(nèi)外必要的文字說明框內(nèi)外必要的文字說明3. 3.流程線不要忘記畫箭頭，否則難以判定各框的執(zhí)行次序。流程線不要忘記畫箭頭，否則難以判定各框的執(zhí)行次序。 （3三種基本結(jié)構(gòu)和改進(jìn)的流程圖三種基本結(jié)構(gòu)和改進(jìn)的流程圖1. 1.傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒有嚴(yán)格限制使用沒有嚴(yán)格限制使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使人難使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使人難以理解算法的邏輯以理解算法的邏輯2. 2.三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)(1)(1)順序結(jié)構(gòu)順序結(jié)構(gòu)AB（2 2選擇結(jié)構(gòu)選擇

12、結(jié)構(gòu)pYANBpYAN（3 3循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)結(jié)構(gòu)p1YAN0 xx5輸出輸出t例例: :將將5050名學(xué)生中成績高于名學(xué)生中成績高于8080分者的學(xué)號(hào)和成績輸出。將該算法用分者的學(xué)號(hào)和成績輸出。將該算法用N-SN-S圖表示。圖表示。1i輸入輸入ni、gii+1i直到直到i501igi80是是輸出輸出ni,gi否否i+1i直到直到i50例例: :將判定閏年的算法用將判定閏年的算法用N-SN-S圖表示圖表示n一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的n在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只在基本結(jié)構(gòu)之間不存在向前或向后的

13、跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)范圍之內(nèi)存在于一個(gè)基本結(jié)構(gòu)范圍之內(nèi)n一個(gè)非結(jié)構(gòu)化的算法可以用一個(gè)等價(jià)的結(jié)構(gòu)化算法代替，一個(gè)非結(jié)構(gòu)化的算法可以用一個(gè)等價(jià)的結(jié)構(gòu)化算法代替，其功能不變其功能不變n如果一個(gè)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它必然不是如果一個(gè)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它必然不是一個(gè)結(jié)構(gòu)化的算法一個(gè)結(jié)構(gòu)化的算法 （5用偽代碼表示算法用偽代碼表示算法n偽代碼是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)來描偽代碼是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號(hào)來描述算法述算法n用偽代碼寫算法并無固定的、嚴(yán)格的語法規(guī)則，可以用英文，用偽代碼寫算法并無固定的、嚴(yán)格的語法規(guī)則，可以用英文，也可

14、以中英文混用也可以中英文混用例例: :求求5! 5!。begin (begin (算法開始算法開始) ) 1 1 t t 2 2 i i while i5 while i5 t t* *i i t t i+1 i+1 i i print t print tend (end (算法結(jié)束算法結(jié)束) )例例: : 求求10019914131211begin begin 1 1 sum sum 2 2 deno deno 1 1 sign sign while deno 100 while deno 100 (-1) (-1)* *sign sign sign sign sign sign* *1/d

15、eno 1/deno term term sum+term sum+term sum sum deno+1 deno+1 deno deno print sum print sumendend（6 6用計(jì)算機(jī)語言表示算法用計(jì)算機(jī)語言表示算法n要完成一項(xiàng)工作，包括設(shè)計(jì)算法和實(shí)現(xiàn)算法兩個(gè)部分。要完成一項(xiàng)工作，包括設(shè)計(jì)算法和實(shí)現(xiàn)算法兩個(gè)部分。n設(shè)計(jì)算法的目的是為了實(shí)現(xiàn)算法。設(shè)計(jì)算法的目的是為了實(shí)現(xiàn)算法。n不僅要考慮如何設(shè)計(jì)一個(gè)算法，也要考慮如何實(shí)現(xiàn)一個(gè)算法。不僅要考慮如何設(shè)計(jì)一個(gè)算法，也要考慮如何實(shí)現(xiàn)一個(gè)算法。例例: :將算法求將算法求5! 5!）用）用C C語言表示。語言表示。#include #

16、include int main( )int main( ) int i,t; int i,t; t=1; i=2; t=1; i=2; while(i=5) while(i=5) t=t t=t* *i; i; i=i+1; i=i+1; printf(%dn,t); printf(%dn,t); return 0; return 0; 例例: :將算法求多項(xiàng)式的值用將算法求多項(xiàng)式的值用C C語言表示。語言表示。10019914131211#include #include int main( )int main( ) int sign=1; int sign=1; double deno

17、= 2.0,sum = 1.0, term; double deno = 2.0,sum = 1.0, term; while (deno = 100) while (deno 中提出中提出“百雞問題百雞問題”：雞翁一值錢五，雞母一值錢三，：雞翁一值錢五，雞母一值錢三，雞雛三值錢一。百錢買百雞，問雞翁、母、雛各幾何？雞雛三值錢一。百錢買百雞，問雞翁、母、雛各幾何？（體會(huì)編程步驟）（體會(huì)編程步驟）(1)(1)分析：分析：cocks+hens+chicks=100 5cocks+hens+chicks=100 5* *cocks+3cocks+3* *hens+chicks/3=100hens+c

18、hicks/3=100其中，其中，0 cocks 19 , 0 hens 33 ,0 chicks 1000 cocks 19 , 0 hens 33 ,0 chicks 100累試法枚舉法求解累試法枚舉法求解算法描述：算法描述： cocks=0 cocks=0 當(dāng)當(dāng)cocks 19cocks 19時(shí)時(shí)找滿足題意的找滿足題意的hens,chickshens,chicks數(shù)數(shù) cocks cocks加加1 1 細(xì)化細(xì)化cocks=0cocks=0 當(dāng)當(dāng)cocks 19cocks 19時(shí)時(shí)hens=0hens=0當(dāng)當(dāng)hens 33hens 33時(shí)時(shí) 找滿足題意的找滿足題意的chickschicks數(shù)數(shù) hens hens加加11henshens加加1 1 細(xì)化細(xì)化cocks=0cocks=0當(dāng)當(dāng)cocks