C程序設(shè)計(第四版)(譚浩強(qiáng)編)教程-第2章 算法——程序的靈魂

《C程序設(shè)計(第四版)(譚浩強(qiáng)編)教程-第2章 算法——程序的靈魂》由會員分享，可在線閱讀，更多相關(guān)《C程序設(shè)計(第四版)(譚浩強(qiáng)編)教程-第2章 算法——程序的靈魂（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,第,*,頁,Click to edit Master title style,中國科學(xué)技術(shù)大學(xué),C,語言程序設(shè)計講義,2010,C,程序設(shè)計,Liu Yong Dept.23 USTC,2010,第一講回顧,C,語言的特點,C,程序的基本結(jié)構(gòu),算法的概念,4,程序設(shè)計的任務(wù),問題分析：建模。（條件、目標(biāo)、方法）,設(shè)計算法與數(shù)據(jù)結(jié)構(gòu)：求解步驟，流程圖,編程與調(diào)試：,編輯和編譯,編譯檢查語法錯誤，運行、分析檢查邏輯（算法）錯誤,編寫程

2、序文檔：開發(fā)者注釋說明和使用者說明,5,書寫程序時應(yīng)遵循的規(guī)則,從書寫清晰，便于閱讀，理解，維護(hù)的角度出發(fā)，,在書寫程序時應(yīng)遵循以下規(guī)則：,一個說明或一個語句占一行。,用,括起來的部分，通常表示了程序的某一層次結(jié)構(gòu)。,一般與該結(jié)構(gòu)語句的第一個字母對齊，并單獨占一行。,低一層次的語句或說明可比高一層次的語句或說明縮進(jìn)若干格后書寫。以便看起來更加清晰，增加程序的可讀性。,在編程時應(yīng)力求遵循這些規(guī)則，以養(yǎng)成良好的編程風(fēng)格。,程序例 （,1,）,求正弦值,#include,#include,int,main(),double,x,s,;,printf(input,number:n);,scanf(%l

3、f,&x,);,s=,sin(x,);,printf(sine,of%lf is%lf,n,x,s,);,return(0);,include,文件包含,命令,擴(kuò)展名為,.h,的文件稱為頭文件,定義兩個實數(shù)變量，以被后面程序使用,顯示提示信息,從鍵盤獲得一個實數(shù),x,求,x,的正弦,并把它賦給變量,s,顯示程序運算結(jié)果,main,函數(shù)結(jié)束,求兩個數(shù)之和,#include,int,main(),int,a,b,sum,;,a=123;,b=456;,sum=,a+b,;,printf(“sum,is%d,n”,sum,);,return(0);,程序例 （,2,）,6,程序的靈魂,算法,一個程序

4、應(yīng)包括：,對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu),data structure,對操作的描述。即操作步驟，也就是算法,algorithm,Nikiklaus,Wirth,提出的公式：,數(shù)據(jù)結(jié)構(gòu),+,算法,=,程序,算法的概念,做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。,計算機(jī)算法：計算機(jī)能夠執(zhí)行的算法。,計算機(jī)算法可分為兩大類：,數(shù)值運算算法：求解數(shù)值；,非數(shù)值運算算法：事務(wù)管理領(lǐng)域。,如何求,sigma,（,1.n,）,?,簡單算法舉例,回顧上一講,【,例,】,求,5,！,=12345,。,最原始方法：,步驟,1,：先求,12,，得到

5、結(jié)果,2,。,步驟,2,：將步驟,1,得到的乘積,2,乘以,3,，得到結(jié)果,6,。,步驟,3,：將,6,再乘以,4,，得,24,。,步驟,4,：將,24,再乘以,5,，得,120,。,這樣的算法雖然正確，但太繁。,改進(jìn)的算法：設(shè)兩個變量，使用循環(huán),S1:,使,t=1,S2:,使,i=2,S3:,使,ti,乘積仍然放在在變量,t,中，可表示為,tit,S4:,使,i,的值,+1,，即,i+1i,S5:,如果,i5,返回重新執(zhí)行步驟,S3,以及其后的,S4,和,S5,；否則，算法結(jié)束。,如果計算,100,！只需將,S5:,若,i5,改成,i100,即可。,如果該求,1357911,，算法也只需做很

6、少的改動：,S1:1t,S2:3i,S3:,tit,S4:i+2t,S5:,若,i11,返回,S3,，否則，結(jié)束。,該算法不僅正確，而且是計算機(jī)較好的算法，因為計算機(jī)是高速運算的自動機(jī)器，實現(xiàn)循環(huán)輕而易舉。,思考：若將,S5,寫成：,S5:,若,i,11,返回,S3;,否則，結(jié)束。,【,例,】,有,50,個學(xué)生，要求將他們之中成績在,80,分以上者打印出來。,如果，,n,表示學(xué)生學(xué)號，,n,i,表示第個學(xué)生學(xué)號；,g,表示學(xué)生成績，,g,i,表示第個學(xué)生成績則算法可表示如下：,S1:1i,S2:,如果,g,i,80,，則打印,n,i,和,g,i,，否則不打印,S3:i+1i,S4:,若,i50

7、,返回,S2,，否則，結(jié)束。,（思考：表示學(xué)生成績需要,50,個變量嗎？）,【,例,】,判定,2000 2500,年中的每一年是否閏年，將結(jié)果輸出。,潤年的條件：,能被,4,整除，但不能被,100,整除的年份；,能被,100,整除，又能被,400,整除的年份；,設(shè),y,為被檢測的年份，則算法可表示如下：,S1:2000y,S2:,若,y,不能被,4,整除，則輸出,y“,不是閏年”，然后轉(zhuǎn)到,S6,S3:,若,y,能被,4,整除，不能被,100,整除，則輸出,y“,是閏年”，然后轉(zhuǎn)到,S6,S4:,若,y,能被,100,整除，又能被,400,整除，輸出,y“,是閏年”否則輸出,y“,不是閏年”，

8、然后轉(zhuǎn)到,S6,S5:,輸出,y“,不是閏年”。,S6:y+1y,S7:,當(dāng),y2500,時,返回,S2,繼續(xù)執(zhí)行，否則，結(jié)束。,判斷條件正確才能得到正確結(jié)果；,多個條件的判斷順序有時候是有邏輯關(guān)系的，即順序錯了會得到錯誤結(jié)果。,【,例,】,求,算法可表示如下：,S1:sign=1/,符號項,S2:sum=1/,累加和,S3:,deno,=2 /,分母,S4:sign=(-1)sign,S5:term=sign(1/deno)/,當(dāng)前項,S6:,sum=,sum+term,S7:,deno,=,deno,+1,S8:,若,deno100,，返回,S4,；否則，結(jié)束。,【,例,】,對一個大于或等

9、于,3,的正整數(shù)，判斷它是不是一個素數(shù)。,算法可表示如下：,S1:,輸入,n,的值,S2:i=2,S3:n,被,i,除，得余數(shù),r,S4:,如果,r=0,，表示,n,能被,i,整除，則打印,n“,不是素數(shù)”，算法結(jié)束；否則執(zhí)行,S5,S5:i+1i,S6:,如果,in-1,，返回,S3,；否則打印,n“,是素數(shù)”；然后算法結(jié)束。,改進(jìn)：,S6:,如果,i,，返回,S3,；否則打印,n“,是素數(shù)”,;,然后算法結(jié)束。,算法的特性,有窮性：一個算法應(yīng)包含有限的操作步驟而不能是無限的。,確定性：算法中每一個步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。,有零個或多個輸入。,有一個或多個輸出。,有

10、效性：算法中每一個步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。,對于程序設(shè)計人員，必須會設(shè)計算法，并根據(jù)算法寫出程序。,用流程圖表示算法,統(tǒng)計學(xué)生成績的例子,判斷閏年的例子,用計算機(jī)語言實現(xiàn)算法,我們的任務(wù)是用計算機(jī)解題，就是用計算機(jī)實現(xiàn)算法；,用計算機(jī)語言表示算法必須嚴(yán)格遵循所用語言的語法規(guī)則。,【,例,】,求,12345,用,C,語言表示。,int,main(),int,i,t,;,t=1;,i=2;,while(i,=5),t=t*i;,i=i+1;,printf(“%d”,t);,對比：算法的表示與實現(xiàn)方式,自然語言,流程圖,偽語言,計算機(jī)語言,請課后思考：交換兩個（或兩組）數(shù)據(jù)的值，,結(jié)

11、構(gòu)化程序設(shè)計方法,N,。,Wirth,公式：,數(shù)據(jù)結(jié)構(gòu),+,算法,=,程序,即,結(jié)構(gòu)特性設(shè)計,+,過程特性設(shè)計,結(jié)構(gòu)化程序設(shè)計：面向,過程 （分別考慮數(shù)據(jù)和過程）,【,注,】,面向?qū)ο蟪绦蛟O(shè)計：面向?qū)ο螅〝?shù)據(jù)和過程的封裝）,結(jié)構(gòu)化算法,由基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn),結(jié)構(gòu)化程序設(shè)計方法,自頂向下,逐步細(xì)化,模塊化設(shè)計,結(jié)構(gòu)化編碼,核心思想是算法設(shè)計：自頂向下、逐步細(xì)化,-,講一個復(fù)雜任務(wù)逐步分拆，逐層細(xì)化到便于理解和描述的程度；最終形成一個由若干獨立模塊組成的樹狀層次結(jié)構(gòu),Questions,？,作業(yè)：,15,頁：,5,，,6,36,頁：,4-,（,3,）；,4-,（,5,）,