C語言程序設(shè)計：chapter02 算法

1、第二章 程序的靈魂算法本章內(nèi)容提要2.1 算法的概念2.2簡單算法舉例2.3算法的特性2.4算法的表示方法2.5結(jié)構(gòu)化程序設(shè)計方法一個程序應(yīng)包括兩個方面的內(nèi)容:對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure)對操作的描述：算法(algorithm)著名計算機(jī)科學(xué)家沃思提出一個公式: 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序 數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具完整的程序設(shè)計應(yīng)該是: 廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。方法1：1+2，+3，+4，一直加到100 加99次方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次

2、對同一個問題，可有不同的解題方法和步驟例： 求 2.1 算法的概念為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡單，運(yùn)算步驟少。2. 算法的分類： 數(shù)值算法 非數(shù)值算法1)數(shù)值算法：數(shù)值算法具有現(xiàn)成的數(shù)學(xué)模型，其研究比較深入，通常把這些算法匯集起來，編制為現(xiàn)成的程序，供人們調(diào)用。(求數(shù)值解，程序）2)非數(shù)值算法：其種類繁多，要求各異，難以規(guī)范化，通常只對一些典型的非數(shù)值算法進(jìn)行研究。（事務(wù)管理，廣泛） 2.2 簡單算法舉例例2.1: 求12345 步驟1：先求12，得到結(jié)果2步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6步驟3：將6再乘以4，得24步

3、驟4：將24再乘以5，得120太繁瑣如果要求121000，則要寫999個步驟 S1：使p=1。 S2：使i=2。 S3：使pi，乘積仍放在變量p中，可表示為： pi p S4：使i的值加1，即i+1 i。 S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值?？梢栽O(shè)兩個變量：一個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果, 算法可改寫： 思考1 如果題目改為1357911，算法如何改動？S1: 1 pS2: 3 iS3: pipS4: i2

4、 iS5: 如果i=11，則返回S3；否則，結(jié)束。算法簡練思考2 如果題目改為2468910, 算法如何改動？S1: 0 sumS2: 2 iS3: sumisumS4: i2 iS5: 如果i=10，則返回S3；否則，結(jié)束。思考3如果S5改為i5開始2it*iti+1i結(jié)束NY 例2.6 將例2.1的算法用流程圖表示。 求12345如果需要將最后結(jié)果輸出:1t輸出ti5開始2it*iti+1i結(jié)束NY結(jié)束Y1i開始gi80輸出ni、gii+1ii50NYN 例2.7 例2.2的算法用流程圖表示。有50個學(xué)生，要求將成績在80分以上的學(xué)生的學(xué)號和成績輸出。1ii50開始i+1i結(jié)束NY輸入ni

5、、gi1igi80輸出ni、gii+1ii50NYYN如果包括輸入數(shù)據(jù)部分 例2.8 例2.3判定閏年的算法用流程圖表示。判定20002500年中的每一年是否閏年，將結(jié)果輸出。NYN2000yearyear+1yearYYNYN例2.9 將例2.4的算法用流程圖表示。求1sum2deno1sign(-1)*signsignsign*(1/deno)termsum+termsumdeno+1denoNY例2.9 將例2.4的算法用流程圖表示。NY2in%iri+1iiYN 例2.10 ：例2.5判斷素數(shù)的算法用流程圖表示。對一個大于或等于3的正整數(shù)，判斷它是不是一個素數(shù)。通過以上幾個例子可以看出

6、流程圖是表示算法的較好的工具一個流程圖包括以下幾部分：(1) 表示相應(yīng)操作的框(2) 帶箭頭的流程線(3) 框內(nèi)外必要的文字說明流程線不要忘記畫箭頭，否則難以判定各框的執(zhí)行次序2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖1.傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使人難以理解算法的邏輯2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖2.三種基本結(jié)構(gòu)(1) 順序結(jié)構(gòu)AB2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖2.三種基本結(jié)構(gòu)(2) 選擇結(jié)構(gòu)ABYpNAYpN2.4.3 三種基本結(jié)構(gòu)和改進(jìn)的流程圖2.三種基本結(jié)構(gòu)(3) 循環(huán)結(jié)構(gòu)

7、當(dāng)型循環(huán)結(jié)構(gòu)AYp1NYx51t輸出t2it*iti+1i 例2.12 將例2.2的算法用N-S圖表示。將50名學(xué)生中成績高于80分者的學(xué)號和成績輸出。直到i501t1ii+1i輸入ni、gii+1i直到i50gi80否是輸出ni,gi例2.13 將例2.3判定閏年的算法用N-S圖表示直到y(tǒng)ear25002000yearyear+1year否是year%4為0否是輸出year非閏年year%100不為0year%400為0是否輸出year非閏年輸出year閏年輸出year閏年例2.14 將例2.4的算法用N-S圖表示。求直到deno100deno+1deno輸出sum1sum1sign2den

8、o(-1)*signsignsign*(1/deno)termsum+termsum 例2.15 將例2.10判別素數(shù)的算法用N-S流程圖表示。NY2in%iri+1iiYN例2.10的流程圖不是由三種基本結(jié)構(gòu)組成的循環(huán)有兩個出口，不符合基本結(jié)構(gòu)的特點(diǎn)無法直接用N-S流程圖的三種基本結(jié)構(gòu)的符號來表示先作必要的變換NY開始輸入n0w 2in%irr=0i+1ii 和w=0YN1w輸出n是素數(shù)結(jié)束w=0輸出n不是素數(shù)輸入nr=0是否0w2in%ir1wi+1i直到i 或w 0w=0是否輸出n是素數(shù)輸出n不是素數(shù)一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)

9、移只存在于一個基本結(jié)構(gòu)范圍之內(nèi)一個非結(jié)構(gòu)化的算法可以用一個等價的結(jié)構(gòu)化算法代替，其功能不變?nèi)绻粋€算法不能分解為若干個基本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化的算法2.4.5用偽代碼表示算法偽代碼是用介于自然語言和計算機(jī)語言之間的文字和符號來描述算法用偽代碼寫算法并無固定的、嚴(yán)格的語法規(guī)則，可以用英文，也可以中英文混用例2.16 求5!。begin (算法開始) 1 t 2 i while i5 t*i t i+1 i print tend (算法結(jié)束)例2.17 求begin 1 sum 2 deno 1 sign while deno 100 (-1)*sign sign sign*1/deno

10、term sum+term sum deno+1 deno print sumend2.4.6用計算機(jī)語言表示算法要完成一項工作，包括設(shè)計算法和實(shí)現(xiàn)算法兩個部分。設(shè)計算法的目的是為了實(shí)現(xiàn)算法。不僅要考慮如何設(shè)計一個算法，也要考慮如何實(shí)現(xiàn)一個算法。 例2.18 將例2.16表示的算法（求5!）用C語言表示。#include int main( ) int i,t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(%dn,t); return 0;例2.19 將例2.17表示的算法（求多項式 的值）用C語言表示。#include int main( ) int

11、sign=1; double deno = 2.0,sum = 1.0, term; while (deno 編譯、連接、執(zhí)行程序輸出結(jié)果。例：張丘建算經(jīng)中提出“百雞問題”：雞翁一值錢五，雞母一值錢三，雞雛三值錢一。百錢買百雞，問雞翁、母、雛各幾何？（體會編程步驟、算法分析）1、分析：cockshens+chicks=100 5*cocks3*hens+chicks/3=100其中：0 cocks 19 0 hens 33 0chicks 100思路：依次取 cocks值域中的值，然后求其余兩數(shù)，看是否合乎題意。（累試法、枚舉法）算法描述：2.用計算機(jī)語言寫出程序#include void main() int cocks=0,hens,chicks; while(cocks=19) hens=0; while(hens=33) c