C程序設(shè)計第四譚浩強(qiáng)編教程算法——程序的靈魂實(shí)用教案

1、第一第一(dy)講回顧講回顧C(jī)語言的特點(diǎn)(tdin)C程序的基本結(jié)構(gòu)算法的概念第1頁/共26頁第一頁，共27頁。4 程序設(shè)計程序設(shè)計(chn x sh j)的任務(wù)的任務(wù)問題分析：建模。（條件、目標(biāo)、方法）設(shè)計(shj)算法與數(shù)據(jù)結(jié)構(gòu)：求解步驟，流程圖編程與調(diào)試：編輯和編譯編譯檢查語法錯誤，運(yùn)行、分析檢查邏輯（算法）錯誤編寫程序文檔：開發(fā)者注釋說明和使用者說明第2頁/共26頁第二頁，共27頁。5 書寫程序書寫程序(chngx)時應(yīng)遵循的規(guī)則時應(yīng)遵循的規(guī)則從書寫清晰，便于閱讀，理解，維護(hù)的角度出發(fā)，在書寫程序時應(yīng)遵循以下規(guī)則： 一個說明或一個語句占一行。 用 括起來的部分，通常表示了程序的某一層次

2、結(jié)構(gòu)。一般與該結(jié)構(gòu)語句的第一個字母(zm)對齊，并單獨(dú)占一行。 低一層次的語句或說明可比高一層次的語句或說明縮進(jìn)若干格后書寫。以便看起來更加清晰，增加程序的可讀性。 在編程時應(yīng)力求遵循這些規(guī)則，以養(yǎng)成良好的編程風(fēng)格。第3頁/共26頁第三頁，共27頁。 程序程序(chngx)例例 （1）求正弦(zhngxin)值#include #includeint main() double x,s; printf(input number:n); scanf(%lf,&x); s=sin(x); printf(sine of %lf is %lfn,x,s); return(0); include文件包含

3、命令擴(kuò)展名為.h的文件稱為頭文件定義兩個實(shí)數(shù)變量，以被后面程序使用顯示提示信息從鍵盤獲得一個實(shí)數(shù)x求x的正弦,并把它賦給變量s顯示程序運(yùn)算(yn sun)結(jié)果main函數(shù)結(jié)束第4頁/共26頁第四頁，共27頁。 求兩個(lin )數(shù)之和 #include int main() int a,b,sum; a=123; b=456; sum=a+b; printf(“sum is %d n”,sum); return (0); 第5頁/共26頁第五頁，共27頁。6 程序程序(chngx)的靈魂的靈魂算法算法 一個程序應(yīng)包括： 對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型(lixng)和數(shù)據(jù)的組織形式，即數(shù)

4、據(jù)結(jié)構(gòu) data structure 對操作的描述。即操作步驟，也就是算法 algorithm Nikiklaus Wirth提出的公式： 數(shù)據(jù)結(jié)構(gòu)+算法=程序第6頁/共26頁第六頁，共27頁。算法(sun f)的概念做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。法。計算機(jī)算法：計算機(jī)能夠執(zhí)行計算機(jī)算法：計算機(jī)能夠執(zhí)行(zhxng)的算法。的算法。計算機(jī)算法可分為兩大類：計算機(jī)算法可分為兩大類：數(shù)值運(yùn)算算法：求解數(shù)值；數(shù)值運(yùn)算算法：求解數(shù)值；非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。

5、如何求如何求 sigma（1.n）?第7頁/共26頁第七頁，共27頁。簡單簡單(jindn)算法舉例算法舉例 回顧上一講【例】求5！=12345。 最原始方法： 步驟1：先求12，得到結(jié)果2。 步驟2：將步驟1得到的乘積2乘以3，得到結(jié)果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得120。 這樣(zhyng)的算法雖然正確，但太繁。第8頁/共26頁第八頁，共27頁。 改進(jìn)的算法(sun f)：設(shè)兩個變量，使用循環(huán) S1: 使t=1 S2: 使i=2 S3: 使ti, 乘積仍然放在在變量t中，可表示為tit S4: 使i的值+1，即i+1i S5: 如果i5, 返回重新執(zhí)行步

6、驟S3以及其后的S4和S5；否則，算法(sun f)結(jié)束。第9頁/共26頁第九頁，共27頁。 如果計算100！只需將S5:若i5改成(i chn)i100即可。 如果該求1357911，算法也只需做很少的改動： S1: 1t S2: 3i S3: tit S4: i+2t S5:若i11, 返回S3，否則，結(jié)束。 該算法不僅正確，而且是計算機(jī)較好的算法，因?yàn)橛嬎銠C(jī)是高速運(yùn)算的自動機(jī)器，實(shí)現(xiàn)循環(huán)輕而易舉。 思考：若將 S5寫成：S5:若i11, 返回S3;否則，結(jié)束。第10頁/共26頁第十頁，共27頁。 【例】有50個學(xué)生，要求將他們之中成績在80分以上者打印(d yn)出來。 如果，n表示學(xué)生

7、學(xué)號，ni表示第i個學(xué)生學(xué)號；g表示學(xué)生成績，gi表示第i個學(xué)生成績則算法可表示如下： S1: 1i S2: 如果gi80，則打印(d yn)ni和gi，否則不打印(d yn) S3: i+1i S4:若i50, 返回S2，否則，結(jié)束。 （思考：表示學(xué)生成績需要50個變量嗎？）第11頁/共26頁第十一頁，共27頁。 【例】判定2000 2500年中的每一年是否閏年，將結(jié)果輸出。 潤年的條件： 能被4整除，但不能被100整除的年份； 能被100整除，又能被400整除的年份； 設(shè)y為被檢測的年份，則算法可表示如下： S1: 2000y S2:若y不能被4整除，則輸出y“不是閏年”，然后(rnhu)

8、轉(zhuǎn)到S6 S3:若y能被4整除，不能被100整除，則輸出y“是閏年”，然后(rnhu)轉(zhuǎn)到S6 S4:若y能被100整除，又能被400整除，輸出y“是閏年” 否則輸出y“不是閏年”，然后(rnhu)轉(zhuǎn)到S6 S5:輸出y“不是閏年”。 S6:y+1y S7:當(dāng)y2500時, 返回S2繼續(xù)執(zhí)行，否則，結(jié)束。第12頁/共26頁第十二頁，共27頁。 判斷條件(tiojin)正確才能得到正確結(jié)果； 多個條件(tiojin)的判斷順序有時候是有邏輯關(guān)系的，即順序錯了會得到錯誤結(jié)果。第13頁/共26頁第十三頁，共27頁。 【例】求 算法可表示如下： S1: sign=1/符號項(xiàng) S2: sum=1/累加和

9、 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，返回(fnhu)S4；否則，結(jié)束。1001991.4131211第14頁/共26頁第十四頁，共27頁。 【例】對一個大于或等于3的正整數(shù)，判斷它是不是一個素數(shù)。 算法可表示如下： S1: 輸入n的值 S2: i=2 S3: n被i除，得余數(shù)r S4:如果(rgu)r=0，表示n能被i整除，則打印n“不是素數(shù)”，算法結(jié)束；否則執(zhí)行S5 S5: i+1i S6:如果(rgu)in-

10、1，返回S3；否則打印n“是素數(shù)”；然后算法結(jié)束。 改進(jìn)： S6:如果(rgu)i ，返回S3；否則打印n“是素數(shù)”;然后算法結(jié)束。n第15頁/共26頁第十五頁，共27頁。算法(sun f)的特性有窮性：一個算法應(yīng)包含有限的操作步驟而不能是無限的。有窮性：一個算法應(yīng)包含有限的操作步驟而不能是無限的。 確定性：算法中每一個步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩確定性：算法中每一個步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的?？傻?。有零個或多個輸入。有零個或多個輸入。有一個或多個輸出。有一個或多個輸出。有效性：算法中每一個步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。有效性：算法中每一個步驟應(yīng)

11、當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。對于程序設(shè)計對于程序設(shè)計(shj)人員，必須會設(shè)計人員，必須會設(shè)計(shj)算法，并根據(jù)算法寫出程算法，并根據(jù)算法寫出程序。序。第16頁/共26頁第十六頁，共27頁。用流程圖表示用流程圖表示(biosh)算法算法 統(tǒng)計學(xué)生成績(chngj)的例子第17頁/共26頁第十七頁，共27頁。 判斷(pndun)閏年的例子第18頁/共26頁第十八頁，共27頁。用計算機(jī)語言用計算機(jī)語言(yyn)實(shí)現(xiàn)算法實(shí)現(xiàn)算法 我們的任務(wù)是用計算機(jī)解題，就是用計算機(jī)實(shí)現(xiàn)算法； 用計算機(jī)語言表示(biosh)算法必須嚴(yán)格遵循所用語言的語法規(guī)則。 【例】求12345用C語言表示(biosh)

12、。int main()int i,t; t=1; i=2; while(i=5) t=t*i;i=i+1; printf(“%d”,t); 第19頁/共26頁第十九頁，共27頁。對比：算法對比：算法(sun f)的表示與實(shí)現(xiàn)方式的表示與實(shí)現(xiàn)方式自然語言流程圖偽語言計算機(jī)語言請課后思考(sko)：交換兩個（或兩組）數(shù)據(jù)的值，第20頁/共26頁第二十頁，共27頁。結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計(shj)方法方法 N。Wirth 公式：數(shù)據(jù)結(jié)構(gòu)( jigu)+算法=程序 即 結(jié)構(gòu)( jigu)特性設(shè)計 + 過程特性設(shè)計 結(jié)構(gòu)( jigu)化程序設(shè)計：面向過程 （分別考慮數(shù)據(jù)和過程） 【注】面向?qū)ο蟪绦?/p>

13、設(shè)計：面向?qū)ο螅〝?shù)據(jù)和過程的封裝） 結(jié)構(gòu)( jigu)化算法 由基本結(jié)構(gòu)( jigu)順序組成的算法結(jié)構(gòu)( jigu)，在基本結(jié)構(gòu)( jigu)之間不存在向前或向后的跳轉(zhuǎn)第21頁/共26頁第二十一頁，共27頁。 結(jié)構(gòu)化程序設(shè)計方法 自頂向下 逐步細(xì)化 模塊化設(shè)計 結(jié)構(gòu)化編碼 核心思想是算法設(shè)計：自頂向下、逐步細(xì)化- 講一個復(fù)雜任務(wù)逐步分拆，逐層細(xì)化到便于(biny)理解和描述的程度；最終形成一個由若干獨(dú)立模塊組成的樹狀層次結(jié)構(gòu)第22頁/共26頁第二十二頁，共27頁。第23頁/共26頁第二十三頁，共27頁。第24頁/共26頁第二十四頁，共27頁。Questions？ 作業(yè)(zuy)： 15頁： 5，6 36頁： 4-（3）； 4-（5）第25頁/共26頁第二十五頁，共27頁。謝謝您的觀看(gunkn)！第26頁/共26頁第二十六頁，共27