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

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,第,*,頁(yè),Click to edit Master title style,中國(guó)科學(xué)技術(shù)大學(xué),C,語(yǔ)言程序設(shè)計(jì)講義,2010,C,程序設(shè)計(jì),Liu Yong Dept.23 USTC,2010,第一講回顧,C,語(yǔ)言的特點(diǎn),C,程序的基本結(jié)構(gòu),算法的概念,4,程序設(shè)計(jì)的任務(wù),問(wèn)題分析：建模。（條件、目標(biāo)、方法）,設(shè)計(jì)算法與數(shù)據(jù)結(jié)構(gòu)：求解步驟，流程圖,編程與調(diào)試：,編輯和編譯,編譯檢查語(yǔ)法錯(cuò)誤，運(yùn)行、分析檢查邏輯（算法）錯(cuò)誤,編寫程序文檔：開發(fā)者注釋說(shuō)明和使用者說(shuō)明,5,書寫程序時(shí)應(yīng)遵循的規(guī)則,從書寫清晰，便于閱讀，理解，維護(hù)的角度出發(fā)，,在書寫程序時(shí)應(yīng)遵循以下規(guī)則：,一個(gè)說(shuō)明或一個(gè)語(yǔ)句占一行。,用,括起來(lái)的部分，通常表示了程序的某一層次結(jié)構(gòu)。,一般與該結(jié)構(gòu)語(yǔ)句的第一個(gè)字母對(duì)齊，并單獨(dú)占一行。,低一層次的語(yǔ)句或說(shuō)明可比高一層次的語(yǔ)句或說(shuō)明縮進(jìn)若干格后書寫。以便看起來(lái)更加清晰，增加程序的可讀性。,在編程時(shí)應(yīng)力求遵循這些規(guī)則，以養(yǎng)成良好的編程風(fēng)格。,程序例 （,1,）,求正弦值,#include,#include,int,main(),double,x,s,;,printf(input,number:n);,scanf(%lf,&x,);,s=,sin(x,);,printf(sine,of%lf is%lf,n,x,s,);,return(0);,include,文件包含,命令,擴(kuò)展名為,.h,的文件稱為頭文件,定義兩個(gè)實(shí)數(shù)變量，以被后面程序使用,顯示提示信息,從鍵盤獲得一個(gè)實(shí)數(shù),x,求,x,的正弦,并把它賦給變量,s,顯示程序運(yùn)算結(jié)果,main,函數(shù)結(jié)束,求兩個(gè)數(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,程序的靈魂,算法,一個(gè)程序應(yīng)包括：,對(duì)數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu),data structure,對(duì)操作的描述。即操作步驟，也就是算法,algorithm,Nikiklaus,Wirth,提出的公式：,數(shù)據(jù)結(jié)構(gòu),+,算法,=,程序,算法的概念,做任何事情都有一定的步驟。為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為算法。,計(jì)算機(jī)算法：計(jì)算機(jī)能夠執(zhí)行的算法。,計(jì)算機(jī)算法可分為兩大類：,數(shù)值運(yùn)算算法：求解數(shù)值；,非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。,如何求,sigma,（,1.n,）,?,簡(jiǎn)單算法舉例,回顧上一講,【,例,】,求,5,！,=12345,。,最原始方法：,步驟,1,：先求,12,，得到結(jié)果,2,。,步驟,2,：將步驟,1,得到的乘積,2,乘以,3,，得到結(jié)果,6,。,步驟,3,：將,6,再乘以,4,，得,24,。,步驟,4,：將,24,再乘以,5,，得,120,。,這樣的算法雖然正確，但太繁。,改進(jìn)的算法：設(shè)兩個(gè)變量，使用循環(huán),S1:,使,t=1,S2:,使,i=2,S3:,使,ti,乘積仍然放在在變量,t,中，可表示為,tit,S4:,使,i,的值,+1,，即,i+1i,S5:,如果,i5,返回重新執(zhí)行步驟,S3,以及其后的,S4,和,S5,；否則，算法結(jié)束。,如果計(jì)算,100,！只需將,S5:,若,i5,改成,i100,即可。,如果該求,1357911,，算法也只需做很少的改動(dòng)：,S1:1t,S2:3i,S3:,tit,S4:i+2t,S5:,若,i11,返回,S3,，否則，結(jié)束。,該算法不僅正確，而且是計(jì)算機(jī)較好的算法，因?yàn)橛?jì)算機(jī)是高速運(yùn)算的自動(dòng)機(jī)器，實(shí)現(xiàn)循環(huán)輕而易舉。,思考：若將,S5,寫成：,S5:,若,i,11,返回,S3;,否則，結(jié)束。,【,例,】,有,50,個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?80,分以上者打印出來(lái)。,如果，,n,表示學(xué)生學(xué)號(hào)，,n,i,表示第個(gè)學(xué)生學(xué)號(hào)；,g,表示學(xué)生成績(jī)，,g,i,表示第個(gè)學(xué)生成績(jī)則算法可表示如下：,S1:1i,S2:,如果,g,i,80,，則打印,n,i,和,g,i,，否則不打印,S3:i+1i,S4:,若,i50,返回,S2,，否則，結(jié)束。,（思考：表示學(xué)生成績(jī)需要,50,個(gè)變量嗎？）,【,例,】,判定,2000 2500,年中的每一年是否閏年，將結(jié)果輸出。,潤(rùn)年的條件：,能被,4,整除，但不能被,100,整除的年份；,能被,100,整除，又能被,400,整除的年份；,設(shè),y,為被檢測(cè)的年份，則算法可表示如下：,S1:2000y,S2:,若,y,不能被,4,整除，則輸出,y“,不是閏年”，然后轉(zhuǎn)到,S6,S3:,若,y,能被,4,整除，不能被,100,整除，則輸出,y“,是閏年”，然后轉(zhuǎn)到,S6,S4:,若,y,能被,100,整除，又能被,400,整除，輸出,y“,是閏年”否則輸出,y“,不是閏年”，然后轉(zhuǎn)到,S6,S5:,輸出,y“,不是閏年”。,S6:y+1y,S7:,當(dāng),y2500,時(shí),返回,S2,繼續(xù)執(zhí)行，否則，結(jié)束。,判斷條件正確才能得到正確結(jié)果；,多個(gè)條件的判斷順序有時(shí)候是有邏輯關(guān)系的，即順序錯(cuò)了會(huì)得到錯(cuò)誤結(jié)果。,【,例,】,求,算法可表示如下：,S1:sign=1/,符號(hào)項(xiàng),S2:sum=1/,累加和,S3:,deno,=2 /,分母,S4:sign=(-1)sign,S5:term=sign(1/deno)/,當(dāng)前項(xiàng),S6:,sum=,sum+term,S7:,deno,=,deno,+1,S8:,若,deno100,，返回,S4,；否則，結(jié)束。,【,例,】,對(duì)一個(gè)大于或等于,3,的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。,算法可表示如下：,S1:,輸入,n,的值,S2:i=2,S3:n,被,i,除，得余數(shù),r,S4:,如果,r=0,，表示,n,能被,i,整除，則打印,n“,不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行,S5,S5:i+1i,S6:,如果,in-1,，返回,S3,；否則打印,n“,是素?cái)?shù)”；然后算法結(jié)束。,改進(jìn)：,S6:,如果,i,，返回,S3,；否則打印,n“,是素?cái)?shù)”,;,然后算法結(jié)束。,算法的特性,有窮性：一個(gè)算法應(yīng)包含有限的操作步驟而不能是無(wú)限的。,確定性：算法中每一個(gè)步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。,有零個(gè)或多個(gè)輸入。,有一個(gè)或多個(gè)輸出。,有效性：算法中每一個(gè)步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。,對(duì)于程序設(shè)計(jì)人員，必須會(huì)設(shè)計(jì)算法，并根據(jù)算法寫出程序。,用流程圖表示算法,統(tǒng)計(jì)學(xué)生成績(jī)的例子,判斷閏年的例子,用計(jì)算機(jī)語(yǔ)言實(shí)現(xiàn)算法,我們的任務(wù)是用計(jì)算機(jī)解題，就是用計(jì)算機(jī)實(shí)現(xiàn)算法；,用計(jì)算機(jī)語(yǔ)言表示算法必須嚴(yán)格遵循所用語(yǔ)言的語(yǔ)法規(guī)則。,【,例,】,求,12345,用,C,語(yǔ)言表示。,int,main(),int,i,t,;,t=1;,i=2;,while(i,=5),t=t*i;,i=i+1;,printf(“%d”,t);,對(duì)比：算法的表示與實(shí)現(xiàn)方式,自然語(yǔ)言,流程圖,偽語(yǔ)言,計(jì)算機(jī)語(yǔ)言,請(qǐng)課后思考：交換兩個(gè)（或兩組）數(shù)據(jù)的值，,結(jié)構(gòu)化程序設(shè)計(jì)方法,N,。,Wirth,公式：,數(shù)據(jù)結(jié)構(gòu),+,算法,=,程序,即,結(jié)構(gòu)特性設(shè)計(jì),+,過(guò)程特性設(shè)計(jì),結(jié)構(gòu)化程序設(shè)計(jì)：面向,過(guò)程 （分別考慮數(shù)據(jù)和過(guò)程）,【,注,】,面向?qū)ο蟪绦蛟O(shè)計(jì)：面向?qū)ο螅〝?shù)據(jù)和過(guò)程的封裝）,結(jié)構(gòu)化算法,由基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn),結(jié)構(gòu)化程序設(shè)計(jì)方法,自頂向下,逐步細(xì)化,模塊化設(shè)計(jì),結(jié)構(gòu)化編碼,核心思想是算法設(shè)計(jì)：自頂向下、逐步細(xì)化,-,講一個(gè)復(fù)雜任務(wù)逐步分拆，逐層細(xì)化到便于理解和描述的程度；最終形成一個(gè)由若干獨(dú)立模塊組成的樹狀層次結(jié)構(gòu),Questions,？,作業(yè)：,15,頁(yè)：,5,，,6,36,頁(yè)：,4-,（,3,）；,4-,（,5,）,