第2章算法及其描述課件

第2章算法及其描述

（程序的靈魂）第2章算法及其描述12.1算法

2.1.1什么是算法？算法是對問題的思維方法和過程體現(xiàn).1.算法的特征:(1)確定性,確定唯一的意義,不能有二意性.(2)有限行,執(zhí)行時有限時間內(nèi)結(jié)束,解決問題.(3)可行性,控制操作是可實現(xiàn)的.2.算法的結(jié)構(gòu):(1)順序結(jié)構(gòu)：<操作1><操作2><操作3>。(2)選擇結(jié)構(gòu)：如果<條件>成立執(zhí)行<操作1>

否則執(zhí)行<操作2>。(3)循環(huán)結(jié)構(gòu)：重復執(zhí)行<操作>直到<條件>成立。2.1算法

2.1.1什么是算法？算法是對問題的思維方22.1.2算法的描述算法是解決問題的方法和步驟在計算機上的表示任何問題的求解都有一定的“算法”計算機算法有很大不同算法是人設(shè)計出來的計算機算法是嚴謹?shù)?不能有二意性.算法可分為兩類：數(shù)值運算算法：主要用于科學運算非數(shù)值運算算法：如信息檢索、人工智能等2.1.2算法的描述算法是解決問題的方法和步驟在計算機上32.1.3算法的舉例:

例：判斷任意整數(shù)n（n≥3）是不是素數(shù)？素數(shù)是只能被1和自身整除（余數(shù)為零）的整數(shù)算法分析：用n做被除數(shù)，依次用2到（n–1）之間的各個整數(shù)做除數(shù)，求所有的余數(shù)，如果所有余數(shù)都不為零，則n為素數(shù)；只要有一個余數(shù)為零就可以斷定n不是素數(shù)算法：1）任意輸入n2）令i=2（i做除數(shù)，i=2,3,...,n-1）3）計算n/i，得余數(shù)r4）若r=0，則打印“n不是素數(shù)”，轉(zhuǎn)到7；否則繼續(xù)5）令i=i+16）若i<n，轉(zhuǎn)到3；否則打印“n是素數(shù)”7）算法結(jié)束2.1.3算法的舉例:

例：判斷任意整數(shù)n（n≥3）4算法的舉例:例2-1：求Y=1!+3!+5!+……+49!問題：求1到50之間奇數(shù)的階乘之和.(1)問題分析:理解奇數(shù)階乘的求和.(2)算法描述:Y表示求和,S表示每一個階乘,I階乘的序號.(3)算法的說明:1)意為Y=1!2)意為S=2!3)令I(lǐng)=34)S=S*I=I!5)INT(I/2)!=I/2I!為奇數(shù)的階乘，加入到Y(jié)中.6)I加1.7)返回4)進行4),5),6)步;直到I=50,輸出結(jié)果算法結(jié)束.算法的舉例:例2-1：求Y=1!+3!+5!+…52.2流程圖2.2.1流程圖及其分類1.傳統(tǒng)流程圖起止框處理框輸入/出框判斷框流程線基本圖件2.2流程圖起止框處理框輸入/出框判斷框流程線基本圖件6三種基本結(jié)構(gòu)（1966年，Bohra和Jacopini提出）（1）順序結(jié)構(gòu)（2）選擇（分支）結(jié)構(gòu)ABC順序結(jié)構(gòu)ABCP二路分支結(jié)構(gòu)三種基本結(jié)構(gòu)（1966年，Bohra和Jacopini提出）7（3）循環(huán)結(jié)構(gòu)當型循環(huán)（先判斷后執(zhí)行，執(zhí)行次數(shù)可能為0）

直到型循環(huán)（先執(zhí)行后判斷，至少執(zhí)行1次）ABCP當型循環(huán)否是ABCP直到型循環(huán)是否（3）循環(huán)結(jié)構(gòu)ABCP當型循環(huán)否是ABCP直到型循環(huán)是否8三種基本結(jié)構(gòu)的特點：只有一個入口只有一個出口具有結(jié)構(gòu)化的特征應避免流程線的交叉三種基本結(jié)構(gòu)的特點：92.N-S盒圖1973年由美國的I.Nassi和B.Shneidermen提出特點：1）不使用流程線（箭頭）；2）全部算法寫在一個大的矩形框內(nèi)；3）搭積木方式，真正的結(jié)構(gòu)化。2.N-S盒圖1973年由美國的I.Nassi和10三種基本結(jié)構(gòu)A操作B操作順序結(jié)構(gòu)P是否AB分支結(jié)構(gòu)P條件滿足A循環(huán)體當型循環(huán)PA直到型循環(huán)只允許“從上邊入，從下邊出”三種基本結(jié)構(gòu)A操作B操作順序結(jié)構(gòu)P是否AB分支結(jié)構(gòu)P條件滿足11輸入nN>=0？輸出-n輸出n例2-2：輸出一個數(shù)的絕對值解題思路：1、判斷n>=0; 2、是輸出n;否則輸出-n.輸入nn>=0？是否輸出n輸出-n輸入nN>=0？輸出-n輸出n例2-2：輸出一個數(shù)的絕對值解12例算法的舉例:例：求s=1+2+3+……+100問題：求100個整數(shù)的和s，結(jié)果是s

這100個整數(shù)是從1到100的所有自然數(shù)算法一：設(shè)s為累加單元1)將1送到S中；2)把2加到S中（即S中的內(nèi)容1加2后再送回S中，下同）3)把3加到S中；……100)把100加到S中；101)把S中的結(jié)果輸出。例算法的舉例:算法一：設(shè)s為累加單元131=>SS+2=>SS+3=>SS+100=>S輸出S例用流程圖與盒圖描述算法1=>SS+2=>SS+3=>S…………S+100=>S輸出S1=>SS+2=>SS+3=>SS+100=>14例：求s=1+2+3+……+100問題：求100個整數(shù)的和s，結(jié)果是s

這100個整數(shù)是從1到100的所有自然數(shù)算法二：設(shè)n為計數(shù)單元，s為累加單元1)將0送到S中，將0送到n中；2)將n+1送到n中，再把n加到s中；3)判斷n的值是否大于等于100？4)若n<100，轉(zhuǎn)到2；否則向下進行；5）輸出s中的內(nèi)容。例：求s=1+2+3+……+100算法二150=>n0=>Sn<100輸出Sn+1=>nS+n=>S例用流程圖與盒圖描述算法0=>S,nn+1=>nS+n=>S輸出Sn<100是否0=>nn<100輸出Sn+1=>n16例2-3輸入10個數(shù)，求它們的平均值。例2-4輸入50個學生成績，統(tǒng)計出不及格的人數(shù)。例2-3輸入10個數(shù)，求它們的平均值。17例求Fibonacci數(shù)列：1，1，2，3，5，8，……的前40個數(shù)。

F1=1(n=1)F2=1(n=2)Fn=Fn-1+Fn-2(n≥3)1534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144987676546368317811217830914930352102334155/*c5_12.c*/#include<stdio.h>main(){longintf1,f2;inti;f1=1;f2=1;

for(i=1;i<=20;i++){printf("%12ld%12ld",f1,f2);if(i%2==0)printf("\n");f1=f1+f2;f2=f2+f1;}}f1=1,f2=1fori=1to20輸出f1,f2f1=f1+f2f2=f2+f1例求Fibonacci數(shù)列：1，1，2，3，5，8，……的18例判斷m是否素數(shù)/*c5_13.c*/#include<stdio.h>#include<math.h>main(){intm,i,k;scanf("%d",&m);k=sqrt(m);

for(i=2;i<=k;i++)if(m%i==0)break;if(i>=k+1)printf("%dis",m);elseprintf("%disnot",m);printf("aprimenumber\n");}例6.9求100~200間的全部素數(shù)讀入mi=2當i≤km被i整除真假用break結(jié)束循環(huán)i=i+1i≥k+1真假輸出:m”是素數(shù)”輸出:m”不是素數(shù)”k=m例判斷m是否素數(shù)/*c5_13.c*/例6.9求10192.2.3流程圖應用舉例例2-5求Y=1!+3!+5!+……+49!問題：求1到50之間奇數(shù)的階乘之和.2.2.3流程圖應用舉例例2-5求Y=1!+3!+202.3偽代碼偽代碼的使用UsageofPseudocode

偽代碼(Pseudocode)是一種算法描述語言。使用為代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言(Pascal,C,Java,etc)實現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰，代碼簡單，可讀性好，并且類似自然語言。

下面介紹一種類偽代碼的語法規(guī)則。

偽代碼的語法規(guī)則

在偽代碼中，每一條指令占一行(elseif例外，)，指令后不跟任何符號（Pascal和C中語句要以分號結(jié)尾）；書寫上的“縮進”表示程序中的分支程序結(jié)構(gòu)。這種縮進風格也適用于if-then-else語句。用縮進取代傳統(tǒng)Pascal中的begin和end語句來表示程序的塊結(jié)構(gòu)可以大大提高代碼的清晰性；同一模塊的語句有相同的縮進量，次一級模塊的語句相對與其父級模塊的語句縮進；2.3偽代碼偽代碼的使用UsageofPseudoco21偽代碼表示的算法

用傳統(tǒng)的流程圖和N-S圖表示算法直觀易懂，但畫起來比較費事，在設(shè)計一個算法時，可能要反復修改，而修改流程圖是比較麻煩的。因此，流程圖適宜于表示一個算法，但在設(shè)計算法過程中使用不是很理想的(尤其是當算法比較復雜、需要反復修改時)。為了設(shè)計算法時方便，常用一種稱為偽代碼的工具。偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。它如同一篇文章一樣，自上而下地寫下來。每一行(或幾行)表示一個基本操作。它不用圖形符號，因此書寫方便、格式緊湊，易懂也便于向計算機語言算法(即程序)過渡。可以用英文、漢字、中英文混合表示算法，以便于書寫和閱讀為原則。用偽代碼寫算法并無固定的、嚴格的語法規(guī)則，只要把意思表達清楚，并且書寫的格式要寫成清晰易讀的形式。偽代碼表示的算法

用傳統(tǒng)的流程圖和N-S圖表示算法直觀22例如：

x←y

x←20*(y+1)

x←y←30

以上語句用Pascal分別表示為：

x:=y;

x:=20*(y+1);

x:=30;y:=30;

以上語句用C分別表示為：

x=y;

x=20*(y+1);

x=y=30;

例如：

x←y

x←20*(y+1)

x←y←30

232.3.1偽代碼及其分類自然語言描述（如上）通俗、冗長、易“歧義”1）類Pascal偽代碼 簡潔、易實現(xiàn)、不直觀常用語：BEGINENDIF…ELSEFORWHILEDO….2.3.1偽代碼及其分類24例如：求任意兩個數(shù)a和b的和算法： 1）輸入a和b 2）計算a+b，結(jié)果存入sum 3）打印sum用偽代碼表示：

BEGIN INPUTa,b a+b=>sum PRINTa,'+',b,'=',sum END例如：求任意兩個數(shù)a和b的和252)類C偽代碼(1)順序結(jié)構(gòu):…<操作1><操作2>…(2)選擇結(jié)構(gòu)：if<條件>{

執(zhí)行<操作1>}else {<操作2> }(3)循環(huán)結(jié)構(gòu)：直到格式do{<操作>}while<條件>

當型格式while<條件>{<操作>}2)類C偽代碼(1)順序結(jié)構(gòu):…262.3.2用偽代碼描述算法例2-6：求s=1+2+3+……+100問題：求1~100之間各個整數(shù)的和s算法：sum(){y=0,i=1;do{y=y+I;i=i+1;}whilei<=100;printy;}2.3.2用偽代碼描述算法算法：27例2-7:求一個自然數(shù)N的階乘.Factorial(){輸入N的值;y=1,i=2;Whilei<=N{y=y*i;i=i+1;}Print“N!=“,y;}例2-7:求一個自然數(shù)N的階乘.282.3.3偽代碼應用舉例例2-8：求Y=1!+3!+5!+……+49!問題：求1到50之間奇數(shù)的階乘之和.sumforFactorial(){輸入N的值;y=1,s=2,i=3;do{s=s*i;ifINT(i/2)!=i/2;{y=y+s;}i=i+1;}Whilei<=NPrinty;}2.3.3偽代碼應用舉例例2-8：求Y=1!+3!29例2-9：分別求1到N之間各奇數(shù)之和各偶數(shù)之和.Sumforodd&even(){輸入N的值;Odd=0,even=0;i=1;do{ifINT(i/2)=i/2;{even=even+i;}Else{odd=odd+i;}i=i+1;}Whilei<=NPrintodd,even;}例2-9：分別求1到N之間各奇數(shù)之和各偶數(shù)之和.30例2-10：將一個數(shù)組A1,A2,A3…An中的數(shù)據(jù)按從大到小的順序進行排序.Sort(){i=1;Do{j=i+1;Do{ifA(i)<A(j){

交換A(i)與A(j)的值;}j=j+1;}Whilej<=ni=i+1;}Whilei<=n}例2-10：將一個數(shù)組A1,A2,A3…An中的數(shù)據(jù)按從大到31第2章算法及其描述

（程序的靈魂）第2章算法及其描述322.1算法

2.1.1什么是算法？算法是對問題的思維方法和過程體現(xiàn).1.算法的特征:(1)確定性,確定唯一的意義,不能有二意性.(2)有限行,執(zhí)行時有限時間內(nèi)結(jié)束,解決問題.(3)可行性,控制操作是可實現(xiàn)的.2.算法的結(jié)構(gòu):(1)順序結(jié)構(gòu)：<操作1><操作2><操作3>。(2)選擇結(jié)構(gòu)：如果<條件>成立執(zhí)行<操作1>

否則執(zhí)行<操作2>。(3)循環(huán)結(jié)構(gòu)：重復執(zhí)行<操作>直到<條件>成立。2.1算法

2.1.1什么是算法？算法是對問題的思維方332.1.2算法的描述算法是解決問題的方法和步驟在計算機上的表示任何問題的求解都有一定的“算法”計算機算法有很大不同算法是人設(shè)計出來的計算機算法是嚴謹?shù)?不能有二意性.算法可分為兩類：數(shù)值運算算法：主要用于科學運算非數(shù)值運算算法：如信息檢索、人工智能等2.1.2算法的描述算法是解決問題的方法和步驟在計算機上342.1.3算法的舉例:

例：判斷任意整數(shù)n（n≥3）是不是素數(shù)？素數(shù)是只能被1和自身整除（余數(shù)為零）的整數(shù)算法分析：用n做被除數(shù)，依次用2到（n–1）之間的各個整數(shù)做除數(shù)，求所有的余數(shù)，如果所有余數(shù)都不為零，則n為素數(shù)；只要有一個余數(shù)為零就可以斷定n不是素數(shù)算法：1）任意輸入n2）令i=2（i做除數(shù)，i=2,3,...,n-1）3）計算n/i，得余數(shù)r4）若r=0，則打印“n不是素數(shù)”，轉(zhuǎn)到7；否則繼續(xù)5）令i=i+16）若i<n，轉(zhuǎn)到3；否則打印“n是素數(shù)”7）算法結(jié)束2.1.3算法的舉例:

例：判斷任意整數(shù)n（n≥3）35算法的舉例:例2-1：求Y=1!+3!+5!+……+49!問題：求1到50之間奇數(shù)的階乘之和.(1)問題分析:理解奇數(shù)階乘的求和.(2)算法描述:Y表示求和,S表示每一個階乘,I階乘的序號.(3)算法的說明:1)意為Y=1!2)意為S=2!3)令I(lǐng)=34)S=S*I=I!5)INT(I/2)!=I/2I!為奇數(shù)的階乘，加入到Y(jié)中.6)I加1.7)返回4)進行4),5),6)步;直到I=50,輸出結(jié)果算法結(jié)束.算法的舉例:例2-1：求Y=1!+3!+5!+…362.2流程圖2.2.1流程圖及其分類1.傳統(tǒng)流程圖起止框處理框輸入/出框判斷框流程線基本圖件2.2流程圖起止框處理框輸入/出框判斷框流程線基本圖件37三種基本結(jié)構(gòu)（1966年，Bohra和Jacopini提出）（1）順序結(jié)構(gòu)（2）選擇（分支）結(jié)構(gòu)ABC順序結(jié)構(gòu)ABCP二路分支結(jié)構(gòu)三種基本結(jié)構(gòu)（1966年，Bohra和Jacopini提出）38（3）循環(huán)結(jié)構(gòu)當型循環(huán)（先判斷后執(zhí)行，執(zhí)行次數(shù)可能為0）

直到型循環(huán)（先執(zhí)行后判斷，至少執(zhí)行1次）ABCP當型循環(huán)否是ABCP直到型循環(huán)是否（3）循環(huán)結(jié)構(gòu)ABCP當型循環(huán)否是ABCP直到型循環(huán)是否39三種基本結(jié)構(gòu)的特點：只有一個入口只有一個出口具有結(jié)構(gòu)化的特征應避免流程線的交叉三種基本結(jié)構(gòu)的特點：402.N-S盒圖1973年由美國的I.Nassi和B.Shneidermen提出特點：1）不使用流程線（箭頭）；2）全部算法寫在一個大的矩形框內(nèi)；3）搭積木方式，真正的結(jié)構(gòu)化。2.N-S盒圖1973年由美國的I.Nassi和41三種基本結(jié)構(gòu)A操作B操作順序結(jié)構(gòu)P是否AB分支結(jié)構(gòu)P條件滿足A循環(huán)體當型循環(huán)PA直到型循環(huán)只允許“從上邊入，從下邊出”三種基本結(jié)構(gòu)A操作B操作順序結(jié)構(gòu)P是否AB分支結(jié)構(gòu)P條件滿足42輸入nN>=0？輸出-n輸出n例2-2：輸出一個數(shù)的絕對值解題思路：1、判斷n>=0; 2、是輸出n;否則輸出-n.輸入nn>=0？是否輸出n輸出-n輸入nN>=0？輸出-n輸出n例2-2：輸出一個數(shù)的絕對值解43例算法的舉例:例：求s=1+2+3+……+100問題：求100個整數(shù)的和s，結(jié)果是s

這100個整數(shù)是從1到100的所有自然數(shù)算法一：設(shè)s為累加單元1)將1送到S中；2)把2加到S中（即S中的內(nèi)容1加2后再送回S中，下同）3)把3加到S中；……100)把100加到S中；101)把S中的結(jié)果輸出。例算法的舉例:算法一：設(shè)s為累加單元441=>SS+2=>SS+3=>SS+100=>S輸出S例用流程圖與盒圖描述算法1=>SS+2=>SS+3=>S…………S+100=>S輸出S1=>SS+2=>SS+3=>SS+100=>45例：求s=1+2+3+……+100問題：求100個整數(shù)的和s，結(jié)果是s

這100個整數(shù)是從1到100的所有自然數(shù)算法二：設(shè)n為計數(shù)單元，s為累加單元1)將0送到S中，將0送到n中；2)將n+1送到n中，再把n加到s中；3)判斷n的值是否大于等于100？4)若n<100，轉(zhuǎn)到2；否則向下進行；5）輸出s中的內(nèi)容。例：求s=1+2+3+……+100算法二460=>n0=>Sn<100輸出Sn+1=>nS+n=>S例用流程圖與盒圖描述算法0=>S,nn+1=>nS+n=>S輸出Sn<100是否0=>nn<100輸出Sn+1=>n47例2-3輸入10個數(shù)，求它們的平均值。例2-4輸入50個學生成績，統(tǒng)計出不及格的人數(shù)。例2-3輸入10個數(shù)，求它們的平均值。48例求Fibonacci數(shù)列：1，1，2，3，5，8，……的前40個數(shù)。

F1=1(n=1)F2=1(n=2)Fn=Fn-1+Fn-2(n≥3)1534233159710946750255142293524578241578171855377258417711121393832040570288739088169213896104181286571964181346269922746563245986321144987676546368317811217830914930352102334155/*c5_12.c*/#include<stdio.h>main(){longintf1,f2;inti;f1=1;f2=1;

for(i=1;i<=20;i++){printf("%12ld%12ld",f1,f2);if(i%2==0)printf("\n");f1=f1+f2;f2=f2+f1;}}f1=1,f2=1fori=1to20輸出f1,f2f1=f1+f2f2=f2+f1例求Fibonacci數(shù)列：1，1，2，3，5，8，……的49例判斷m是否素數(shù)/*c5_13.c*/#include<stdio.h>#include<math.h>main(){intm,i,k;scanf("%d",&m);k=sqrt(m);

for(i=2;i<=k;i++)if(m%i==0)break;if(i>=k+1)printf("%dis",m);elseprintf("%disnot",m);printf("aprimenumber\n");}例6.9求100~200間的全部素數(shù)讀入mi=2當i≤km被i整除真假用break結(jié)束循環(huán)i=i+1i≥k+1真假輸出:m”是素數(shù)”輸出:m”不是素數(shù)”k=m例判斷m是否素數(shù)/*c5_13.c*/例6.9求10502.2.3流程圖應用舉例例2-5求Y=1!+3!+5!+……+49!問題：求1到50之間奇數(shù)的階乘之和.2.2.3流程圖應用舉例例2-5求Y=1!+3!+512.3偽代碼偽代碼的使用UsageofPseudocode

偽代碼(Pseudocode)是一種算法描述語言。使用為代碼的目的是為了使被描述的算法可以容易地以任何一種編程語言(Pascal,C,Java,etc)實現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰，代碼簡單，可讀性好，并且類似自然語言。

下面介紹一種類偽代碼的語法規(guī)則。

偽代碼的語法規(guī)則

在偽代碼中，每一條指令占一行(elseif例外，)，指令后不跟任何符號（Pascal和C中語句要以分號結(jié)尾）；書寫上的“縮進”表示程序中的分支程序結(jié)構(gòu)。這種縮進風格也適用于if-then-else語句。用縮進取代傳統(tǒng)Pascal中的begin和end語句來表示程序的塊結(jié)構(gòu)可以大大提高代碼的清晰性；同一模塊的語句有相同的縮進量，次一級模塊的語句相對與其父級模塊的語句縮進；2.3偽代碼偽代碼的使用UsageofPseudoco52偽代碼表示的算法

用傳統(tǒng)的流程圖和N-S圖表示算法直觀易懂，但畫起來比較費事，在設(shè)計一個算法時，可能要反復修改，而修改流程圖是比較麻煩的。因此，流程圖適宜于表示一個算法，但在設(shè)計算法過程中使用不是很理想的(尤其是當算法比較復雜、需要反復修改時)。為了設(shè)計算法時方便，常用一種稱為偽代碼的工具。偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。它如同一篇文章一樣，自上而下地寫下來。每一行(或幾行)表示一個基本操作。它不用圖形符號，因此書寫方便、格式緊湊，易懂也便于向計算機語言算法(即程序)過渡?？梢杂糜⑽摹h字、中英文混合表示算法，以便于書寫和閱讀為原則。用偽代碼寫算法并無固定的、嚴格的語法規(guī)則，只要把意思表達清楚，并且書寫的格式要寫成清晰易讀的形式。偽代碼表示的算法

用傳統(tǒng)的流程圖和N-S圖表示算法直觀53例如：

x←y

x←20*(y+1)

x←y←30

以上語句用Pascal分別表示為：

x:=y;

x:=20*(y+1);

x:=30;y:=30;

以上語句用C分別表示為：

x=y;

x=20*(y+1);

x=y=30;

例如：

x←y

x←20*(y+1)

x←y←30

542.3.1偽代碼及其分類自然語言描述（如上）通俗、冗長、易“歧義”1）類Pascal偽代碼 簡潔、易實現(xiàn)、不直觀常用語：BEGINENDIF…ELSEFORWHILEDO….2.3.1偽代碼及其分類55例如：求任意兩個數(shù)a和b的和算法： 1）輸入a和b 2）計算a+b，結(jié)果存入sum 3）打印sum用偽代碼表示：

BEGIN INPUTa,b a+b=>sum PRINTa,'+',b,'=',sum END例如：求任意兩個數(shù)a和b的和562)類C偽代碼(1)順序結(jié)構(gòu):…<操作1><操作2>…(2)選擇