《第2章 算法---程序的靈魂》由會(huì)員分享，可在線閱讀，更多相關(guān)《第2章 算法---程序的靈魂（41頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),*,程序設(shè)計(jì)基礎(chǔ),單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),*,程序設(shè)計(jì)基礎(chǔ),第,2,章 算法,-,程序的靈魂,一個(gè)程序主要包括以下兩方面的信息：,(1),對(duì)數(shù)據(jù)的描述,。在程序中要指定用到,哪,些數(shù)據(jù)以及這些數(shù)據(jù)的類型和數(shù)據(jù)的組織形式,這就是數(shù)據(jù)結(jié)構(gòu),(data structure),(2),對(duì)操作的描述,。即要求計(jì)算機(jī)進(jìn)行操作的步驟,也就是算法,(algorithm),數(shù)據(jù)是操作的對(duì)象,操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工處理，以得到期望的結(jié)果,著名計(jì)算機(jī)科學(xué)家沃思,(,Nikiklaus,Wirth),提

2、出一個(gè)公式：,算法,+,數(shù)據(jù)結(jié)構(gòu),=,程序,算法,、,數(shù)據(jù)結(jié)構(gòu),、,程序設(shè)計(jì)方法,和,語(yǔ)言工具,是一個(gè)程序設(shè)計(jì)人員應(yīng)具備的知識(shí),2.1,什么是算法,2.2,簡(jiǎn)單的算法舉例,2.3,算法的特性,2.4,怎樣表示一個(gè)算法,2.5,結(jié)構(gòu)化程序設(shè)計(jì)方法,本章學(xué)習(xí)目標(biāo),2.1,什么是算法,廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為“,算法,”,對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟,為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法,2.1,什么是算法,計(jì)算機(jī)算法可分為兩大類別：,數(shù)值運(yùn)算算法,非數(shù)值運(yùn)算算法,數(shù)值運(yùn)算,的目的是求數(shù)值解,非數(shù)值運(yùn)算,包括的面十分廣泛，

3、最常見(jiàn)的是用于事務(wù)管理領(lǐng)域,2.2,簡(jiǎn)單的算法舉例,例,2.1,求,1,2,3,4,5,可以用最原始的方法進(jìn)行：,步驟,1,：先求,1*2,，得到結(jié)果,2,。,步驟,2,：將步驟,1,得到的乘積,2,再乘以,3,，得到結(jié)果,6,。,步驟,3,：將,6,再乘以,4,，得,24,。,步驟,4,：將,24,再乘以,5,，得,120,。這就是最后的結(jié)果。,例,2.1,求,1,2,3,4,5,1000,太繁瑣,2.2,簡(jiǎn)單的算法舉例,改進(jìn)的算法：,設(shè)變量,p,為被乘數(shù),變量,i,為乘數(shù),用循環(huán)算法求結(jié)果,2.2,簡(jiǎn)單的算法舉例,S1,：使,p=1,，或?qū)懗?1,p,S2,：使,i=2,，或?qū)懗?2,i,

4、S3,：使,p,與,i,相乘，乘積仍放在變量,p,中，可表示為：,p*,i,p,S4,：使,i,的值加,1,，即,i+1,i,S5,：如果,i,不大于,5,，返回重新執(zhí)行,S3,；否則，算法結(jié)束,最后得到,p,的值就是,5!,的值,若是,1000,，求什么？,2.2,簡(jiǎn)單的算法舉例,S1,：使,p=1,，或?qū)懗?1,p,S2,：使,i=2,，或?qū)懗?2,i,S3,：使,p,與,i,相乘，乘積仍放在變量,p,中，可表示為：,p*,i,p,S4,：使,i,的值加,1,，即,i+1,i,S5,：如果,i,不大于,5,，返回重新執(zhí)行,S3,；否則，算法結(jié)束,最后得到,p,的值就是,5!,的值,若,求,

5、1,3,5,7,9,11,3,3,2,2,11,11,相當(dāng)于,i 11,例,2.2,有,50,個(gè)學(xué)生,的成績(jī),，要求將成績(jī)?cè)?80,分以上的學(xué)生的學(xué)號(hào)和成績(jī)輸出。,用,n,i,代表第,i,個(gè)學(xué)生,學(xué)號(hào)，,g,i,表示第,i,個(gè)學(xué)生成績(jī),S1,：,1,i,S2,：如果,g,i,80,，,則輸出,n,i,和,g,i,，否則不輸出,S3,：,i+1,i,S4,：如果,i,50,，返回到步驟,S2,，繼續(xù)執(zhí)行，否則，算法結(jié)束,例,2.3,輸入,一個(gè)大于或等于,3,的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。,所謂素?cái)?shù),(prime),，是指除了,1,和該數(shù)本身之外，不能被其他任何整數(shù)整除的數(shù),例如，,13,是素?cái)?shù)

6、，因?yàn)樗荒鼙?2,，,3,，,4,，,12,整除。,判斷一個(gè)數(shù),n(n,3),是否素?cái)?shù)：將,n,作為被除數(shù)，將,2,到,(n-1),各個(gè)整數(shù)先后作為除數(shù)，如果都不能被整除，則,n,為素?cái)?shù),S1,：輸入,n,的值,S2,：,i=2,（,i,作為除數(shù)）,S3,：,n,被,i,除，得余數(shù),r,S4,：如果,r=0,，表示,n,能被,i,整除，則輸出,n,“不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行,S5,S5,：,i+1,i,S6,：如果,i,n-1,，返回,S3,；否則輸出,n,“是素?cái)?shù)”，然后結(jié)束。,可改為,n/2,2.3,算法的特性,一個(gè)有效算法應(yīng)該具有以下,特點(diǎn),：,(1),有窮性,。一個(gè)算法應(yīng)包含有

7、限的操作步驟，而不能是無(wú)限的。,(2),確定性,。算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。,2.3,算法的特性,(3),有零個(gè)或多個(gè)輸入,。所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。,(4),有一個(gè)或多個(gè)輸出,。算法的目的是為了求解，“解”就是輸出。,沒(méi)有輸出的算法是沒(méi)有意義的。,(5),有效性,。算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。,2.4,怎樣表示一個(gè)算法,2.4.1,用自然語(yǔ)言表示算法,2.4.2,用流程圖表示算法,2.4.3,三種基本結(jié)構(gòu)和改進(jìn)的流程圖,2.4.4,用,N-S,流程圖表示算法,2.4.5,用偽代碼表示算法,2.4.6,

8、用計(jì)算機(jī)語(yǔ)言表示算法,2.4.1,用自然語(yǔ)言表示算法,2.2,節(jié)介紹的算法是用自然語(yǔ)言表示的,用自然語(yǔ)言表示通俗易懂，但文字冗長(zhǎng)，容易出現(xiàn)歧義性,用自然語(yǔ)言描述包含分支和循環(huán)的算法，不很方便,除了很簡(jiǎn)單的問(wèn)題外，一般不用自然語(yǔ)言,2.4.2,用流程圖表示算法,流程圖,是用一些圖框來(lái)表示各種操作,用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點(diǎn),注釋框,x0,Y,N,一個(gè)入口,兩個(gè)出口,2.4.2,用流程圖表示算法,流程圖,是用一些圖框來(lái)表示各種操作,用圖形表示算法，直觀形象，易于理解,起止框,輸入輸出框,處理框,判斷框,流程線,連接點(diǎn),注釋框,位置不夠,防

9、止交叉,例,2.6,將例,2.1,的算法用流程圖表示。,求,1,2,3,4,5,如果需要將最后結(jié)果輸出,:,1,t,i5,開(kāi)始,2,i,t*,i,t,i+1,i,結(jié)束,N,Y,例,2.6,將例,2.1,的算法用流程圖表示。,求,1,2,3,4,5,如果需要將最后結(jié)果輸出,:,1,t,輸出,t,i5,開(kāi)始,2,i,t*,i,t,i+1,i,結(jié)束,N,Y,例,2.7,例,2.2,的算法用流程圖表示。有,50,個(gè)學(xué)生,的成績(jī),，要求將成績(jī)?cè)?80,分以上的學(xué)生的學(xué)號(hào)和成績(jī)輸出。,結(jié)束,Y,1,i,開(kāi)始,g,i,80,輸出,n,i,、,g,i,i+1,i,i50,N,Y,N,例,2.8,例,2.3,判

10、斷素?cái)?shù)的算法用流程圖表示。對(duì)一個(gè)大于或等于,3,的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。,N,Y,輸出,n,是素?cái)?shù),結(jié)束,開(kāi)始,輸入,n,2i,n%i,r,r=0,i+1i,i,輸出,n,是素?cái)?shù),Y,N,通過(guò)以上幾個(gè)例子可以看出流程圖是表示算法的較好的工具,一個(gè)流程圖包括以下幾部分,：,(1),表示相應(yīng)操作的框,(2),帶箭頭的流程線,(3),框內(nèi)外必要的文字說(shuō)明,流程線不要忘記畫(huà)箭頭，,否則,難以判定各框的執(zhí)行次序,2.4.3,三種基本結(jié)構(gòu)和改進(jìn)的流程圖,1.,傳統(tǒng)流程圖的弊端,傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制,使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去，使人難以理

11、解算法的邏輯,2.4.3,三種基本結(jié)構(gòu)和改進(jìn)的流程圖,2.,三種基本結(jié)構(gòu),(1),順序結(jié)構(gòu),A,B,2.4.3,三種基本結(jié)構(gòu)和改進(jìn)的流程圖,2.,三種基本結(jié)構(gòu),(2),選擇結(jié)構(gòu),A,B,Y,p,N,A,Y,p,N,2.4.3,三種基本結(jié)構(gòu)和改進(jìn)的流程圖,2.,三種基本結(jié)構(gòu),(3),循環(huán)結(jié)構(gòu),當(dāng)型循環(huán)結(jié)構(gòu),A,Y,p1,N,Y,x5,1,t,輸出,t,2,i,t*,i,t,i+1,i,例,2.10,將例,2.2,的算法用,N-S,圖表示。將,50,名學(xué)生中成績(jī)高于,80,分者的學(xué)號(hào)和成績(jī)輸出。,直到,i50,1,t,1,i,i+1,i,輸入,n,i,、,g,i,i+1,i,直到,i50,g,i,

12、80,否,是,輸出,n,i,g,i,2.5,結(jié)構(gòu)化程序設(shè)計(jì)方法,結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu),。,結(jié)構(gòu)化程序設(shè)計(jì)方法的,基本思路,是：把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段進(jìn)行，每個(gè)階段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。,2.5,程序設(shè)計(jì)的一般方法,采取以下方法保證得到結(jié)構(gòu)化的程序：,（,1,）,說(shuō)明問(wèn)題需求,（,2,）,分析問(wèn)題,（,3,）,設(shè)計(jì)解決問(wèn)題的算法,（,4,）編碼,問(wèn)題：求,1,100,間所有偶數(shù)的和,1,問(wèn)題分析與算法設(shè)計(jì),思路,：設(shè)置一個(gè)變量,(sum),，,其初值為,0,，然后在,1,100,的數(shù)中,(i),尋找偶數(shù),，,將它們一個(gè)一個(gè)累加到,sum,中。,一步累加：,sum=sum+i;,重復(fù)累加，用循環(huán)語(yǔ)句實(shí)現(xiàn)，在循環(huán)過(guò)程中：,(1),判別,i,是不是偶數(shù)：用分支控制語(yǔ)句來(lái)實(shí)現(xiàn)。,(2),對(duì)循環(huán)次數(shù)進(jìn)行控制：通過(guò),i,值的變化,sum=0,i=1,i=100,i,是偶數(shù)？,sum=,sum+i,i=i+1,輸出,sum,真,真,假,假,#include,int,main(void,),int,i,sum=0;,for(i=1;i=100;i+),if(i%2=0),sum=sum+i;,printf(%d,sum);,return 0;,編輯程序,作業(yè),參考教材：,P13,頁(yè)：第,3,，,5,，,6,題,