算法與程序設(shè)計(jì)基礎(chǔ)

1、中國(guó)鐵道出版社 China Railway Publishing House 解決一個(gè)實(shí)際問(wèn)題而采取的方法和步驟， 稱之為“算法”。對(duì)于同一個(gè)問(wèn)題，可能有不 同的方法和步驟，即有不同的算法。 求1+2+3+4+100=? 步驟步驟1：1+2=3 步驟步驟2：3+3=6 步驟步驟3：6+4=10 步驟步驟99：4950+100=5 050 步驟步驟1：0+100=100 步驟步驟2：1+99=100 步驟步驟3：2+98=100 步驟步驟50：49+51=100 步驟步驟51：100*50=5 000 步驟步驟52：5 000+50=5 050 算法3 步驟1：k=1，s=0 步驟2：如果k10

2、0，則算法結(jié)束，s即為所求的和，輸出s； 否則轉(zhuǎn)向步驟3 步驟3：s=s+k，k=k+1 步驟4：轉(zhuǎn)向步驟2 當(dāng)然，算法也有優(yōu)劣之分，有的算法較簡(jiǎn)練，而有的 算法較煩瑣。上面三個(gè)算法中，算法2比算法1步驟少，算 法3比算法2步驟少，算法3的質(zhì)量最優(yōu)。一般地說(shuō)，希望 采用方法簡(jiǎn)單、運(yùn)算步驟少的方法。 順序結(jié)構(gòu)的程序是按語(yǔ)句的書(shū)寫(xiě)順序執(zhí)行的，用圖 3-2表示 選擇結(jié)構(gòu)或稱分支結(jié)構(gòu)、條件結(jié)構(gòu)，用圖3-3表示 循環(huán)結(jié)構(gòu)又稱重復(fù)結(jié)構(gòu)，有兩種方式： 一種是先判斷條件，若條件成立再進(jìn)入循環(huán)體，可 用圖3-4表示； 另一種是先進(jìn)入循環(huán)體執(zhí)行，再判斷條件是否成立。 可用圖3-5表示。 1973年美國(guó)的計(jì)算機(jī)科學(xué)

3、家INassi和 BShneiderman提出了一種新的流程圖形 式。在這種流程圖中把流程線完全去掉了，全 部算法寫(xiě)在一個(gè)矩形框內(nèi)，在框內(nèi)還可以包含 其他框，即由一些基本的框組成一個(gè)較大的框。 這種流程圖稱為N-S結(jié)構(gòu)流程圖（以兩人 名字的頭一個(gè)字母組成）。 偽代碼（pseudo code）是用介于自 然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)表 示算法，即計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言中具有的語(yǔ) 句關(guān)鍵字用英文表示，其他的可用漢字，也 可用英文，只要便于書(shū)寫(xiě)和閱讀就可。 用計(jì)算機(jī)語(yǔ)言描述算法必須嚴(yán)格遵循所用 語(yǔ)言的語(yǔ)法規(guī)則 #include void main() int sign,i,n; float su

4、m; printf(n Please input an integer to n: ); scanf(%d, sign=1; sum=1; i=1; while(ia+b 若a=3,b=4,c=9 則結(jié)果為1 a=bc 若b=4,c=9 則a的值為0 兩個(gè)數(shù)值進(jìn)行比較，是比較其數(shù)值的大小，兩個(gè) 字符進(jìn)行比較，是比較其ASCII碼值的大小。 用邏輯運(yùn)算符將關(guān)系表達(dá)式或邏輯表達(dá)式連 接起來(lái)的式子稱邏輯表達(dá)式。 例如，若a=4,b=2,x=6,y=7，則： ab c=getchar(); if(c=a 運(yùn)行情況如下： x Yes! 該語(yǔ)句的功能是:首先計(jì)算表達(dá)式的值，然后 判斷表達(dá)式的值是否為非零(

5、真)，若非零(真)， 則執(zhí)行語(yǔ)句1，否則執(zhí)行語(yǔ)句2。 其執(zhí)行過(guò)程下圖 【例3.9】輸入兩個(gè)數(shù)并判斷兩數(shù)是否相等。 1. if后面的表達(dá)式可以為任何類型的表達(dá) 式，只要表達(dá)式的結(jié)果為非零，則表示條件成 立，否則表示條件不成立。 2if語(yǔ)句中的語(yǔ)句1，語(yǔ)句2可以是一條語(yǔ) 句，也可以是由構(gòu)成的一個(gè)復(fù)合語(yǔ)句，如果 在該語(yǔ)句處需要寫(xiě)多條語(yǔ)句才能完成所必要的 功能時(shí)，就使用復(fù)合語(yǔ)句的形式。 3在格式2中的else前面的語(yǔ)句必須要有 一個(gè)分號(hào)，整個(gè)語(yǔ)句結(jié)束處有一個(gè)分號(hào)。如例 3.9中的if語(yǔ)句。 【例3.11】編寫(xiě)程序，求下列分段函數(shù)的值。 ： C語(yǔ)言規(guī)定：else總是與它 上面最近的且又沒(méi)有配對(duì) 的if語(yǔ)

6、句進(jìn)行配對(duì)。 #include stdio.h#include void main( )void main( ) int int score; score; char grade; char grade; printf(please printf(please input a score input a score：n);n); scanf(%d,); grade = score=90? A:(score grade = score=90? A:(score=60? B: C);=60? B: C); printf(%d belongs to %c,score,grade printf(%d

7、belongs to %c,score,grade);); 運(yùn)行結(jié)果如下：運(yùn)行結(jié)果如下： please input a score please input a score ：5959 59 belongs to C59 belongs to C switch語(yǔ)句屬于多分支結(jié)構(gòu)語(yǔ)句，通常用于描述有多種情況語(yǔ)句屬于多分支結(jié)構(gòu)語(yǔ)句，通常用于描述有多種情況 的選擇，其格式如下：的選擇，其格式如下： switch (表達(dá)式表達(dá)式) case 常量表達(dá)式常量表達(dá)式1： 語(yǔ)句語(yǔ)句1; case 常量表達(dá)式常量表達(dá)式2： 語(yǔ)句語(yǔ)句2; case 常量表達(dá)式常量表達(dá)式n： 語(yǔ)句語(yǔ)句n; default: 語(yǔ)句

8、語(yǔ)句(n+1); 圖3-29 用嵌套的if語(yǔ)句求一元二次方程的解 （1）goto語(yǔ)句以及用goto語(yǔ)句構(gòu)成的循環(huán) （2）用while 語(yǔ)句 （3）用do-while 語(yǔ)句 （4）用for 語(yǔ)句 goto語(yǔ)句為無(wú)條件轉(zhuǎn)向語(yǔ)句，其格式為 通常在兩種情況下使用goto語(yǔ)句： (1)與if語(yǔ)句一起構(gòu)成循環(huán)結(jié)構(gòu)； (2)從循環(huán)體中跳轉(zhuǎn)到循環(huán)體外，但在C語(yǔ)言 中可以用break語(yǔ)句和continue語(yǔ)句跳出本層 循環(huán)和結(jié)束本次循環(huán)。 while 語(yǔ)句又稱當(dāng)循環(huán)語(yǔ)句，其一般的形式如下： ； while 語(yǔ)句的執(zhí)行過(guò)程： 第1步：計(jì)算表達(dá)式的值，若表達(dá)式的值為真（非0）， 則執(zhí)行第二步，若表達(dá)式的值為假（值為

9、0），則轉(zhuǎn)到 第四步執(zhí)行。 第2步：執(zhí)行循環(huán)體語(yǔ)句，循環(huán)體語(yǔ)句可以是簡(jiǎn)單的一條 語(yǔ)句，也可以是由多條語(yǔ)句構(gòu)成的復(fù)合語(yǔ)句。 第3步：轉(zhuǎn)到第一步執(zhí)行。 第4步：結(jié)束循環(huán)，執(zhí)行while語(yǔ)句后的第一條語(yǔ)句。 do-while循環(huán)語(yǔ)句又稱直到型循環(huán)語(yǔ) 句，但是與Pascal語(yǔ)言中的repeat-until 語(yǔ)句又有所不同。 C語(yǔ)言中do-while語(yǔ)句的格式： i=1 sum=0 sum+=i i=i+2 當(dāng) i=100 輸出 sum 求解表達(dá)式1 當(dāng)表達(dá)式2 為真 執(zhí)行循環(huán)體語(yǔ)句 求解表達(dá)式3 執(zhí)行for 語(yǔ)句的下一條語(yǔ)句 圖3-35 for語(yǔ)句的執(zhí)行圖解 break語(yǔ)句格式： break； bre

10、ak語(yǔ)句的作用是從最內(nèi)層的switch、 for、while或dowhile語(yǔ)句中跳出，終止這 些語(yǔ)句的執(zhí)行，把控制流程轉(zhuǎn)移到被中斷的循 環(huán)語(yǔ)句（或者switch語(yǔ)句）后去執(zhí)行。 通過(guò)使用break語(yǔ)句，可以不必等到循環(huán) 或switch語(yǔ)句執(zhí)行結(jié)束，而是根據(jù)情況，提前 結(jié)束這些語(yǔ)句的執(zhí)行。 continue語(yǔ)句的形式： continue;continue; 其作用是提前結(jié)束本次循 環(huán)，即跳過(guò)循環(huán)體中那些尚 未執(zhí)行的語(yǔ)句，緊接著進(jìn)行 下一次是否執(zhí)行循環(huán)的判斷。 表達(dá)式 1 語(yǔ)句 1 continue 表達(dá)式 2 語(yǔ)句 2 while 循環(huán)的下一語(yǔ)句 假 真 真 假 從鍵盤(pán)輸入整數(shù)，顯示出其中的正

11、整數(shù)， 若輸入的是0，則退出。 #include void main( ) int x; do scanf(%d, if(x0) continue; printf(%dn,x); while(x!=0); 下面程序的作用是求連續(xù)的奇數(shù)和，當(dāng)奇數(shù) 和剛好超過(guò)1000時(shí)停止計(jì)算，并按運(yùn)行結(jié)果輸出。程序 中有兩空，請(qǐng)補(bǔ)充完整，使之能實(shí)現(xiàn)上述功能。 #include void main() int i,sum=0; for(i=1;i+) if(i%2=0) continue ; sum+=i; if(sum1000) break ; printf(1+3+5+%d=%dn,i,sum); 【例【例3

12、.36】利用格里高利公式求】利用格里高利公式求。 計(jì)算計(jì)算的公式為：的公式為： 直到最后一項(xiàng)的值小于直到最后一項(xiàng)的值小于10-6為止。為止。 【例【例3.36】的程序清單】的程序清單 【例【例3.37】的程序清單】的程序清單 【例【例3.37】程序】程序 【例【例3.38】編程打印樓梯，同時(shí)在樓梯上方打印兩個(gè) 笑臉。用音符代表臺(tái)階，如圖3-42所示。 笑臉和音符可用字符來(lái)表示，通過(guò)查詢ASCII碼 表得知，笑臉的ASCII值是1，音符的ASCII值是14。 【例【例3.38】 【例【例3.39】輸入一行字符，分別統(tǒng)計(jì)出其中 英文字母、空格、數(shù)字和其它字符的個(gè)數(shù)。 分析： 對(duì)于輸入的單個(gè)字符，要

13、學(xué)會(huì)判斷是英文 字母（AZ或者az），是阿拉伯?dāng)?shù) 字字符（09）還是其它字符的技巧。 #include void main( ) char c; int letters=0,space=0,digit=0,others=0; printf(please input some characters:n); while(c=getchar()!=n) if(c=a else others+; printf(all in all:char=%d space=%d, digit=%d, others=%dn, letters,space,digit,others); 【例【例3.39】的程序清單】的程序清單 【例【例3.40】 輸入整數(shù)x t=x*(x-1)+1 for(i=1;