算法和基本程序設(shè)計

1、第3章 算法和基本程序設(shè)計,3.1 算法的概念 3.2 結(jié)構(gòu)化程序設(shè)計方法 3.3 程序的基本結(jié)構(gòu) 3.4 順序結(jié)構(gòu)程序設(shè)計 3.5 數(shù)據(jù)的輸入輸出 3.6 C程序的上機(jī)步驟,3.1 算法的概念,1.定義: 做任何事情都有一定的步驟。為解決一個問題而采取的方法和步驟，就稱為算法。 2.計算機(jī)算法可分為兩大類： 數(shù)值運(yùn)算算法：求解數(shù)值； 非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。,一個著名的公式,數(shù)據(jù)結(jié)構(gòu)+算法=程序 數(shù)據(jù)：計算機(jī)所能識別、存儲和處理的對象。數(shù)據(jù)的動態(tài)性。 數(shù)據(jù)結(jié)構(gòu)：確定數(shù)據(jù)對象及其存儲方式，并定義在這些數(shù)據(jù)對象上的運(yùn)算集合。 算法：為解決一個問題而采取的方法和步驟。,算法的特性,1 有窮性

2、 操作步驟是有限的，不是無限的。 2 確定性 每個步驟是確定的，無歧義性。 3 有零個或多個輸入 4 有一個或多個輸出 5 有效性 每一步驟能有效執(zhí)行，并得到確定結(jié)果。,3.1.2 算法的評價標(biāo)準(zhǔn) 1. 正確性 對任何合法的輸入，算法都會得出正確的結(jié)果。 2. 可讀性 可讀性指算法被理解的難易程度。 3. 健壯性（魯棒性） 健壯性即對非法輸入的抵抗能力。 4. 高效率與低存儲量需求 通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模有關(guān)。二者往往是一對矛盾，常?？梢杂每臻g換時間，也可以用時間換空間。,怎樣表示一個算法,用自然語言表示算法,用流程圖表示

3、算法,用N-S流程圖表示算法,用偽代碼表示算法,用計算機(jī)語言表示算法,歧義性，描述分支、循環(huán)算法不方便,起止框,輸入輸出框,處理框,判斷框,流程線,連接點,【例3.1】 求三個整數(shù)的和。 求三個整數(shù)和的算法流程圖如圖所示。,輸入x,y,z,圖3.2 求三個整數(shù)和的算法,【例3.2】 求最大公約數(shù)。,最大公因數(shù)的算法 求最大公因數(shù)的最普遍的算法是歐幾里得算法，它最初是公元前由歐幾里得提出來的，有時也稱它為輾轉(zhuǎn)相除法表述如下： 設(shè)給定m，n(mn)，令r0=m，r1=n，有 則得rk=gcd(rk-1，rk)=gcd(rk-2，rk-1)=gcd(r2，r3)=gcd(r1，r2)=gcd(r0，

4、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個步驟，太可怕了。,案例 求12341000,3.2 結(jié)構(gòu)化程序設(shè)計的方法,結(jié)構(gòu)化程序設(shè)計思想采用了模塊分解與功能抽象和自頂向下、分而治之的方法，從而有效地將一個較復(fù)雜的程序系統(tǒng)設(shè)計任務(wù)分解成許多易于控制和處理的子程序，便于開發(fā)和維護(hù)，減少程序的出錯概率和提高軟件的開發(fā)效率。 采用結(jié)構(gòu)化程序設(shè)計方法應(yīng)遵循以下原則。 1. 自頂向下 即在程序設(shè)計時

5、，先考慮總體，做出全局設(shè)計，然后再考慮細(xì)節(jié)進(jìn)行局部設(shè)計，逐步實現(xiàn)精細(xì)化。這種方法稱為“自頂向下，逐步細(xì)化”的方法。 2. 模塊化 就是將一個大任務(wù)分成若干個較小的部分，每一部分承擔(dān)一定的功能，稱為“功能模塊”。每個模塊可以分別編程和調(diào)試，然后組成一個完整的程序。模塊的劃分應(yīng)遵循一些基本原則，如模塊內(nèi)部聯(lián)系要緊密，關(guān)聯(lián)程度要高；模塊間的接口要盡可能簡單，以減少模塊間的數(shù)據(jù)傳遞。 3. 限制使用GOTO語句,結(jié)構(gòu)化的程序設(shè)計方法,基本思路: 把一個復(fù)雜問題的求解過程分階段進(jìn)行,每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi). 采用的方法: 1 自頂而下 2 逐步細(xì)化 3 模塊化設(shè)計 4 結(jié)構(gòu)

6、化編碼,三種基本結(jié)構(gòu),1 順序結(jié)構(gòu) 2 選擇結(jié)構(gòu) 3 循環(huán)結(jié)構(gòu),3.3 程序的基本結(jié)構(gòu),三種基本結(jié)構(gòu)的特點,1 只有一個入口 2 只有一個出口,順序結(jié)構(gòu)的流程圖符號,傳統(tǒng)流程圖,N-S流程圖,選擇結(jié)構(gòu)的流程圖符號,傳統(tǒng)流程圖,選擇結(jié)構(gòu)的流程圖符號（續(xù)）,N-S流程圖,循環(huán)結(jié)構(gòu)的流程圖符號,不成立,傳統(tǒng)流程圖,While型,Until型,循環(huán)結(jié)構(gòu)的流程圖符號（續(xù)）,While型,Until型,N-S流程圖,一個有用的結(jié)論,已經(jīng)證明： 三種基本結(jié)構(gòu)的順序組成可以表示任何復(fù)雜的算法結(jié)構(gòu)。 由基本結(jié)構(gòu)構(gòu)成的算法，屬于“結(jié)構(gòu)化”算法。,有關(guān)結(jié)構(gòu)化算法的總結(jié),一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的；基

7、本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本結(jié)構(gòu)的范圍之內(nèi)（如循環(huán)中的流程跳轉(zhuǎn)）；,一個非結(jié)構(gòu)化算法可以用一個等價的結(jié)構(gòu)化算法代替，其功能不變。,如果一個算法不能分解為若干個節(jié)本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化算法。,3.4 順序結(jié)構(gòu)程序設(shè)計,1. 表達(dá)式語句 表達(dá)式語句是在各種表達(dá)式后加一個分號(；)形成一個表達(dá)式語句。 2. 空語句 空語句直接由分號(；)組成，常用于控制語句中必須出現(xiàn)語句之處。它不做任何操作，只在邏輯上起到有一個語句的作用。例如： ; 空語句也是一個語句，不產(chǎn)生任何動作?？照Z句常用于構(gòu)成標(biāo)號語句，標(biāo)識程序中相關(guān)位置；循環(huán)語句中空循環(huán)體；模塊化程序中未實現(xiàn)的模塊

8、及暫不鏈入的模塊。,3. 函數(shù)調(diào)用語句 由函數(shù)調(diào)用加上分號組成。 4.復(fù)合語句是由一對花括號 括起的若干個語句，語法上可以看成是一個語句。復(fù)合語句中最后一個語句的分號不能省略。例如下面是一個復(fù)合語句： z = x； x = y； y =z; 凡是單一語句可以存在的位置，均可以使用復(fù)合語句。復(fù)合語句用在語法上是單一語句，而相應(yīng)操作需多條語句描述的情況。,5. 控制語句 控制語句有條件判斷語句(if、switch)，循環(huán)語句(for、while、do-while)，轉(zhuǎn)移語句(goto、continue、break、return)。控制語句根據(jù)控制條件決定程序的執(zhí)行流程，控制語句不是順序執(zhí)行的。 順

9、序結(jié)構(gòu)是C語言的基本結(jié)構(gòu)，除非指示轉(zhuǎn)移，否則計算機(jī)自動以語句編寫的順序一句一句地執(zhí)行C語句。,C語言無I/O語句，I/O操作由函數(shù)實現(xiàn) #include 字符輸出函數(shù),3.5 數(shù)據(jù)的輸入與輸出,格式: putchar( c ) 參數(shù): c為字符常量、變量或表達(dá)式 功能：把字符c輸出到顯示器上 返值：正常，為顯示的代碼值；出錯，為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)行后，在屏幕上顯示：red,數(shù)據(jù)輸入 字符輸入

10、函數(shù),格式:getchar( ) 功能：從鍵盤讀一字符 返值：正常，返回讀取的代碼值；出錯,返回EOF(-1),注意：getchar()函數(shù)的括號中沒有參數(shù)，該函數(shù)的輸入一直到“回車”才結(jié)束?；剀嚽暗乃休斎胱址紩饌€顯示在屏幕上，但只有第一個字符作為函數(shù)的返回值。,運(yùn)行時，輸入xxx ，在屏幕上顯示：x,【例3.4】 單個字符的輸入和輸出。 #include main() char ch; /*從鍵盤上讀入字符直到“回車”結(jié)束*/ ch= getchar(); /*顯示輸入的第一個字符*/ putchar(ch); putchar(n); /*換行*/ ,【例3.5】 將小寫字母轉(zhuǎn)換成大寫

11、。 #include main( ) char ch; ch=getche( ); putchar(ch-32); ,若輸入b，在屏幕上顯示： bB,3. 字符串輸入/輸出函數(shù),字符串輸入函數(shù)gets() 用來從鍵盤讀入一串字符。函數(shù)的調(diào)用形式： gets(字符串變量名)； 在輸入字符串后，必須用回車作為輸入結(jié)束。該回車符并不屬于這串字符，由一個“空操作字符( 0 )”在串的最后來代替它。此時空格不能結(jié)束字符串的輸入，gets函數(shù)返回一個指針。 字符串輸出函數(shù)puts()，將字符串?dāng)?shù)據(jù)(可以是字符串常量、字符指針或字符數(shù)組名)顯示在屏幕上并換行。 函數(shù)的調(diào)用形式是： puts(字符串?dāng)?shù)據(jù))；,

12、【例3.6】 字符串的輸入和輸出。 #include main( ) char str80; gets(str); puts(str); ,當(dāng)輸入為“How are you?”，則輸出為： How are you?,格式：printf(“格式控制串”，輸出表) 功能：按指定格式向顯示器輸出數(shù)據(jù) 返值：正常，返回輸出字節(jié)數(shù)；出錯，返回EOF(-1),3.5.3 格式輸入與輸出_格式輸出函數(shù),輸出表：要輸出的數(shù)據(jù)（可以沒有，多個時以“,”分隔） 格式控制串：包含兩種信息 格式說明： %修飾符格式字符 ，用于指定輸出格式 普通字符或轉(zhuǎn)義序列：原樣輸出 格式字符,int a=567;printf (

13、“%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”,a);,float a=567.789;printf(“%g”,a);,printf(“%”);,567,ff,101,567,A,ABC,5.677890e+02,567.789000,567.789,%,說明 格

14、式字符要用小寫 格式字符與輸出項個數(shù)應(yīng)相同，按先后順序一一對應(yīng) 輸出轉(zhuǎn)換:格式字符與輸出項類型不一致,自動按指定格式輸出,例 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 %dn”,a,b); printf(“a=%d , b=%dn”,a,b); 輸出結(jié)果: 3 4 a=3, b=4,格式輸入函數(shù),格式: scanf(“格式控制串”，地址表） 功

15、能：按指定格式從鍵盤讀入數(shù)據(jù)，存入地址表指定的 存儲單元中,并按回車鍵結(jié)束 返值：正常，返回輸入數(shù)據(jù)個數(shù),地址表：變量的地址，常用取地址運(yùn)算符 char ch; scanf(“%d”, 執(zhí)行：123 輸出：x=123,ch=10,例 int x; char ch; scanf(“%d”, 執(zhí)行：123 輸出：x=123,ch=10,解決方法： （1）用getchar()清除 （2）用函數(shù)fflush(stdin)清除全部剩余內(nèi)容 (3) 用格式串中空格或“%*c”來“吃掉”,例 int x; char ch; scanf(“%d”,注意: scanf( )函數(shù)沒有輸出功能(即不會向屏幕顯示任何

16、字符) 也不能規(guī)定小數(shù)位數(shù)(m.n) 典型錯誤: scanf( “a=%d,b=%d,c=%d n”,正確語句: printf( “ Input a,b,c=“); scanf( “%d, %d, %d”, ,/* 求圓的面積和周長 */ #define PI 3.14159 #include stdio.h main( ) float r; float s, l; printf（請輸入圓的半徑: ）; scanf（%f, ,輸入數(shù)據(jù)：3 運(yùn)行結(jié)果為： 面積=28.274, 周長=18.850,【例3.10】 編寫顯示如下界面的程序: 學(xué)生管理程序 Add追加數(shù)據(jù) Modify修改數(shù)據(jù) Delete刪除數(shù)據(jù) Print打印數(shù)據(jù) Sort成績排序 Qu