模塊5-2.ppt

1、計算機應(yīng)用基礎(chǔ),模塊一計算機概論 模塊二計算機基本理論 模塊三微機操作環(huán)境 模塊四計算機網(wǎng)絡(luò)基礎(chǔ) 模塊五計算機程序設(shè)計基礎(chǔ) 模塊六數(shù)據(jù)庫基礎(chǔ) 模塊七計算機安全,2020/7/28,程序設(shè)計基礎(chǔ)知識,5.1 程序與程序設(shè)計語言 5.2算法與算法設(shè)計 5.3程序結(jié)構(gòu) 5.4結(jié)構(gòu)化程序設(shè)計方法,2020/7/28,不只是計算問題有算法，實際上任何一個問題的進(jìn)行過程都有它自己的算法。解決任何問題都要確定有哪些操作步驟，以及如何控制各步驟的進(jìn)行。,生活中的算法問題,例1: 一天中的時間安排問題,例2: 處理某一件事情的具體步驟,例3: 紅、藍(lán)兩個墨水瓶中的墨水互換,算法就是解決實際問題的方法和步驟。,一

2、、算法,5.2 算法與算法設(shè)計,1. 算法的概念,什么是算法?,2020/7/28,5.2 算法與算法設(shè)計,決定了算法的執(zhí)行順序 控制結(jié)構(gòu)有：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。 算法的控制結(jié)構(gòu)也是組成程序的基本結(jié)構(gòu)。,算術(shù)運算、邏輯運算、比較運算和數(shù)據(jù)傳送,1.基本功能操作,2. 控制結(jié)構(gòu),算法的 基本要素,2. 算法的基本要素,由上例可見任何簡單或復(fù)雜的算法都包含兩個基本要素。,2020/7/28,3. 算法的基本特征,輸出是指與輸入有某種特定關(guān)系的量，是算法進(jìn)行信息加工后得到的結(jié)果,有窮性,一個算法必須在執(zhí)行有限個操作步驟后終止,確定性,算法中每一個步驟都有確切的定義,不可出現(xiàn)任何二義性,可行

3、性,算法中每一步操作都能有效執(zhí)行 （如：一個數(shù)被0 除的操作就是無效的）,有零個 或多個輸入,輸入是指算法開始之前所需要的原始數(shù)據(jù),有一個 或多個輸出,5.2 算法與算法設(shè)計,2020/7/28,4. 算法的分類,計算機算法可分為兩大類： 數(shù)值運算算法： 求解數(shù)值； 非數(shù)值運算算法： 事務(wù)管理。,例1: 數(shù)值計算問題：結(jié)構(gòu)靜力分析計算需要解線性代數(shù)方程組。,例2: 非數(shù)值計算問題：計算機對弈 算法對弈的規(guī)則和策略 模型棋盤及棋盤的格局,5.2 算法與算法設(shè)計,2020/7/28,二、算法設(shè)計的原則,1.正確性：對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果。,2.可讀性：算法應(yīng)該易理解，便于交流

4、,3.健壯性：當(dāng)輸入非法數(shù)據(jù)時，算法應(yīng)恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)處理。,4.高效率與低存儲量需求：算法執(zhí)行時間較少，算法執(zhí)行所需存儲空間較小。,5.2 算法與算法設(shè)計,2020/7/28,三、算法的表示,自然語言 流程圖 結(jié)構(gòu)化流程圖（N-S圖） 偽代碼 PAD圖(Problem Analysis Diagram） 計算機語言,5.2 算法與算法設(shè)計,2020/7/28,1. 流程圖,用規(guī)定的一系列圖形、流程線和文字說明算法中的基本操作和控制流程。,5.2 算法與算法設(shè)計,流程圖包括： 表示相應(yīng)操作的框； 帶箭頭的流程線； 框內(nèi)外必要的文字說明。,2020/7/28,（1）圖形符號,5.2 算法

5、與算法設(shè)計,起止框,判斷框,處理框,輸入/輸出框,注釋框,流向線,連接點,2020/7/28,圖 c,例：連接點的使用,圖 A,圖 B,等價,圖A+圖B等價于圖C,5.2 算法與算法設(shè)計,2020/7/28,（2）用流程圖表示算法,例1：求給定半徑R的圓面積和圓周長。,5.2 算法與算法設(shè)計,算法： 圓面積 S=* R2 圓周長 L=2*R,2020/7/28,5.2 算法與算法設(shè)計,開始,輸入a,b,c,x,xa？,輸出 f,結(jié)束,Y,N,選擇結(jié)構(gòu),（2）用流程圖表示算法,2020/7/28,例3：上節(jié)求12345，即5。用流程圖表示法,方法一：,方法二：,開始,循環(huán)結(jié)構(gòu),循環(huán)體,2020/

6、7/28,例4：求 S=1+2+3+.+100,0s; s+1s s+2 s . s+100 s,0s s+i s (循環(huán)) (i=1,2,.,100),5.2 算法與算法設(shè)計,循環(huán)體,2020/7/28,例5: 給定K值，求T=1+2+3+K。,5.2 算法與算法設(shè)計,K=5，T=0 I=1：T=0+1=1，I=1+1=2 I=2：T=1+2=3，I=2+1=3 I=3：T=3+3=6，I=3+1=4 I=4：T=6+4=10，I=4+1=5 I=5：T=10+5=15，I=5+1=6,0 T T+I T(I=1,2,3,K),2020/7/28,2. NS流程圖,5.2 算法與算法設(shè)計,由

7、于流程線的任意轉(zhuǎn)向性，傳統(tǒng)流程圖無法保證自頂向下的程序設(shè)計，使模塊之間的調(diào)用關(guān)系難以表達(dá)。故兩位美國學(xué)者 I.Nassi 和B.Shneiderman于1973年提出了無流程線的N-S流程圖。 其根據(jù)是：既然任何算法都是由前面介紹的三種結(jié)構(gòu)組成，所以各基本結(jié)構(gòu)之間的流程線就是多余的，因此，N - S圖也是算法的一種結(jié)構(gòu)化描述方法。,2020/7/28,（1）圖形符號,5.2 算法與算法設(shè)計,2020/7/28,5.2 算法與算法設(shè)計,2020/7/28,5.2 算法與算法設(shè)計,2020/7/28,5.2 算法與算法設(shè)計,2020/7/28,（2）用N-S流程圖表示算法,例：求給定半徑R的圓面積

8、和圓周長。,5.2 算法與算法設(shè)計,2020/7/28,例：求給定數(shù)R的絕對值。,5.2 算法與算法設(shè)計,2020/7/28,例: 給定K值，求T=1+2+3+K。,循環(huán),循環(huán)體,5.2 算法與算法設(shè)計,2020/7/28,3.偽代碼,偽代碼也是描述算法常用的工具之一； 類似英語的表示形式； 部分英語和部分結(jié)構(gòu)化代碼的組合。,5.2 算法與算法設(shè)計,2020/7/28,偽代碼描述算法的一般組成：,算法頭：算法的名字。 目的、條件和返回值： 目的： 有關(guān)算法要做什么的簡短說明 前置條件：列出算法所有前驅(qū)條件 后置條件：指出算法產(chǎn)生的影響 返回值： 算法返回的結(jié)果或無返回值 語句序號：表示語句之間

9、的附屬關(guān)系。,5.2 算法與算法設(shè)計,2020/7/28,例：用偽代碼描述在一數(shù)列中找最小值的算法。,Algorithm （算法）：Finding Smallest Purpose（目的）：在一數(shù)列中找最小值 Pre（前置條件）：List of numbers（數(shù)列） Post（后置條件）：None Return（返回值）：The smallest,3,2,4,1,6,a:,S,3,2,1,算法：設(shè)數(shù)列中第一個數(shù)為最小值S，然后用后續(xù)數(shù)依次與S比較，若比S小，則用該數(shù)替換原S的值，全部比較完成后S即最小值。,5.2 算法與算法設(shè)計,2020/7/28,1.Set smallest to the

10、 first number 2.Loop(not end of list) 2.1 if(next number smallest) 2.2.1 set smallest to next number 2.2 end if 3. end loop 4. return smallest End Finding Smallest,循環(huán),循環(huán)體,5.2 算法與算法設(shè)計,2020/7/28,1. 數(shù)列ai ( i=1,5 ) 2. a1 S, 2 i 3. while(i5) 3.1 if(aiS ) then ai S endif 3.2 i+1i end while 4. return S,偽代碼

11、不一定按上述嚴(yán)格的格式，且可以使用漢字，只要把算法表達(dá)清楚即可。,循環(huán),循環(huán)體,5.2 算法與算法設(shè)計,2020/7/28,4.PAD圖 PAD（Problem Analysis Diagram），是近年來在軟件開發(fā)中被廣泛使用的一種算法的圖形表示法。 與前述的流程圖、N-S圖相比，PAD圖除了自上而下以外，還有自左向右的展開，所以，如果說流程圖、N-S圖是一維的算法描述的話，則PA D圖就是二維的，它能展現(xiàn)算法的層次結(jié)構(gòu)，更直觀易懂。,5.2 算法與算法設(shè)計,2020/7/28,選擇結(jié)構(gòu)(1) 單分支選擇，條件為真執(zhí)行A (2) 兩分支選擇，條件為真執(zhí)行A，為假執(zhí)行B。(3) 多分支選擇，當(dāng)

12、I = I1時執(zhí)行A，= I2時執(zhí)行B，I = I3時執(zhí)行C，I = I4時執(zhí)行。,PAD圖的幾種基本形態(tài)：,順序結(jié)構(gòu),2020/7/28,循環(huán)結(jié)構(gòu)while型循環(huán)，do - while型循環(huán)。,PAD圖的幾種基本形態(tài)：,5.2 算法與算法設(shè)計,2020/7/28,例：輸入三個數(shù)，然后輸出其中最大的數(shù)。 PAD圖表示為：,例：猴子吃桃問題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮，又多吃了一只，第二天照此辦理，吃掉剩下桃子的一半另加一個，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問這堆桃子原來有多少個？,5.2 算法與算法設(shè)計,2020/7/28,s=a1; i=2; whil

13、e(i=5) if(ais ) s = ai; i= i+1; return s;,4. 計算機語言,循環(huán),循環(huán)體,5.2 算法與算法設(shè)計,2020/7/28,四、幾種常用的算法,1. 枚舉法,也稱為窮舉法，即一一的列舉。該方法經(jīng)常用于不定方程的求解問題。如“百錢買百雞問題”。,例1：,雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一，百錢買百雞 ，問雞翁、雞母、雞雛各幾何？,解：用x、y、z分別代表公雞、母雞和小雞的數(shù)量， 列出方程為：,x+y+z=100 5x+3y+z/3=100,根據(jù)題意可知x、y、z的范圍：分別約是正整數(shù)20、30；100，簡單的解題方法是：假設(shè)一組x、y、z的值，一一

14、帶入方程組求解，找出全部可能的組合，以得到所有滿足方程組的解。,5.2 算法與算法設(shè)計,2020/7/28,枚舉法例：,2020/7/28,枚舉法解題的步驟如下：,(1) 分析題目,確定答案的大致范圍。 (2) 確定列舉方法，常用的有順序列舉、排列列舉和組合列舉。 (3) 實驗所有可能范圍內(nèi)的情況。 (4) 實驗后得到滿足題目條件的一組或多組答案，或無答案。,枚舉法的特點：,算法簡單，容易理解，因為要用可能范圍內(nèi)的數(shù)值一一去試，所以運算量較大。枚舉算法以循環(huán)結(jié)構(gòu)實現(xiàn)。,5.2 算法與算法設(shè)計,2020/7/28,2. 迭代法,迭代法是數(shù)值近似求解的方法?？茖W(xué)計算上很多問題可用這種方法解決。,例

15、1：,計算 s=1+2+3+4+100,迭代法有精確迭代法和近似迭代法。精確迭代法指算術(shù)本身提供了問題的精確解，如對N個數(shù)求和、求均值、方差、對方程求近似解等。,迭代方法如下:,5.2 算法與算法設(shè)計,2020/7/28,例2：,牛頓迭代法：,1. 估計實根可能的范圍,任選一個接近于真實根x的近似根x1。,2. 由 x1求出f(x1)。,3. 求f(x1)。,4. 由圖可知：f(x1)=f(x1)/(x1-x2) 所以 x2=x1-f(x1)/f(x1) 同理 xn=xn-1-f(xn-1)/f(xn-1),5. 由x2求出f(x2)再求f(x2)及x3， 重復(fù)以上步驟，依次求出x4、 x5、

16、xn 直到前后兩次求出的近似根| xn+1- xn| 此時就認(rèn)為xn+1是足夠接近真實根的近似根。,假設(shè)函數(shù)f(x)在某區(qū)間內(nèi)為單調(diào)函數(shù),(即在此范圍內(nèi)函數(shù)值單調(diào)增 加或單調(diào)減少)且有一個實根,用牛頓迭代法求f(x)的根的方法為：,迭代法例：,2020/7/28,xn=0.5*(xn-1+a/xn-1),2020/7/28,5.2 算法與算法設(shè)計,3. 遞推和遞歸法,這也是程序中常用的兩種算法，最常見的如用于計算級數(shù)。這種方法一般給出數(shù)列的前項與后項的遞推公式，然后計算數(shù)列的通項。,例1：,已知某數(shù)列為1,1,2,3,5,8,13,.,求第n項的值。,(1) 首先確定 f(1)=1；f(2)=

17、1; (2) 計算 f(3)=f(1)+f(2); f(4)=f(3)+f(2); (3) 依此遞推下去可知 f(n)=f(n-1)+f(n-2) 。,這就是該數(shù)列的通項公式。,遞推法: 由已知的前兩項可得下一項，依次遞推下去，得到第n項得值。,你知道這個數(shù)列嗎？,2020/7/28,遞推法例：,已知某數(shù)列為1,1,2,3,5,8,13,.,求第n項的值。,循環(huán),循環(huán)體,如果輸出前n項的值呢？,2020/7/28,5.2 算法與算法設(shè)計,例2：,求n！；設(shè)n=10。,(1) 首先 f(0)=0!=1； (2) f(1)=1!=1*0!=1; (3) f(2)=2!=2*1!=2; (4) f(

18、3)=3!=3*2!=6 (3) 依此遞推下去可知 f(n)=n!=n*(n-1)!=n*f(n-1) 。,遞推法的關(guān)鍵是找到進(jìn)行遞推的通項公式,然后求解。,2020/7/28,5.2 算法與算法設(shè)計,遞歸法也是利用遞推公式，它的特點是: 由繁到簡，用簡單的問題和已進(jìn)行的操作運算解決復(fù)雜問題。,遞歸法：,上例2：,用遞歸求n！,f(1)=1； f(n)=f(n-1)n; 將后一個式子從n到n-1、再到n-2逐步遞推化簡得到：f(n)= f(n-1)n= f(n-2) (n-1)n; = f(1)*2*3*n (n1),每一次化簡,自變量減一,但多乘一個因子,在化簡的每一步, f(n-1),f(n-2),仍為未知量,直到化簡到f(1),因f(1)是已知的可由最后一個式子得到結(jié)果。.,2020/7/28,遞歸法例：,用遞歸法求n！ 。,調(diào)用f(n)函數(shù),求n!,求n!的遞歸函數(shù)f(n),2020/7/28,5.2 算法與算法設(shè)計,遞推是從已知的初始條件出發(fā)，逐次遞推出最后所求的值。一個遞推算法總可以轉(zhuǎn)換為一個遞歸算法。 一般遞推法用循環(huán)結(jié)構(gòu)實現(xiàn)。 而遞