第2章算法及其描述課件

第2章算法及其描述

（程序的靈魂）2.1算法

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

否則執(zhí)行<操作2>。(3)循環(huán)結構：重復執(zhí)行<操作>直到<條件>成立。2.1.2算法的描述算法是解決問題的方法和步驟在計算機上的表示任何問題的求解都有一定的“算法”計算機算法有很大不同算法是人設計出來的計算機算法是嚴謹的,不能有二意性.算法可分為兩類：數值運算算法：主要用于科學運算非數值運算算法：如信息檢索、人工智能等2.1.3算法的舉例:

例：判斷任意整數n（n≥3）是不是素數？素數是只能被1和自身整除（余數為零）的整數算法分析：用n做被除數，依次用2到（n–1）之間的各個整數做除數，求所有的余數，如果所有余數都不為零，則n為素數；只要有一個余數為零就可以斷定n不是素數算法：1）任意輸入n2）令i=2（i做除數，i=2,3,...,n-1）3）計算n/i，得余數r4）若r=0，則打印“n不是素數”，轉到7；否則繼續(xù)5）令i=i+16）若i<n，轉到3；否則打印“n是素數”7）算法結束算法的舉例:例2-1：求Y=1!+3!+5!+……+49!問題：求1到50之間奇數的階乘之和.(1)問題分析:理解奇數階乘的求和.(2)算法描述:Y表示求和,S表示每一個階乘,I階乘的序號.(3)算法的說明:1)意為Y=1!2)意為S=2!3)令I=34)S=S*I=I!5)INT(I/2)!=I/2I!為奇數的階乘，加入到Y中.6)I加1.7)返回4)進行4),5),6)步;直到I=50,輸出結果算法結束.2.2流程圖2.2.1流程圖及其分類1.傳統(tǒng)流程圖起止框處理框輸入/出框判斷框流程線基本圖件三種基本結構（1966年，Bohra和Jacopini提出）（1）順序結構（2）選擇（分支）結構ABC順序結構ABCP二路分支結構（3）循環(huán)結構當型循環(huán)（先判斷后執(zhí)行，執(zhí)行次數可能為0）

直到型循環(huán)（先執(zhí)行后判斷，至少執(zhí)行1次）ABCP當型循環(huán)否是ABCP直到型循環(huán)是否三種基本結構的特點：只有一個入口只有一個出口具有結構化的特征應避免流程線的交叉2.N-S盒圖1973年由美國的I.Nassi

和B.Shneidermen

提出特點：1）不使用流程線（箭頭）；2）全部算法寫在一個大的矩形框內；3）搭積木方式，真正的結構化。三種基本結構A操作B操作順序結構P是否AB分支結構P條件滿足A循環(huán)體當型循環(huán)PA直到型循環(huán)只允許“從上邊入，從下邊出”輸入nN>=0？輸出-n輸出n例2-2：輸出一個數的絕對值解題思路：1、判斷n>=0; 2、是輸出n;否則輸出-n.輸入nn>=0？是否輸出n輸出-n例

算法的舉例:例：求s=1+2+3+……+100問題：求100個整數的和s，結果是s

這100個整數是從1到100的所有自然數算法一：設s為累加單元1)將1送到S中；2)把2加到S中（即S中的內容1加2后再送回S中，下同）3)把3加到S中；……100)把100加到S中；101)把S中的結果輸出。1=>SS+2=>SS+3=>SS+100=>S輸出S例

用流程圖與盒圖描述算法1=>SS+2=>SS+3=>S…………S+100=>S輸出S例：求s=1+2+3+……+100問題：求100個整數的和s，結果是s

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

求Fibonacci數列：1，1，2，3，5，8，……的前40個數。

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例

判斷m是否素數/*c5_13.c*/#include<stdio.h>#include<math.h>main(){int

m,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間的全部素數讀入mi=2當i≤km被i整除真假用break結束循環(huán)i=i+1i≥k+1真假輸出:m”是素數”輸出:m”不是素數”k=m2.2.3流程圖應用舉例例2-5求Y=1!+3!+5!+……+49!問題：求1到50之間奇數的階乘之和.2.3偽代碼偽代碼的使用UsageofPseudocode

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

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

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

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

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

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;

2.3.1偽代碼及其分類自然語言描述（如上）通俗、冗長、易“歧義”1）類Pascal偽代碼

簡潔、易實現、不直觀常用語：BEGINENDIF…ELSEFORWHILEDO….例如：求任意兩個數a和b的和算法： 1）輸入a和b 2）計算a+b，結果存入sum 3）打印sum用偽代碼表示：

BEGIN INPUTa,b a+b=>sum PRINTa,'+',b,'=',sum END2)類C偽代碼(1)順序結構:…<操作1><操作2>…(2)選擇結構：if<條件>{

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

當型格式while<條件>{<操作>}2.3.2用偽代碼描述算法例2-6：求s=1+2+3+……+100問題：求1~100之間各個整數的和s算法：sum(){y=0,i=1;do{y=y+I;i=i+1;}whilei<=100;printy;}例2-7:求一個自然數N的階乘.Factorial(){輸入N的值;y=1,i=2;Whilei<=N{y=y*i;i=i+1;}Print“