第章算法和基本程序設(shè)計(jì)ppt課件

1、第3章 算法和根本程序設(shè)計(jì) 3.1 算法的概念算法的概念 3.2 構(gòu)造化程序設(shè)計(jì)方法構(gòu)造化程序設(shè)計(jì)方法 3.3 程序的根本構(gòu)造程序的根本構(gòu)造 3.4 順序構(gòu)造程序設(shè)計(jì)順序構(gòu)造程序設(shè)計(jì) 3.5 數(shù)據(jù)的輸入輸出數(shù)據(jù)的輸入輸出 3.6 C程序的上機(jī)步驟程序的上機(jī)步驟3.1 算法的概念 1.定義: 做任何事情都有一定的步驟。為處理一個(gè)問(wèn)題而采取的方法和步驟，就稱為算法。 2.計(jì)算機(jī)算法可分為兩大類： 數(shù)值運(yùn)算算法：求解數(shù)值； 非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。一個(gè)著名的公式一個(gè)著名的公式 數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造+ +算法算法= =程序程序 數(shù)據(jù)：計(jì)算機(jī)所能識(shí)別、存儲(chǔ)和數(shù)據(jù)：計(jì)算機(jī)所能識(shí)別、存儲(chǔ)和處置的對(duì)象。數(shù)據(jù)

2、的動(dòng)態(tài)性。處置的對(duì)象。數(shù)據(jù)的動(dòng)態(tài)性。 數(shù)據(jù)構(gòu)造：確定數(shù)據(jù)對(duì)象及其存數(shù)據(jù)構(gòu)造：確定數(shù)據(jù)對(duì)象及其存儲(chǔ)方式，并定義在這些數(shù)據(jù)對(duì)象儲(chǔ)方式，并定義在這些數(shù)據(jù)對(duì)象上的運(yùn)算集合。上的運(yùn)算集合。 算法：為處理一個(gè)問(wèn)題而采取的算法：為處理一個(gè)問(wèn)題而采取的方法和步驟。方法和步驟。 算法的特性 1 1 有窮性有窮性 操作步驟是有限的，不是無(wú)限的。操作步驟是有限的，不是無(wú)限的。 2 2 確定性確定性 每個(gè)步驟是確定的，無(wú)歧義性。每個(gè)步驟是確定的，無(wú)歧義性。 3 3 有零個(gè)或多個(gè)輸入有零個(gè)或多個(gè)輸入 4 4 有一個(gè)或多個(gè)輸出有一個(gè)或多個(gè)輸出 5 5 有效性有效性 每一步驟能有效執(zhí)行，并得到確定結(jié)果。每一步驟能有效執(zhí)行，

3、并得到確定結(jié)果。 3.1.2 算法的評(píng)價(jià)規(guī)范 1. 正確性 對(duì)任何合法的輸入，算法都會(huì)得出正確的結(jié)果。 2. 可讀性 可讀性指算法被了解的難易程度。 3. 強(qiáng)壯性魯棒性 強(qiáng)壯性即對(duì)非法輸入的抵抗才干。 4. 高效率與低存儲(chǔ)量需求 通常，效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間，兩者都與問(wèn)題的規(guī)模有關(guān)。二者往往是一對(duì)矛盾，經(jīng)常可以用空間換時(shí)間，也可以用時(shí)間換空間。 怎樣表示一個(gè)算法用自然言語(yǔ)表示算法用自然言語(yǔ)表示算法用流程圖表示算法用流程圖表示算法用用N-S流程圖表示算法流程圖表示算法用偽代碼表示算法用偽代碼表示算法用計(jì)算機(jī)言語(yǔ)表示算法用計(jì)算機(jī)言語(yǔ)表示算法 歧義性，描

4、畫(huà)分支、循環(huán)算法不方便歧義性，描畫(huà)分支、循環(huán)算法不方便起止框起止框輸入輸出框輸入輸出框處置框處置框判別框判別框流程線流程線銜接點(diǎn)銜接點(diǎn) 【例3.1】 求三個(gè)整數(shù)的和。 求三個(gè)整數(shù)和的算法流程圖如下圖。開(kāi)場(chǎng)x+y+z = sum輸出sum 的值終了輸入x,y,z圖3.2 求三個(gè)整數(shù)和的算法【例3.2】 求最大公約數(shù)。m,n為正整數(shù)開(kāi)場(chǎng)終了輸入m,n求m/n的余數(shù)rr = 0 ?n =m, r =n輸出n是否最大公因數(shù)的算法求最大公因數(shù)的最普遍的算法是歐幾里得算法，它最初是公元前由歐幾里得提出來(lái)的，有時(shí)也稱它為輾轉(zhuǎn)相除法表述如下：設(shè)給定m，n(mn)，令r0=m，r1=n，有 那么得rk=gcd(

5、rk-1，rk)=gcd(rk-2，rk-1)=gcd(r2，r3)=gcd(r1，r2)=gcd(r0，r1)=gcd(m，n)b|a 表示b整除a或者a整除以b 那么 a是b的倍數(shù)，b是a的約數(shù)rk-2 = qk-1 qk rk + rk =(qk-1 qk +1) rk S1: 求求12=2 S2: 求求23=6 S3: 求求64=24 天?。」残杼彀?！共需999個(gè)步驟，太可個(gè)步驟，太可怕了。怕了。案例案例 求求12341000 S1: 1 p (p:被乘數(shù)被乘數(shù)) S2: 2 i (i:乘數(shù)乘數(shù)) S3: pi p S4: i+1 i S5: 假設(shè)假設(shè)i1000,前往前往S3；否那么，

6、終了。；否那么，終了。 只需只需5個(gè)步驟，簡(jiǎn)單。個(gè)步驟，簡(jiǎn)單。3.2 構(gòu)造化程序設(shè)計(jì)的方法 構(gòu)造化程序設(shè)計(jì)思想采用了模塊分解與功能籠統(tǒng)和自頂向下、分而治之的方法，從而有效地將一個(gè)較復(fù)雜的程序系統(tǒng)設(shè)計(jì)義務(wù)分解成許多易于控制和處置的子程序，便于開(kāi)發(fā)和維護(hù)，減少程序的出錯(cuò)概率和提高軟件的開(kāi)發(fā)效率。 采用構(gòu)造化程序設(shè)計(jì)方法應(yīng)遵照以下原那么。 1. 自頂向下 即在程序設(shè)計(jì)時(shí)，先思索總體，做出全局設(shè)計(jì)，然后再思索細(xì)節(jié)進(jìn)展部分設(shè)計(jì)，逐漸實(shí)現(xiàn)精細(xì)化。這種方法稱為“自頂向下，逐漸細(xì)化的方法。 2. 模塊化 就是將一個(gè)大義務(wù)分成假設(shè)干個(gè)較小的部分，每一部分承當(dāng)一定的功能，稱為“功能模塊。每個(gè)模塊可以分別編程和調(diào)試

7、，然后組成一個(gè)完好的程序。模塊的劃分應(yīng)遵照一些根本原那么，如模塊內(nèi)部聯(lián)絡(luò)要嚴(yán)密，關(guān)聯(lián)程度要高；模塊間的接口要盡能夠簡(jiǎn)單，以減少模塊間的數(shù)據(jù)傳送。 3. 限制運(yùn)用GOTO語(yǔ)句 構(gòu)造化的程序設(shè)計(jì)方法構(gòu)造化的程序設(shè)計(jì)方法 根本思緒根本思緒: 把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段進(jìn)展分階段進(jìn)展,每個(gè)階段處置的問(wèn)題都控制每個(gè)階段處置的問(wèn)題都控制在人們?nèi)菀琢私夂吞幹玫姆秶鷥?nèi)在人們?nèi)菀琢私夂吞幹玫姆秶鷥?nèi). 采用的方法采用的方法: 1 自頂而下自頂而下 2 逐漸細(xì)化逐漸細(xì)化 3 模塊化設(shè)計(jì)模塊化設(shè)計(jì) 4 構(gòu)造化編碼構(gòu)造化編碼三種根本構(gòu)造三種根本構(gòu)造 1 1 順序構(gòu)造順序構(gòu)造 2 2 選擇構(gòu)造

8、選擇構(gòu)造 3 3 循環(huán)構(gòu)造循環(huán)構(gòu)造3.3 程序的根本構(gòu)造程序的根本構(gòu)造三種根本構(gòu)造的特點(diǎn)三種根本構(gòu)造的特點(diǎn) 1 1 只需一個(gè)入口只需一個(gè)入口 2 2 只需一個(gè)出口只需一個(gè)出口pA 3 3 構(gòu)造內(nèi)的每一部分都有時(shí)機(jī)被執(zhí)行到構(gòu)造內(nèi)的每一部分都有時(shí)機(jī)被執(zhí)行到AB 4 4 構(gòu)造內(nèi)沒(méi)有死循環(huán)構(gòu)造內(nèi)沒(méi)有死循環(huán)順序構(gòu)造的流程圖符號(hào)順序構(gòu)造的流程圖符號(hào)ABabAB傳統(tǒng)流程圖傳統(tǒng)流程圖N-S流程圖流程圖選擇構(gòu)造的流程圖符號(hào)選擇構(gòu)造的流程圖符號(hào)Ap成立不成立BAp成立不成立傳統(tǒng)流程圖傳統(tǒng)流程圖選擇構(gòu)造的流程圖符號(hào)續(xù)選擇構(gòu)造的流程圖符號(hào)續(xù)成立不成立ApBN-S流程圖流程圖循環(huán)構(gòu)造的流程圖符號(hào)循環(huán)構(gòu)造的流程圖符號(hào)Ap

9、1成立不成立ab不成立Ap2成立ab傳統(tǒng)流程圖傳統(tǒng)流程圖While型型Until型型循環(huán)構(gòu)造的流程圖符號(hào)續(xù)循環(huán)構(gòu)造的流程圖符號(hào)續(xù)直到直到p1成立成立A當(dāng)當(dāng)p1成立成立AWhile型型Until型型N-S流程圖流程圖一個(gè)有用的結(jié)論一個(gè)有用的結(jié)論 曾經(jīng)證明：曾經(jīng)證明： 三種根本構(gòu)造的順序組成可以三種根本構(gòu)造的順序組成可以表示任何復(fù)雜的算法構(gòu)造。表示任何復(fù)雜的算法構(gòu)造。 由根本構(gòu)造構(gòu)成的算法，屬于由根本構(gòu)造構(gòu)成的算法，屬于“構(gòu)造化算法。構(gòu)造化算法。有關(guān)構(gòu)造化算法的總結(jié)有關(guān)構(gòu)造化算法的總結(jié) 一個(gè)構(gòu)造化的算法是由一些根本構(gòu)造順一個(gè)構(gòu)造化的算法是由一些根本構(gòu)造順序組成的；根本構(gòu)造之間不存在向前或序組成的；

10、根本構(gòu)造之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)根本構(gòu)造的范圍之內(nèi)如循環(huán)中的流程根本構(gòu)造的范圍之內(nèi)如循環(huán)中的流程跳轉(zhuǎn)；跳轉(zhuǎn)； 一個(gè)非構(gòu)造化算法可以用一個(gè)等價(jià)的構(gòu)一個(gè)非構(gòu)造化算法可以用一個(gè)等價(jià)的構(gòu)造化算法替代，其功能不變。造化算法替代，其功能不變。 假設(shè)一個(gè)算法不能分解為假設(shè)干個(gè)節(jié)本假設(shè)一個(gè)算法不能分解為假設(shè)干個(gè)節(jié)本構(gòu)造，那么它必然不是一個(gè)構(gòu)造化算法。構(gòu)造，那么它必然不是一個(gè)構(gòu)造化算法。3.4 順序構(gòu)造程序設(shè)計(jì) 1. 表達(dá)式語(yǔ)句 表達(dá)式語(yǔ)句是在各種表達(dá)式后加一個(gè)分號(hào)(；)構(gòu)成一個(gè)表達(dá)式語(yǔ)句。 2. 空語(yǔ)句 空語(yǔ)句直接由分號(hào)(；)組成，常用于控制語(yǔ)句中必

11、需出現(xiàn)語(yǔ)句之處。它不做任何操作，只在邏輯上起到有一個(gè)語(yǔ)句的作用。例如： ; 空語(yǔ)句也是一個(gè)語(yǔ)句，不產(chǎn)生任何動(dòng)作?？照Z(yǔ)句常用于構(gòu)成標(biāo)號(hào)語(yǔ)句，標(biāo)識(shí)程序中相關(guān)位置；循環(huán)語(yǔ)句中空循環(huán)體；模塊化程序中未實(shí)現(xiàn)的模塊及暫不鏈入的模塊。 3. 函數(shù)調(diào)用語(yǔ)句 由函數(shù)調(diào)用加上分號(hào)組成。 4.復(fù)合語(yǔ)句是由一對(duì)花括號(hào) 括起的假設(shè)干個(gè)語(yǔ)句，語(yǔ)法上可以看成是一個(gè)語(yǔ)句。復(fù)合語(yǔ)句中最后一個(gè)語(yǔ)句的分號(hào)不能省略。例如下面是一個(gè)復(fù)合語(yǔ)句： z = x； x = y； y =z; 凡是單一語(yǔ)句可以存在的位置，均可以運(yùn)用復(fù)合語(yǔ)句。復(fù)合語(yǔ)句用在語(yǔ)法上是單一語(yǔ)句，而相應(yīng)操作需多條語(yǔ)句描畫(huà)的情況。 5. 控制語(yǔ)句 控制語(yǔ)句有條件判別語(yǔ)句(i

12、f、switch)，循環(huán)語(yǔ)句(for、while、do-while)，轉(zhuǎn)移語(yǔ)句(goto、continue、break、return)?？刂普Z(yǔ)句根據(jù)控制條件決議程序的執(zhí)行流程，控制語(yǔ)句不是順序執(zhí)行的。 順序構(gòu)造是C言語(yǔ)的根本構(gòu)造，除非指示轉(zhuǎn)移，否那么計(jì)算機(jī)自動(dòng)以語(yǔ)句編寫的順序一句一句地執(zhí)行C語(yǔ)句。 5C言語(yǔ)無(wú)I/O語(yǔ)句，I/O操作由函數(shù)實(shí)現(xiàn)5 #include 5字符輸出函數(shù)3.5 數(shù)據(jù)的輸入與輸出 格式格式: putchar( c ): putchar( c )參數(shù)參數(shù): c: c為字符常量、變量或表達(dá)式為字符常量、變量或表達(dá)式功能：把字符功能：把字符c c輸出到顯示器上輸出到顯示器上返值：

13、正常，為顯示的代碼值；出錯(cuò)，為返值：正常，為顯示的代碼值；出錯(cuò)，為EOF(-1)EOF(-1)【例3.3】 字符數(shù)據(jù)的輸出。#include main( ) char a, b; a=r; b=e; putchar(a); putchar(b); putchar(d); putchar(n)；運(yùn)轉(zhuǎn)后，在屏幕上顯示：red 數(shù)據(jù)輸入數(shù)據(jù)輸入字符輸入函數(shù)字符輸入函數(shù) 格式格式:getchar( ):getchar( )功能：從鍵盤讀一字符功能：從鍵盤讀一字符返值：正常，前往讀取的代碼值；出錯(cuò)返值：正常，前往讀取的代碼值；出錯(cuò), ,前往前往EOF(-1)EOF(-1)留意：getchar()函數(shù)的括

14、號(hào)中沒(méi)有參數(shù)，該函數(shù)的輸入不斷到“回車才終了。回車前的一切輸入字符都會(huì)逐個(gè)顯示在屏幕上，但只需第一個(gè)字符作為函數(shù)的前往值。 運(yùn)轉(zhuǎn)時(shí)，輸入xxx ，在屏幕上顯示：x【例3.4】 單個(gè)字符的輸入和輸出。#include main() char ch; /*從鍵盤上讀入字符直到“回車終了*/ ch= getchar(); /*顯示輸入的第一個(gè)字符*/ putchar(ch); putchar(n); /*換行*/【例3.5】 將小寫字母轉(zhuǎn)換成大寫。#include main( ) char ch; ch=getche( ); putchar(ch-32);假設(shè)輸入b，在屏幕上顯示： bB 3. 字符

15、串輸入/輸出函數(shù) 字符串輸入函數(shù)gets() 用來(lái)從鍵盤讀入一串字符。函數(shù)的調(diào)用方式： gets(字符串變量名)；在輸入字符串后，必需用回車作為輸入終了。該回車符并不屬于這串字符，由一個(gè)“空操作字符( 0 )在串的最后來(lái)替代它。此時(shí)空格不能終了字符串的輸入，gets函數(shù)前往一個(gè)指針。字符串輸出函數(shù)puts()，將字符串?dāng)?shù)據(jù)(可以是字符串常量、字符指針或字符數(shù)組名)顯示在屏幕上并換行。函數(shù)的調(diào)用方式是： puts(字符串?dāng)?shù)據(jù))；【例3.6】 字符串的輸入和輸出。#include main( ) char str80; gets(str); puts(str);當(dāng)輸入為“How are you?，

16、那么輸出為：How are you?格式：格式：printf(printf(“格式控制串，輸出表格式控制串，輸出表) )功能：按指定格式向顯示器輸出數(shù)據(jù)功能：按指定格式向顯示器輸出數(shù)據(jù)返值：正常，前往輸出字節(jié)數(shù)；出錯(cuò)，前往返值：正常，前往輸出字節(jié)數(shù)；出錯(cuò)，前往EOF(-1)EOF(-1)3.5.3 格式輸入與輸出_格式輸出函數(shù) 輸出表：要輸出的數(shù)據(jù)可以沒(méi)有，多個(gè)時(shí)以輸出表：要輸出的數(shù)據(jù)可以沒(méi)有，多個(gè)時(shí)以“,分隔分隔 格式控制串：包含兩種信息格式控制串：包含兩種信息 格式闡明：格式闡明： %修飾符修飾符格式字符格式字符 ，用于指定輸，用于指定輸出格式出格式 普通字符或本義序列：原樣輸出普通字符或

17、本義序列：原樣輸出 格式字符格式字符d,ix,Xoucse,Efg%格式字符：十六進(jìn)制無(wú)符號(hào)整數(shù)不帶符號(hào)十進(jìn)制整數(shù)十進(jìn)制整數(shù)指數(shù)方式浮點(diǎn)小數(shù)單一字符字符串八進(jìn)制無(wú)符號(hào)整數(shù)小數(shù)方式浮點(diǎn)小數(shù)e和f中較短一種百分號(hào)本身int a=567;printf ( “%d,a);int a=255;printf(“%x,a);int a=65;printf(“%o,a);int a=567;printf(“%u,a);char a=65;printf(“%c,a);printf(“%s,“ABC);float a=567.789;printf(“%e,a);float a=567.789;printf(“%f

18、,a);float a=567.789;printf(“%g,a);printf(“%);567ff101567AABC5.677890e+02567.789000567.789% 闡明 格式字符要用小寫 格式字符與輸出項(xiàng)個(gè)數(shù)應(yīng)一樣，按先后順序一一對(duì)應(yīng) 輸出轉(zhuǎn)換:格式字符與輸出項(xiàng)類型不一致,自動(dòng)按指定格式輸出例 main() unsigned int u=65535; printf(u=%dn,u); 輸出結(jié)果：u=-1例 int a=3,b=4; printf(“%d %dn,a,b); printf(“a=%d , b=%dn,a,b); 例 int a=3,b=4; printf(“%d

19、 %dn,a,b); printf(“a=%d , b=%dn,a,b);輸出結(jié)果: 3 4 a=3, b=411 11 11 11 11 11 11 1165535 格式輸入函數(shù)格式格式: scanf(: scanf(“格式控制串，地址表格式控制串，地址表功能：按指定格式從鍵盤讀入數(shù)據(jù)，存入地址表指定的功能：按指定格式從鍵盤讀入數(shù)據(jù)，存入地址表指定的 存儲(chǔ)單元中存儲(chǔ)單元中, ,并按回車鍵終了并按回車鍵終了返值：正常，前往輸入數(shù)據(jù)個(gè)數(shù)返值：正常，前往輸入數(shù)據(jù)個(gè)數(shù) 地址表：變量的地址，常用取地址運(yùn)算符& 格式字符:d,i,o,x,u,c,s,f,e例 scanf(“%d,&a);

20、 輸入：10 那么 a=10例 scanf(“%x,&a); 輸入：11 那么 a=17 附加格式闡明符修飾符例 scanf(“%4d%2d%2d,&yy,&mm,&dd); 輸入 20191015 那么2019yy, 10 mm, 15 dd例 scanf(“%3d%*4d%f,&k,&f); 輸入 12345678765.43 那么123k, 8765.43f例 scanf(“%2d %*3d %2d,&a,&b); 輸入 12 345 67 那么12a, 67b例 scanf(“%3c%2c,&c1,&c2)

21、; 輸入 abcde 那么ac1, d c2l修飾符功 能hm*用于d,o,x前，指定輸入為short型整數(shù)用于d,o,x前，指定輸入為long型整數(shù)用于e,f前，指定輸入為double型實(shí)數(shù)指定輸入數(shù)據(jù)寬度，遇空格或不可轉(zhuǎn)換字符那么終了抑制符，指定輸入項(xiàng)讀入后不賦給變量 輸入分隔符的指定 普通以空格、TAB或回車鍵作為分隔符 其它字符做分隔符：格式串中兩個(gè)格式符間字符例 scanf(“%d%o%x,&a,&b,&c); printf(“a=%d,b=%d,c=%dn,a,b,c); 輸入 123 123 123 輸出 a=123,b=83,c=291例 scanf(“

22、%d:%d:%d,&h,&m,&s); 輸入 12:30:45 那么12 h, 30 m, 45 s例 scanf(“%d,%d,&a,&b) 輸入 3,4 那么3a, 4 b例 scanf(“a=%d,b=%d,c=%d,&a,&b,&c); 輸入 a=12,b=24,c=36 闡明： 用“%c格式符時(shí)，空格和本義字符作為有效字符輸入如 scanf(“%c%c%c,&c1,&c2,&c3); 假設(shè)輸入a b c 那么ac1, c2, b c3 輸入數(shù)據(jù)時(shí)，遇以下情況以為該數(shù)據(jù)終了： 遇空格、TAB、或回車

23、 遇寬度終了 遇非法輸入如 scanf(“%d%c%f,&a,&b,&c); 假設(shè)輸入1234a123o.26 那么 1234 a, a b, 123 c 輸入函數(shù)留下的“渣滓：例 int x; char ch; scanf(“%d,&x); ch=getchar(); printf(“x=%d,ch=%dn,x,ch);執(zhí)行：123輸出：x=123,ch=10例 int x; char ch; scanf(“%d,&x); scanf(“%c,&ch); printf(“x=%d,ch=%dn,x,ch);執(zhí)行：123輸出：x=123,ch=10處理方法：1用getchar()去除2用函數(shù)fflush(stdin)去除全部剩余內(nèi)容 (3) 用格式串中空格或“%*c來(lái)“吃掉例 int x; char ch; scanf(“%d,&x); getchar(); scanf(“ %c,&ch);或 scanf(“%*c%c,&ch); 留意: scanf( )函數(shù)沒(méi)有輸出功能(即不會(huì)向