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

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

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

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

4、D”“ADD”代表加法，代表加法， “MOV”“MOV”代表數(shù)據(jù)傳遞等等。代表數(shù)據(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é)束，停機結(jié)束，停機 匯編語言 高級語言 高級語言 例如，計算例如，計算A=15+10A=15+10的的C C語言程序如下：語言程序如下： #include #include main() main() in

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

6、編好的一個稱為編譯程序的機器語言程序，通 過編譯程序把高級語言書寫的源程序整個地翻譯成用機器語過編譯程序把高級語言書寫的源程序整個地翻譯成用機器語 言表示的與之等價的目標程序。言表示的與之等價的目標程序。 解釋解釋程序是在源程序進入計算機時，通過解釋程序邊掃描邊程序是在源程序進入計算機時，通過解釋程序邊掃描邊 解釋，逐句輸入，逐句翻譯，計算機一句句執(zhí)行，并不產(chǎn)生解釋，逐句輸入，逐句翻譯，計算機一句句執(zhí)行，并不產(chǎn)生 目標程序。目標程序。 共用體共用體 數(shù)據(jù)類型數(shù)據(jù)類型 基本類型基本類型 整整型型 實型實型 字符型字符型 單精度單精度 雙精度雙精度 非基本類型非基本類型 數(shù)組數(shù)組 結(jié)構(gòu)體結(jié)構(gòu)體 指

7、針類型指針類型 枚舉型枚舉型 3.3.數(shù)據(jù)類型數(shù)據(jù)類型 l整型整型 ：int(如如 0,67, -2) l實型：實型：float、double(如如 2.3, 1.2e-5) l字符型：字符型：char(如如 z, 3, $, n ) 用用開頭的字符為轉(zhuǎn)義字符開頭的字符為轉(zhuǎn)義字符, 代表代表1個字符個字符 l字符串：字符串：char a(如如 UKM, 1, 5a ) 數(shù)據(jù)類型數(shù)據(jù)類型 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è)計結(jié)構(gòu)化程序設(shè)計 l 面向?qū)ο蟮某绦蛟O(shè)計面向?qū)ο蟮某绦蛟O(shè)計 4.4.程序設(shè)計方法程序設(shè)計方法 l 自頂向下自頂向下 l 逐步求精逐步求精 l 模塊化模塊化 l 限制使用限制使用goto語句語句 結(jié)構(gòu)化程序設(shè)計結(jié)構(gòu)化程序設(shè)計 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 /*使用標準函數(shù)庫中的輸入輸出函數(shù)時需引用該頭文件*/ main() printf(Hello,World!n); 程序員的第一個程序 順序結(jié)構(gòu) 1. 輸入整數(shù)輸入整數(shù)a、b并求和并求和 #include main() int a,b; printf(Please input a and b:n); scanf(%d,%d,/* 從鍵盤輸入 從鍵盤輸入a、b的值（以空格或者回車分隔）的值（以空格或者回車分隔） */ printf(a+b=%dn,a+b); 利用海倫公式可以求得三角形面積為：利用海倫公式可以求得三角形面積為： 其中，其中，s=(a+b+c)/2，a、b

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

11、角形的信息信息角形的信息信息 構(gòu)成三角形？構(gòu)成三角形？ YN 二.選擇結(jié)構(gòu) 開始開始 對三邊長賦值對三邊長賦值 計算計算s值值 計算面積計算面積area 結(jié)束結(jié)束 輸出三角形面積輸出三角形面積area 選擇結(jié)構(gòu) 引：輸入一個小寫字母，變成大寫后輸出引：輸入一個小寫字母，變成大寫后輸出 #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.判斷輸入的一個字符，如果是小寫字母，變成大寫后輸出判斷輸入的一個字符，如果是小寫字母，變成大寫后輸出 #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.任意給定兩個數(shù)任意給定兩個數(shù)a a，b b，將它們按從大到小的次序進行排序。，將它們按從大到小的次序進行排序。 #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.晶晶約會：周一、三、五均有課晶晶約會：周一、三、五均有課 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組三角形的三組三角形的三 條邊長，對每組數(shù)據(jù)進行條邊長，對每組數(shù)據(jù)進行 判斷，如果能構(gòu)成三角形則計算三角形的面積，否則，判斷，如果能構(gòu)成三角形則計算三角形的面積，否則， 輸出輸出“不能構(gòu)成三角形不能構(gòu)成三角形”。 Y N Y 開始開始 輸入三條邊長輸入三條邊長 計算面積并輸出計算面積并輸出 結(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）使得隨機數(shù)種子隨時 間的變化而變化。 l time函數(shù)可以獲取當(dāng)前的系統(tǒng)時間，返回從 CUT（Coordinated Universal Time）時間 1970年1月1日00:00:00到當(dāng)前時刻的秒數(shù)。 l rand()返回從0-32767的整數(shù) l srand 和 rand 應(yīng)該組和使用 算法（算法（Algorithm）是一組明確的、可以執(zhí)行的步驟的）是一組明確的、可以執(zhí)行的步驟的 有序集合。有序集合。 l 有窮性有窮性 l 確切性確切性 l 有有0個或多個輸入個或多個輸入 l 有有1個或多個輸出個或多個輸出 l 有效性有效性 二二. .算法算法 算法評價 算法評

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

19、數(shù)為3n+3。 當(dāng)n無限增大時，n的系數(shù)3和需要加的3均可忽略，因此記做時間復(fù)雜度為時間復(fù)雜度為 O(n)。 解決方案1（普通求和） int sum = 0, n = 100; for (int i = 1; i sum； 步驟2：使i為1； 步驟3：將sum與i相加，結(jié)果仍放到變量sum中，寫成 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。 流程圖是通過箭頭相互連接的幾何圖形來表達的方法。流程圖是通過箭頭相互連接的幾何圖形來表達的方法。 ANSI規(guī)定 的一些常 用流程圖 符號。 起止框 輸入輸出框 判斷框 處理框 流程線 1.1.認識算法認識算法算法的算法的描述工具描述工具 sum=0 n=1 n=10 sum=sum+n n=n+1 輸出輸出sum N Y 結(jié)束結(jié)束 開始開始 【示例示例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時

21、，做時，做 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); 用計算機語言表示算法用計算機語言表示算法 【算法思想算法思想】 l 掃描整個序列，從中選出最小的元素，將它與序列的第一個元素交換； l 然后再在余下的元素中找出最小數(shù)據(jù)的元素，與序列的第二個元素相互交換 位置 l 然后對剩下的序列采用同樣的方法，直到序列空為止。 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 在每一輪的排序過程中

23、從第一個數(shù)開始，相鄰兩數(shù)依次比較，當(dāng)發(fā)現(xiàn)前一個數(shù)據(jù) 比后一個數(shù)據(jù)大時，即將這兩個數(shù)據(jù)進行互換。 l 較小的數(shù)據(jù)就會逐個向前移動，大者往后移動，最后將序列中的最大值換到了序 列的最后。 經(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. 初始時，a0自成1個有序區(qū)，無序區(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)典排序算法：插入法排序 【算法思想算法思想】 每次將一個待排序的記錄，按其關(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ù)進行比較 l 如果相等，說明找到，宣布查找成功，記錄數(shù)組下標，算法結(jié)束； l 如果不相等，說明沒有找到，此時應(yīng)判斷是否還有剩余的數(shù)據(jù)，如果 還有剩余的數(shù)據(jù)則繼續(xù)和剩余的數(shù)據(jù)比較，如果沒有剩余的數(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表示查找 范圍的起點位置，b代表查找范圍的末尾，m id表示查找范圍的中間位置， mid=(t+b)/2。 第