C語(yǔ)言程序設(shè)計(jì)-第02章-程序的靈魂-算法

程序的靈魂—算法第2章本章內(nèi)容算法的概念簡(jiǎn)單算法舉例算法的特性算法的表示結(jié)構(gòu)化程序設(shè)計(jì)方法2.1算法的概念程序的幾個(gè)要素程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)方法+語(yǔ)言工具+環(huán)境

算法是靈魂，程序語(yǔ)句是算法的體現(xiàn)數(shù)據(jù)結(jié)構(gòu)是加工對(duì)象語(yǔ)言是工具編程需要采用合適的方法—結(jié)構(gòu)化的程序設(shè)計(jì)方法2.1算法的概念廣義算法算法是為解決一個(gè)問題而采取的方法和步驟。對(duì)同一個(gè)問題，可以有不同的解題方法和步驟。例如：求1+2+3+…+100方法1：先進(jìn)行1+2，再加3，再加4，一直加到100。方法2：100+(1+99)+(2+98)+…+(49+51)+50=100+50+49×100=50502.1算法的概念計(jì)算機(jī)算法即計(jì)算機(jī)能執(zhí)行的算法。數(shù)值運(yùn)算的算法可由庫(kù)函數(shù)實(shí)現(xiàn)，如求函數(shù)的定積分等。非數(shù)值運(yùn)算的算法如查找、排序，事務(wù)管理系統(tǒng)等。2.2簡(jiǎn)單算法舉例例2.1求1×2×3×4×5設(shè)被乘數(shù)為T，乘數(shù)為I，乘積結(jié)果仍放在變量T中，作為下一個(gè)被乘數(shù)。S1：使T=1S2：使I=2S3：使T×I，可表示為：T×I=>T。S4：使I的值加1，即I+1=>I。S5：如果I不大于5，返回重新執(zhí)行S3，以及其后的步驟S4，S5；否則，算法結(jié)束。2.2簡(jiǎn)單算法舉例例2.2有50個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?0分以上者打印出來。用i代表學(xué)生數(shù)，Ni代表第i個(gè)學(xué)生的學(xué)號(hào)，Gi代表第i個(gè)學(xué)生成績(jī)。S1：1=>iS2：如果Gi≥80，則打印Ni和Gi，否則不打印。S3：i+1=>iS4：如果i≤50，返回S2，繼續(xù)執(zhí)行。否則，算法結(jié)束。2.2簡(jiǎn)單算法舉例例2.3將2000~2500年中每一年是否閏年打印出來。閏年的條件是：能被4整除，但不能被100整除的年份都是閏年；能被100整除，又能被400整除的年份是閏年。設(shè)Y為年份，算法表示如下：S1：2000=>YS2：若Y不能被4整除，則打印Y“不是閏年”，然后轉(zhuǎn)到S5。S3：若Y能被4整除，不能被100整除，打印“是閏年”，然后轉(zhuǎn)到S5。S4：若Y能被100整除，又能被400整除，打印Y“是閏年”；否則打印“不是閏年”。S5：Y+1=>YS6：當(dāng)Y<=2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，如Y>2500，算法停止。2.2簡(jiǎn)單算法舉例例2.4求S1:sign=1S2:sum=1S3:deno=2S4:sign=(-1)xsignS5:term=signx(1/deno)S6:sum=sum+termS7:deno=deno+1S8:若deno≤100返回S4；否則結(jié)束。2.2簡(jiǎn)單算法舉例例2.5對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。素?cái)?shù)是指除1和該數(shù)本身之外不能被其它任何整數(shù)整除的數(shù)。判斷一個(gè)數(shù)N(N≥3)是否素?cái)?shù)的方法：將N作為被除數(shù)，將2到SQRT(N)各個(gè)整數(shù)輪流作為除數(shù)，如果都不能被整除，則N為素?cái)?shù)。S1:輸入N的值。S2:i=2。S3:N被i除，得余數(shù)R。S4:如果R=0，表示N能被i整除，則打印N“不是素?cái)?shù)”，算法結(jié)束。否則執(zhí)行S5。S5:i+1=>iS6:如果i≤SQRT(N)，返回S3。否則打印N“是素?cái)?shù)”，算法結(jié)束。2.3算法的特性有窮性包含有限個(gè)操作步驟。確定性含義是唯一的，不應(yīng)當(dāng)產(chǎn)生“歧義性”。有零或多個(gè)輸入有一個(gè)或多個(gè)輸出有效性每步有確定的結(jié)果，如例四分母不能為零。2.4算法的表示常用表示方法有：自然語(yǔ)言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖N-S流程圖偽代碼計(jì)算機(jī)語(yǔ)言PAD圖等2.4算法的表示用傳統(tǒng)流程圖表示算法美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI（AmericanNationalStandardInstitute）規(guī)定了一些常用的流程圖符號(hào)：起止框判斷框輸入輸出框處理框連接點(diǎn)流程線注釋框或2.4算法的表示例2.6：將例2.1求5!的算法用流程圖表示。開始1=>T2=>II+1=>IT×I=>TI≤5打印T結(jié)束YN2.4算法的表示例2.8：將例2.3判定閏年的算法用流程圖表示。1234開始2000=>YY不能被4整除打印Y“是閏年”Y不能被100整除Y能被400整除打印Y“不是閏年”打印Y“是閏年”打印Y“不是閏年”YYYNNN2.4算法的表示12Y+1=>YY≤2500結(jié)束43YN2.4算法的表示例2.10：用流程圖表示判斷一個(gè)數(shù)(≥3)是否素?cái)?shù)的算法。開始N/I的余數(shù)=>R2=>IR=0？輸入NY打印N“不是素?cái)?shù)”I+1=>INI≤SQRT(N)打印N“是素?cái)?shù)”結(jié)束YN2.4算法的表示結(jié)構(gòu)化流程圖傳統(tǒng)流程圖的弊端用流程線指出各框的執(zhí)行順序，流程圖無規(guī)律。閱讀難度大，難以修改。難以保證算法的可靠性和可維護(hù)性。解決方案規(guī)定幾種基本結(jié)構(gòu)。由基本結(jié)構(gòu)按一定規(guī)律組成一個(gè)算法結(jié)構(gòu)。2.4算法的表示三種基本結(jié)構(gòu)順序結(jié)構(gòu)ABab(a)2.4算法的表示選擇結(jié)構(gòu)pAB成立不成立ab(b)pAba(c)2.4算法的表示循環(huán)結(jié)構(gòu)當(dāng)型(While型)循環(huán)結(jié)構(gòu)先判斷后執(zhí)行當(dāng)條件成立時(shí)執(zhí)行pAba(a)直到型(Until)循環(huán)先執(zhí)行后判斷當(dāng)條件不成立時(shí)執(zhí)行pAba(b)成立不成立2.4算法的表示例如：打印五個(gè)數(shù)1，2，3，4，5。x<5?x+1=>x(a)0=>x打印x的值YN(b)x≥5?x+1=>x0=>x打印x的值YN當(dāng)型循環(huán)和直到型循環(huán)是可以互相轉(zhuǎn)換的2.4算法的表示三種基本結(jié)構(gòu)的共同特點(diǎn)只有一個(gè)入口。只有一個(gè)出口。結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行。即對(duì)每一個(gè)框來說，都應(yīng)當(dāng)有一條從入口到出口的路徑通過它。結(jié)構(gòu)內(nèi)不存在“死循環(huán)”（無終止的循環(huán)）。由以上三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可解決任何復(fù)雜問題。由基本結(jié)構(gòu)所構(gòu)成的算法屬于“結(jié)構(gòu)化”的算法，它不存在無規(guī)律的轉(zhuǎn)移，只有在基本結(jié)構(gòu)內(nèi)才存在分支和向前或向后跳轉(zhuǎn)。2.4算法的表示N-S流程圖1973年美國(guó)學(xué)者I.Nassi和B.Shneiderman提出的一種新的流程圖形式。N-S流程圖的特點(diǎn)沒有流程線全部算法寫在一個(gè)矩形框內(nèi)，該框內(nèi)還可包含其它從屬于它的框。適于結(jié)構(gòu)化程序設(shè)計(jì)。2.4算法的表示N-S流程圖的三種基本結(jié)構(gòu)表示順序結(jié)構(gòu)AB選擇結(jié)構(gòu)P

成立不成立

AB循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)當(dāng)P1

A直到型循環(huán)直到P2A2.4算法的表示說明用以上N-S流程圖的三種基本框，可組成復(fù)雜的N-S流程圖，以表示算法。圖中的“A”框或“B”框，可以是一個(gè)簡(jiǎn)單的操作（如讀入數(shù)據(jù)或打印輸出等），也可以是三個(gè)基本結(jié)構(gòu)之一。例如：

P≥100

成立不成立R=0.08R=0.06n≤10P×(1+R)=>PBA2.4算法的表示例2.11用N-S流程圖表示求5!的算法。1=>T2=>II>5T×I=>TI+1=>I打印T2.4算法的表示例2.13用N-S圖表示判定2000~2500年中每一年是否閏年的算法。2000=>Y

Y/4的余數(shù)為0

是否

Y/100的余數(shù)不為0

是否

Y/400的余數(shù)為0

是否打印Y“是閏年”打印Y“非閏年”打印Y“是閏年”Y+1=>Y打印Y“非閏年”

Y>25002.4算法的表示N-S圖總結(jié)每一個(gè)基本結(jié)構(gòu)可以用一個(gè)框代表；一個(gè)結(jié)構(gòu)化的流程圖最后應(yīng)能簡(jiǎn)化為若干個(gè)框（即若干個(gè)基本結(jié)構(gòu)）順序構(gòu)成；每一個(gè)基本結(jié)構(gòu)中還可包含另一個(gè)基本結(jié)構(gòu)。N-S圖表示算法的優(yōu)點(diǎn)直觀、易于理解；比傳統(tǒng)流程圖緊湊易畫（無流程線）；算法結(jié)構(gòu)由各基本結(jié)構(gòu)順序組成；結(jié)構(gòu)化算法。2.4算法的表示用偽代碼表示算法偽代碼用來描述算法的介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)。存在問題傳統(tǒng)流程圖和N-S圖適宜表示一個(gè)算法。當(dāng)其用于設(shè)計(jì)算法而進(jìn)行修改時(shí)比較麻煩。解決辦法用偽代碼（pseudocode)表示算法。用偽代碼表示算法無固定的、嚴(yán)格的語(yǔ)法規(guī)則。2.4算法的表示例2.17打印出50個(gè)學(xué)生中成績(jī)高于80分者的學(xué)號(hào)和成績(jī)。BEGIN1=>IDOUNTILI>50inputNiandGiI+1=>IENDDO1=>IDOUNTILI>50IFGi≥80printNiandGiENDIFI+1=>IENDDOEND2.4算法的表示用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵循所用語(yǔ)言的語(yǔ)法規(guī)則。例2.20：用C語(yǔ)言表示求5!的算法。main(){

inti,t;t=1;i=2;

while(i<=5){t=t*i;i=i+1