第7章算法與程序設(shè)計(jì)

1、第第7 7章章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 大學(xué)計(jì)算機(jī)基礎(chǔ)大學(xué)計(jì)算機(jī)基礎(chǔ)課用課件課用課件 一一 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 二二 學(xué)習(xí)內(nèi)容學(xué)習(xí)內(nèi)容 典型算法典型算法 1.程序：程序：是為實(shí)現(xiàn)特定目標(biāo)或解決特定問(wèn)題而用計(jì)算機(jī)語(yǔ)言編寫(xiě)是為實(shí)現(xiàn)特定目標(biāo)或解決特定問(wèn)題而用計(jì)算機(jī)語(yǔ)言編寫(xiě) 的命令序列的集合。的命令序列的集合。 程序是程序設(shè)計(jì)的最終產(chǎn)物。計(jì)算機(jī)程序設(shè)計(jì)又稱(chēng)編程程序是程序設(shè)計(jì)的最終產(chǎn)物。計(jì)算機(jī)程序設(shè)計(jì)又稱(chēng)編程 （Programming），是一門(mén)編寫(xiě)和設(shè)計(jì)計(jì)算機(jī)程序的科學(xué)和藝），是一門(mén)編寫(xiě)和設(shè)計(jì)計(jì)算機(jī)程序的科學(xué)和藝 術(shù)。術(shù)。 一一. .程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ) 2.2. 計(jì)算機(jī)語(yǔ)言計(jì)算機(jī)語(yǔ)言 高級(jí)

2、語(yǔ)言高級(jí)語(yǔ)言 機(jī)器語(yǔ)言機(jī)器語(yǔ)言 匯編語(yǔ)言匯編語(yǔ)言 低級(jí)語(yǔ)言低級(jí)語(yǔ)言 計(jì)算機(jī)語(yǔ)言計(jì)算機(jī)語(yǔ)言 面向問(wèn)題的語(yǔ)言面向問(wèn)題的語(yǔ)言 面向過(guò)程的語(yǔ)言面向過(guò)程的語(yǔ)言 面向?qū)ο蟮恼Z(yǔ)言面向?qū)ο蟮恼Z(yǔ)言 C C、PascalPascal、 FortranFortran Visual FoxProVisual FoxPro C+C+、 Java Java 機(jī)器語(yǔ)言 機(jī)器語(yǔ)言是用二進(jìn)制代碼表示的計(jì)算機(jī)能直接識(shí)別和是用二進(jìn)制代碼表示的計(jì)算機(jī)能直接識(shí)別和 執(zhí)行的一種機(jī)器指令的集合。機(jī)器語(yǔ)言的所有指令都是由執(zhí)行的一種機(jī)器指令的集合。機(jī)器語(yǔ)言的所有指令都是由0 0、 1 1組成的二進(jìn)制。組成的二進(jìn)制。 操作碼操作碼操作數(shù)操作數(shù)

3、例如，計(jì)算例如，計(jì)算A=15+10A=15+10的機(jī)器語(yǔ)言程序如下：的機(jī)器語(yǔ)言程序如下： 10110000 00001111 10110000 00001111 把把1515放到累加器放到累加器A A中中 00101100 00001010 1000101100 00001010 10與累加器與累加器A A的值相加，結(jié)果仍放入的值相加，結(jié)果仍放入A A中中 11110100 11110100 結(jié)束，停機(jī)結(jié)束，停機(jī) 格式格式 機(jī)器語(yǔ)言 匯編語(yǔ)言 匯編語(yǔ)言用一些簡(jiǎn)潔的英文字母、符號(hào)串來(lái)替代一個(gè)用一些簡(jiǎn)潔的英文字母、符號(hào)串來(lái)替代一個(gè) 特定的指令的二進(jìn)制串，例如，用特定的指令的二進(jìn)制串，例如，用“AD

4、D”“ADD”代表加法，代表加法， “MOV”“MOV”代表數(shù)據(jù)傳遞等等。代表數(shù)據(jù)傳遞等等。 例如，計(jì)算 例如，計(jì)算A=15+10A=15+10的匯編程序如下：的匯編程序如下： MOV A,15 MOV A,15 把把1515放到累加器放到累加器A A中中 ADD A,10 10ADD A,10 10與累加器與累加器A A的值相加，結(jié)果仍放入的值相加，結(jié)果仍放入A A中中 HLT HLT 結(jié)束，停機(jī)結(jié)束，停機(jī) 匯編語(yǔ)言 高級(jí)語(yǔ)言 高級(jí)語(yǔ)言 例如，計(jì)算例如，計(jì)算A=15+10A=15+10的的C C語(yǔ)言程序如下：語(yǔ)言程序如下： #include #include main() main() in

5、tint a;a; a=15+10; a=15+10; printfprintf(“%(“%d”,ad”,a); ); return 0; return 0; 高級(jí)語(yǔ)言 lC程序由函數(shù)構(gòu)成，有且有一個(gè)主函數(shù)程序由函數(shù)構(gòu)成，有且有一個(gè)主函數(shù) l 程序執(zhí)行時(shí)總是從程序執(zhí)行時(shí)總是從main()函數(shù)開(kāi)始函數(shù)開(kāi)始 l 語(yǔ)句必須以語(yǔ)句必須以“；”結(jié)束，書(shū)寫(xiě)格式自由結(jié)束，書(shū)寫(xiě)格式自由 l “#”開(kāi)頭的為編譯預(yù)處理命令開(kāi)頭的為編譯預(yù)處理命令 l 利用利用/* */作為注釋作為注釋 機(jī)器語(yǔ)言機(jī)器語(yǔ)言 高級(jí)語(yǔ)言高級(jí)語(yǔ)言 書(shū)寫(xiě)書(shū)寫(xiě) 翻譯翻譯 執(zhí)行執(zhí)行 編譯編譯是指事先編好的一個(gè)稱(chēng)為編譯程序的機(jī)器語(yǔ)言程序，通是指事先

6、編好的一個(gè)稱(chēng)為編譯程序的機(jī)器語(yǔ)言程序，通 過(guò)編譯程序把高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序整個(gè)地翻譯成用機(jī)器語(yǔ)過(guò)編譯程序把高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序整個(gè)地翻譯成用機(jī)器語(yǔ) 言表示的與之等價(jià)的目標(biāo)程序。言表示的與之等價(jià)的目標(biāo)程序。 解釋解釋程序是在源程序進(jìn)入計(jì)算機(jī)時(shí)，通過(guò)解釋程序邊掃描邊程序是在源程序進(jìn)入計(jì)算機(jī)時(shí)，通過(guò)解釋程序邊掃描邊 解釋?zhuān)鹁漭斎?，逐句翻譯，計(jì)算機(jī)一句句執(zhí)行，并不產(chǎn)生解釋?zhuān)鹁漭斎?，逐句翻譯，計(jì)算機(jī)一句句執(zhí)行，并不產(chǎn)生 目標(biāo)程序。目標(biāo)程序。 共用體共用體 數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型 基本類(lèi)型基本類(lèi)型 整整型型 實(shí)型實(shí)型 字符型字符型 單精度單精度 雙精度雙精度 非基本類(lèi)型非基本類(lèi)型 數(shù)組數(shù)組 結(jié)構(gòu)體結(jié)構(gòu)體 指

7、針類(lèi)型指針類(lèi)型 枚舉型枚舉型 3.3.數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型 l整型整型 ：int(如如 0,67, -2) l實(shí)型：實(shí)型：float、double(如如 2.3, 1.2e-5) l字符型：字符型：char(如如 z, 3, $, n ) 用用開(kāi)頭的字符為轉(zhuǎn)義字符開(kāi)頭的字符為轉(zhuǎn)義字符, 代表代表1個(gè)字符個(gè)字符 l字符串：字符串：char a(如如 UKM, 1, 5a ) 數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型 l 變量必須先聲明，后使用變量必須先聲明，后使用 變量變量 l 變量地址變量地址 數(shù)組 l 數(shù)組的輸入與輸出數(shù)組的輸入與輸出 int i,a5; for(i=0;i5;i+) scanf(“%d”, for(i

8、=0;i5;i+) printf(“%d”, ai); l 數(shù)組元素求和數(shù)組元素求和 int i,sum=0,a5=1,2,3,4,5; for(i=0;i5;i+) sum=sum+ai; l 結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì) l 面向?qū)ο蟮某绦蛟O(shè)計(jì)面向?qū)ο蟮某绦蛟O(shè)計(jì) 4.4.程序設(shè)計(jì)方法程序設(shè)計(jì)方法 l 自頂向下自頂向下 l 逐步求精逐步求精 l 模塊化模塊化 l 限制使用限制使用goto語(yǔ)句語(yǔ)句 結(jié)構(gòu)化程序設(shè)計(jì)結(jié)構(gòu)化程序設(shè)計(jì) A B BA P P A 順序結(jié)構(gòu)順序結(jié)構(gòu)選擇結(jié)構(gòu)選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 程序的三種主要結(jié)構(gòu)程序的三種主要結(jié)構(gòu) P A 當(dāng)型循環(huán)當(dāng)型循環(huán)直到型循環(huán)直到型循環(huán) 一.順

9、序結(jié)構(gòu) #include /*使用標(biāo)準(zhǔn)函數(shù)庫(kù)中的輸入輸出函數(shù)時(shí)需引用該頭文件*/ main() printf(Hello,World!n); 程序員的第一個(gè)程序 順序結(jié)構(gòu) 1. 輸入整數(shù)輸入整數(shù)a、b并求和并求和 #include main() int a,b; printf(Please input a and b:n); scanf(%d,%d,/* 從鍵盤(pán)輸入 從鍵盤(pán)輸入a、b的值（以空格或者回車(chē)分隔）的值（以空格或者回車(chē)分隔） */ printf(a+b=%dn,a+b); 利用海倫公式可以求得三角形面積為：利用海倫公式可以求得三角形面積為： 其中，其中，s=(a+b+c)/2，a、b

10、、c是三條邊長(zhǎng)是三條邊長(zhǎng) 2. 已知三角形的三條邊長(zhǎng)，計(jì)算三角形的面積。已知三角形的三條邊長(zhǎng)，計(jì)算三角形的面積。 開(kāi)始開(kāi)始 對(duì)三邊長(zhǎng)賦值對(duì)三邊長(zhǎng)賦值 計(jì)算計(jì)算s值值 計(jì)算面積計(jì)算面積area 結(jié)束結(jié)束 輸出三角形面積輸出三角形面積area 順序結(jié)構(gòu) 【示例示例7-4】輸入三角形的三輸入三角形的三 條邊長(zhǎng)，如果能構(gòu)成三角形則計(jì)算三角形的面積，條邊長(zhǎng)，如果能構(gòu)成三角形則計(jì)算三角形的面積， 否則，輸出否則，輸出“不能構(gòu)成三角形不能構(gòu)成三角形”。 開(kāi)始開(kāi)始 輸入三條邊長(zhǎng)輸入三條邊長(zhǎng) 計(jì)算計(jì)算s值值 計(jì)算面積計(jì)算面積area 結(jié)束結(jié)束 輸出三角形面積輸出三角形面積area 輸出不能構(gòu)成三輸出不能構(gòu)成三

11、角形的信息信息角形的信息信息 構(gòu)成三角形？構(gòu)成三角形？ YN 二.選擇結(jié)構(gòu) 開(kāi)始開(kāi)始 對(duì)三邊長(zhǎng)賦值對(duì)三邊長(zhǎng)賦值 計(jì)算計(jì)算s值值 計(jì)算面積計(jì)算面積area 結(jié)束結(jié)束 輸出三角形面積輸出三角形面積area 選擇結(jié)構(gòu) 引：輸入一個(gè)小寫(xiě)字母，變成大寫(xiě)后輸出引：輸入一個(gè)小寫(xiě)字母，變成大寫(xiě)后輸出 #include “stdio.h” main() char a； printf(“Input a lowercase letter：”)； a = getchar()； a = a-32； printf(“%c n”，a)； #include “stdio.h” main() char a； printf(“i

12、nput a letter:”); a=getchar( ); if(a=a printf(“%cn”,a); 1.判斷輸入的一個(gè)字符，如果是小寫(xiě)字母，變成大寫(xiě)后輸出判斷輸入的一個(gè)字符，如果是小寫(xiě)字母，變成大寫(xiě)后輸出 #include main() int a,b; printf(Please input 2 numbers:); scanf(%d%d, if(ab) printf(%d,%d,a,b); else printf(%d,%d,b,a); 2.2.任意給定兩個(gè)數(shù)任意給定兩個(gè)數(shù)a a，b b，將它們按從大到小的次序進(jìn)行排序。，將它們按從大到小的次序進(jìn)行排序。 #include ma

13、in() int a; printf(“Please input the day you want to date:”）; scanf(%d, if(a=1|a=3|a=5) printf(NO); else printf(YES); 3. 3.晶晶約會(huì)：周一、三、五均有課晶晶約會(huì)：周一、三、五均有課 4.4.判斷輸入的年份是否為閏年判斷輸入的年份是否為閏年 main() int year; printf(Please input the year:); scanf(%d, if (year%4=0 else printf(%d is not a leap year.n,year); 【例例】

14、輸入輸入5組三角形的三組三角形的三 條邊長(zhǎng)，對(duì)每組數(shù)據(jù)進(jìn)行條邊長(zhǎng)，對(duì)每組數(shù)據(jù)進(jìn)行 判斷，如果能構(gòu)成三角形則計(jì)算三角形的面積，否則，判斷，如果能構(gòu)成三角形則計(jì)算三角形的面積，否則， 輸出輸出“不能構(gòu)成三角形不能構(gòu)成三角形”。 Y N Y 開(kāi)始開(kāi)始 輸入三條邊長(zhǎng)輸入三條邊長(zhǎng) 計(jì)算面積并輸出計(jì)算面積并輸出 結(jié)束結(jié)束 輸出相應(yīng)信息輸出相應(yīng)信息 構(gòu)成三角形？構(gòu)成三角形？ 循環(huán)變量循環(huán)變量i=1 i5？ i=i+1 N 三.控制結(jié)構(gòu) 循環(huán)控制 #include main() int sum=0,n=1; for(n=1;n=10;n+) sum=sum+n; printf(sum=%dn,sum); 循環(huán)

15、控制 #include “stdio.h” main() int score, sum=0, i; float average; for(i=1;i=10;i+) printf(“n Input No.%d score:”, i ); scanf(%d, sum=sum+score; average=sum/10; printf(naverage=%fn,average); #include #include #include main() int i,g,j=1; long t; srand(time(NULL); i=rand()%100+1; printf(Please input yo

16、ur number（1-100）：）：); scanf(%d, t=time(NULL); while(g!=i) if(gi)printf(n The number is too big,please input again：); if(gi)printf(nThe number is too small,please input again：); scanf(%d, j+; t=time(NULL)-t; printf(nCongratulations！You got the right answer with %d times，uesed %d second。n,j,t); l sran

17、d（time（NULL）使得隨機(jī)數(shù)種子隨時(shí) 間的變化而變化。 l time函數(shù)可以獲取當(dāng)前的系統(tǒng)時(shí)間，返回從 CUT（Coordinated Universal Time）時(shí)間 1970年1月1日00:00:00到當(dāng)前時(shí)刻的秒數(shù)。 l rand()返回從0-32767的整數(shù) l srand 和 rand 應(yīng)該組和使用 算法（算法（Algorithm）是一組明確的、可以執(zhí)行的步驟的）是一組明確的、可以執(zhí)行的步驟的 有序集合。有序集合。 l 有窮性有窮性 l 確切性確切性 l 有有0個(gè)或多個(gè)輸入個(gè)或多個(gè)輸入 l 有有1個(gè)或多個(gè)輸出個(gè)或多個(gè)輸出 l 有效性有效性 二二. .算法算法 算法評(píng)價(jià) 算法評(píng)

18、價(jià) l 正確性正確性 l 時(shí)間復(fù)雜度時(shí)間復(fù)雜度（計(jì)算機(jī)上運(yùn)行所花費(fèi)的時(shí)間）* l 空間復(fù)雜度空間復(fù)雜度（算法運(yùn)行過(guò)程中臨時(shí)占用的存儲(chǔ)空間的大?。?測(cè)定運(yùn)行時(shí)間最可靠的方法就是計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本操作計(jì)算對(duì)運(yùn)行時(shí)間有消耗的基本操作 （如（如“運(yùn)算運(yùn)算”、“條件比較條件比較”、“變量代入變量代入”）的執(zhí)行次數(shù)）的執(zhí)行次數(shù)，運(yùn)行時(shí)間 與該計(jì)數(shù)成正比。 算法的復(fù)雜度標(biāo)記方法一般采用“O記法記法”。在O記法中，算法的復(fù) 雜度是以處理對(duì)象數(shù)據(jù)的數(shù)量n為基準(zhǔn)來(lái)記述的。 【例例】求求1+2+3+1001+2+3+100 普通求和中，數(shù)據(jù)量為n時(shí)，時(shí)間復(fù)雜度是1+1+(n+1)+n+n=3n+3，操作次

19、數(shù)為3n+3。 當(dāng)n無(wú)限增大時(shí)，n的系數(shù)3和需要加的3均可忽略，因此記做時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n)。 解決方案1（普通求和） int sum = 0, n = 100; for (int i = 1; i sum； 步驟2：使i為1； 步驟3：將sum與i相加，結(jié)果仍放到變量sum中，寫(xiě)成 sum+i=sum； 步驟4：使i的值加1，即i+1=i； 步驟5：如果i的值不大于11（i10），返回重新執(zhí)行第3步和其 后的步驟4和步驟5；否則，算法結(jié)束，sum的值即為所求。 方法一：方法一： 步驟1：先求1與2的和，得到結(jié)果3； 步驟2：將步驟1得到的和與3相加，得到結(jié)果6； 步驟3：將步驟

20、2得到的和與4相加，得到結(jié)果10； 步驟9：將步驟8得到的和與10相加，得到結(jié)果55。 流程圖是通過(guò)箭頭相互連接的幾何圖形來(lái)表達(dá)的方法。流程圖是通過(guò)箭頭相互連接的幾何圖形來(lái)表達(dá)的方法。 ANSI規(guī)定 的一些常 用流程圖 符號(hào)。 起止框 輸入輸出框 判斷框 處理框 流程線 1.1.認(rèn)識(shí)算法認(rèn)識(shí)算法算法的算法的描述工具描述工具 sum=0 n=1 n=10 sum=sum+n n=n+1 輸出輸出sum N Y 結(jié)束結(jié)束 開(kāi)始開(kāi)始 【示例示例7-1】求求1+2+3+10，即，即 10 1n n 流程圖流程圖 sum=0，n=1 sum=sum+n n=n+1 輸出輸出sum的值的值 當(dāng)當(dāng)i=10時(shí)

21、，做時(shí)，做 N-S圖圖 用流程圖用流程圖/N-S/N-S圖表示算法圖表示算法 【示例示例7-1】求求1+2+3+10，即，即 10 1n n #include main() int sum=0,n=1; for(n=1;n=10;n+) sum=sum+n; printf(sum=%dn,sum); 用計(jì)算機(jī)語(yǔ)言表示算法用計(jì)算機(jī)語(yǔ)言表示算法 【算法思想算法思想】 l 掃描整個(gè)序列，從中選出最小的元素，將它與序列的第一個(gè)元素交換； l 然后再在余下的元素中找出最小數(shù)據(jù)的元素，與序列的第二個(gè)元素相互交換 位置 l 然后對(duì)剩下的序列采用同樣的方法，直到序列空為止。 2.經(jīng)典算法 排序算法：選擇排序

22、#include main() int i,index,k,n,temp,a5; printf(“Please input 5 numbers:n”); for(k=0;k5;k+) scanf(%d, for(k=0;k4;k+) index=k; for(i=k+1;i5;i+) if(aiaindex) index=i; if(index!=k) temp=aindex; aindex=ak; ak=temp; 內(nèi)循環(huán)內(nèi)循環(huán) 外循環(huán)外循環(huán) 選擇法排序選擇法排序 printf(n); for(k=0;k5;k+) printf(%d,ak); 【算法思想算法思想】 l 在每一輪的排序過(guò)程中

23、從第一個(gè)數(shù)開(kāi)始，相鄰兩數(shù)依次比較，當(dāng)發(fā)現(xiàn)前一個(gè)數(shù)據(jù) 比后一個(gè)數(shù)據(jù)大時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)行互換。 l 較小的數(shù)據(jù)就會(huì)逐個(gè)向前移動(dòng)，大者往后移動(dòng)，最后將序列中的最大值換到了序 列的最后。 經(jīng)典排序算法：冒泡法經(jīng)典排序算法：冒泡法排序 #include main() int i,j,n=5,temp,a5=18,6,3,15,2; printf(the old array isn); for(i=0;in;i+) printf(%d ,ai); for(i=0;in-1;i+) for(j=0;jaj+1) temp=aj; aj=aj+1; aj+1=temp; printf(nthe new a

24、rray isn); for(i=0;in;i+) printf(%d ,ai); 冒泡法排序冒泡法排序 設(shè)數(shù)組為設(shè)數(shù)組為an： 1. 初始時(shí)，a0自成1個(gè)有序區(qū)，無(wú)序區(qū)為a1.n-1。令i=1 2. 將ai并入當(dāng)前的有序區(qū)a0i-1中形成a0i的有序區(qū)間。 3. i+并重復(fù)第二步直到i=n-1。排序完成。 經(jīng)典排序算法：插入法經(jīng)典排序算法：插入法排序 【算法思想算法思想】 每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子序列中 的適當(dāng)位置，直到全部記錄插入完成為止。 main() int i,j,n=7,temp,a7=12,15,9,20,6,31,24; for (i =

25、1; i n; i+) if (ai = 0 j-) aj + 1 = aj; aj + 1 = temp; 插入法排序插入法排序 【算法思想算法思想】 l 逐一將數(shù)組的數(shù)據(jù)與輸入數(shù)進(jìn)行比較 l 如果相等，說(shuō)明找到，宣布查找成功，記錄數(shù)組下標(biāo)，算法結(jié)束； l 如果不相等，說(shuō)明沒(méi)有找到，此時(shí)應(yīng)判斷是否還有剩余的數(shù)據(jù)，如果 還有剩余的數(shù)據(jù)則繼續(xù)和剩余的數(shù)據(jù)比較，如果沒(méi)有剩余的數(shù)據(jù)，則 宣布查找失敗，算法結(jié)束 輸入：輸入： 2 9 8 10 6 查找：查找： 9 輸出：輸出：2 輸入：輸入：2 9 8 10 6 查找：查找：7 輸出：輸出：Not Found 經(jīng)典查找算法：順序查找經(jīng)典查找算法：順序

26、查找-輸入一組數(shù)據(jù)，再輸入需要查找的數(shù)x，如果找到，輸 出相應(yīng)的位置，否則，輸出Not Found。 #include main() int i,x,a5; printf(Please input 5 numbers:n); for(i=0;i5;i+) scanf(%d, printf(Please input the number you want to find:n); scanf(%d, for(i=0;i=5) printf(There is no such number); 順序查找順序查找 經(jīng)典查找算法：折半查找經(jīng)典查找算法：折半查找（數(shù)據(jù)已經(jīng)排好序）（數(shù)據(jù)已經(jīng)排好序） 輸入：10 17 20 22 31 44 51 55 68 查找：20 【算法思想算法思想】 數(shù)據(jù)存放在數(shù)組中，被查找數(shù)據(jù)放到x變量中，t表示查找 范圍的起點(diǎn)位置，b代表查找范圍的末尾，m id表示查找范圍的中間位置， mid=(t+b)/2。 第