c程序相關(guān)設(shè)計(jì)第二章

1、c程序相關(guān)設(shè)計(jì)第二章程序的靈魂程序的靈魂1 什么是算法2 算法的特性3 算法的表示4 結(jié)構(gòu)化程序設(shè)計(jì)方法一個(gè)程序主要包括兩方面的信息：n 對(duì)數(shù)據(jù)的描述：在程序中要指定用到哪些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式。即數(shù)據(jù)結(jié)構(gòu)（data structure)n 對(duì)操作的描述：即要求計(jì)算機(jī)進(jìn)行操作的步驟，也就是算法(algorithm)著名計(jì)算機(jī)科學(xué)家沃思提出的一個(gè)公式：算法+數(shù)據(jù)結(jié)構(gòu)=程序 算法就是解決問(wèn)題的思路。有好的算法，才會(huì)有好的程序。算法是程序的精髓。類比于我們平常用的漢語(yǔ)，我們都能看懂普通的文字，但不是每個(gè)會(huì)說(shuō)普通話的人都能寫(xiě)出漂亮的文章。 數(shù)據(jù)是操作的對(duì)象;操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工

2、處理，以得到期望的結(jié)果 一個(gè)程序除了算法和數(shù)據(jù)結(jié)構(gòu)這主要要素外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語(yǔ)言表示 算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語(yǔ)言工具是一個(gè)程序設(shè)計(jì)人員應(yīng)具備的知識(shí)n算法是解決“做什么”和“怎么做”的問(wèn)題n程序中的操作語(yǔ)句，是算法的體現(xiàn)n不了解算法就談不上程序設(shè)計(jì)一、什么是算法一、什么是算法 廣義地講：為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為算法。例如：描述太極拳動(dòng)作的圖解，就是太極拳的算法。一首歌曲的樂(lè)譜，也可以稱為該歌曲的算法。 計(jì)算機(jī)能執(zhí)行的算法，為計(jì)算機(jī)算法。其可分為兩大類別：數(shù)值運(yùn)算算法和非數(shù)值運(yùn)算算法。對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟為

3、了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法數(shù)值運(yùn)算的目的是求數(shù)值解非數(shù)值運(yùn)算包括的面十分廣泛，最常見(jiàn)的是用于事務(wù)管理領(lǐng)域例1、求1*2*3*4*5。例2、有50個(gè)學(xué)生，要求輸出成績(jī)?cè)?0分以上的學(xué)生的學(xué)號(hào)和成績(jī)。例3、給出一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。二、算法的特性二、算法的特性n有窮性：一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。有窮性往往指“在合理的范圍之內(nèi)”?！昂侠硐薅取庇扇藗兊某ＷR(shí)和需要判定。n確定性：算法的每一個(gè)步驟都應(yīng)當(dāng)是確定的，不應(yīng)當(dāng)含糊和模棱兩可。也就是說(shuō)算法的含義應(yīng)當(dāng)是唯一的，而不可以產(chǎn)生“歧義性”n有零個(gè)或多個(gè)輸入：所謂輸

4、入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。一個(gè)算法可以有兩個(gè)或多個(gè)輸入，也可以沒(méi)有輸入。n有一個(gè)或多個(gè)輸出：算法的目的是為了求解，“解”就是輸出。但算法的輸出并不一定就是計(jì)算機(jī)的打印輸出或屏幕輸出，一個(gè)算法得到的結(jié)果就是算法的輸出，沒(méi)有輸出的算法是沒(méi)有意義的。n有效性：算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。三、算法的表示三、算法的表示 用自然語(yǔ)言表示算法 用流程圖表示算法 三種基本結(jié)構(gòu)和改進(jìn)的流程圖 用N-S流程圖表示算法 用偽代碼表示算法 用計(jì)算機(jī)語(yǔ)言表示算法（1）用自然語(yǔ)言表示算法）用自然語(yǔ)言表示算法n用自然語(yǔ)言表示通俗易懂，但文字冗長(zhǎng)，容易出現(xiàn)歧義性用自然語(yǔ)言表示通俗

5、易懂，但文字冗長(zhǎng)，容易出現(xiàn)歧義性n用自然語(yǔ)言描述包含分支和循環(huán)的算法，不很方便用自然語(yǔ)言描述包含分支和循環(huán)的算法，不很方便n除了很簡(jiǎn)單的問(wèn)題外，一般不用自然語(yǔ)言除了很簡(jiǎn)單的問(wèn)題外，一般不用自然語(yǔ)言 （2）用流程圖表示算法）用流程圖表示算法流程圖是用一些圖框表示各種操作。x0YN一個(gè)入口兩個(gè)出口 菱形框的作用是對(duì)一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立決定如何執(zhí)行其后的操作。 連接點(diǎn)（小圓圈）是用于將畫(huà)在不同地方的流程線連接起來(lái)。位置不夠防止交叉例、求1*2*3*4*5。將該算法用流程圖表示。開(kāi)始1t2it*iti+1ii5Y結(jié)束N如果需要將最后結(jié)果輸出:開(kāi)始1t2it*iti+1ii5Y

6、N輸出t結(jié)束如果需要將最后結(jié)果輸出:例、求1*2*3*4*5。將該算法用流程圖表示。例、 判定20002500年中的每一年是否閏年，將結(jié)果輸出。 將該算法用流程圖表示。開(kāi)始year不能被4整除2000yearNyear不能被100整除Yyear是閏年Yyear不是閏年Nyear不能被400整除Yyear不是閏年Nyear是閏年year+1yearyear2500NY結(jié)束1.通過(guò)以上幾個(gè)例子可以看出流程圖是表示算法的較好的工具。2.一個(gè)流程圖包括以下幾部分：(1) 表示相應(yīng)操作的框(2) 帶箭頭的流程線(3) 框內(nèi)外必要的文字說(shuō)明3.流程線不要忘記畫(huà)箭頭，否則難以判定各框的執(zhí)行次序。 （3）三種

7、基本結(jié)構(gòu)和改進(jìn)的流程圖）三種基本結(jié)構(gòu)和改進(jìn)的流程圖1. 1.傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖的弊端n傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制格限制n使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去，使人難以使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去，使人難以理解算法的邏輯理解算法的邏輯2. 2.三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)(1)順序結(jié)構(gòu)AB（2）選擇結(jié)構(gòu)pYANBpYAN（3）循環(huán)結(jié)構(gòu) 當(dāng)型循環(huán)結(jié)構(gòu)p1YAN0 xx5輸出t例:將50名學(xué)生中成績(jī)高于80分者的學(xué)號(hào)和成績(jī)輸出。將該算法用N-S圖表示。1i輸入ni、gii+1i

8、直到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)之間不存在向前或向后的跳轉(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è)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它必然不是一個(gè)

9、結(jié)構(gòu)化的算法結(jié)構(gòu)化的算法 （5）用偽代碼表示用偽代碼表示算法算法n偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法n用偽代碼寫(xiě)算法并無(wú)固定的、嚴(yán)格的語(yǔ)法規(guī)則，可以用英文，也可以中英文用偽代碼寫(xiě)算法并無(wú)固定的、嚴(yán)格的語(yǔ)法規(guī)則，可以用英文，也可以中英文混用混用例例: :求求5! 5!。begin (begin (算法開(kāi)始算法開(kāi)始) ) 1 1 t t 2 2 i i while i while i5 5 t t* *i i t t i+1 i+1 i i print t print tend (end (算法結(jié)束算法結(jié)束) )

10、例: 求10019914131211begin 1 sum 2 deno 1 sign while deno 100 (-1)*sign sign sign*1/deno term sum+term sum deno+1 deno print sumend（6 6）用計(jì)算機(jī)語(yǔ)言表示用計(jì)算機(jī)語(yǔ)言表示算法算法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!）用C

11、語(yǔ)言表示。#include int main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(%dn,t); return 0;例例: :將算法（求多項(xiàng)式的值）用將算法（求多項(xiàng)式的值）用C C語(yǔ)言表示。語(yǔ)言表示。10019914131211#include int main( ) int sign=1; double deno = 2.0,sum = 1.0, term; while (deno = 100) sign = -sign; term = sign/deno; sum = sum+term; deno = deno+1;

12、printf (%fn,sum); return 0;四、四、結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法n結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)晰的結(jié)構(gòu)。n結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是：把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是：把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段進(jìn)行，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。進(jìn)行，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。n采取以下方法保證得到結(jié)構(gòu)化的程序：采取以下方法保證得到結(jié)構(gòu)化的程序：（1 1） 自頂向下；自頂向下；（2 2） 逐步細(xì)化；

13、逐步細(xì)化；（3 3） 模塊化設(shè)計(jì)；模塊化設(shè)計(jì)；（4 4） 結(jié)構(gòu)化編碼。結(jié)構(gòu)化編碼。用三種基本結(jié)構(gòu)組成的程序是結(jié)構(gòu)化程序 自頂向上，逐步細(xì)化：將問(wèn)題求解由抽象逐步具體化的設(shè)計(jì)過(guò)程。 比如設(shè)計(jì)房屋，先進(jìn)行整體規(guī)劃，然后確定建筑物方案，再進(jìn)行各個(gè)部分的設(shè)計(jì)，最后進(jìn)行細(xì)節(jié)的設(shè)計(jì)（門(mén)窗，樓道等），而絕不會(huì)在沒(méi)有整體方案之前先設(shè)計(jì)樓道和廁所。而在完成設(shè)計(jì)，有了圖紙之后，在施工階段則是自下而上實(shí)施的，用一磚一瓦實(shí)現(xiàn)一個(gè)局部，最后由各個(gè)部分組成一個(gè)建筑物。 模塊化設(shè)計(jì)：“分而治之”的思想，把大任務(wù)分為若干子任務(wù)。 程序中的子模塊在C語(yǔ)言中通常是用函數(shù)來(lái)實(shí)現(xiàn)。 結(jié)構(gòu)化編碼：將已設(shè)計(jì)好的算法用計(jì)算機(jī)語(yǔ)言來(lái)表示，即根據(jù)已經(jīng)細(xì)化的算法正確寫(xiě)出計(jì)算機(jī)程序。結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì)步驟步驟一、確定算法：分析問(wèn)題（建立數(shù)學(xué)模型，利用公式),寫(xiě)出算法 描述（比如流程圖）二、編寫(xiě)程序：用計(jì)算機(jī)語(yǔ)言寫(xiě)出實(shí)現(xiàn)算法的程序三、上機(jī)調(diào)試：輸入（編輯）程序-編譯、連接、執(zhí)行程序-輸出結(jié)果舉例： 算經(jīng)中提出“百雞問(wèn)題”：雞翁一值錢(qián)五，雞母一值錢(qián)三，雞雛三值錢(qián)一。百錢(qián)買(mǎi)百雞，問(wèn)雞翁、母、雛各幾何？（體會(huì)編程步驟）(1)分析：cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100其中，0 cocks 19 , 0 hens 33 ,0 chicks 100累試法（枚舉法