第7章算法與程序設計

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

2、言匯編語言匯編語言低級語言低級語言計算機語言計算機語言面向問題的語言面向問題的語言面向過程的語言面向過程的語言面向對象的語言面向對象的語言C C、PascalPascal、FortranFortranVisual FoxProVisual FoxProC+C+、 Java Java 機器語言機器語言是用二進制代碼表示的計算機能直接識別和執(zhí)行的一種機器指令的集合。是用二進制代碼表示的計算機能直接識別和執(zhí)行的一種機器指令的集合。機器語言的所有指令都是由機器語言的所有指令都是由0 0、1 1組成的二進制。組成的二進制。操作碼操作碼操作數(shù)操作數(shù)例如，計算例如，計算A=15+10A=15+10的機器語言

3、程序如下：的機器語言程序如下：10110000 00001111 10110000 00001111 把把1515放到累加器放到累加器A A中中00101100 00001010 1000101100 00001010 10與累加器與累加器A A的值相加，結果仍放入的值相加，結果仍放入A A中中11110100 11110100 結束，停機結束，停機格式格式機器語言 匯編語言匯編語言用一些簡潔的英文字母、符號串來替代一個特定的指令的二進制串，例如，用一些簡潔的英文字母、符號串來替代一個特定的指令的二進制串，例如，用用“ADD”“ADD”代表加法，代表加法，“MOV”“MOV”代表數(shù)據(jù)傳遞等等。

4、代表數(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的值相加，結果仍放入的值相加，結果仍放入A A中中HLT HLT 結束，停機結束，停機匯編語言 高級語言高級語言例如，計算例如，計算A=15+10A=15+10的的C C語言程序如下：語言程序如下：#include #include main() main() int int a;a; a=15+10; a=15+10; printf(“%d”,a);

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

6、成用機器語言表示的與之等價的目標程序。程序整個地翻譯成用機器語言表示的與之等價的目標程序。解釋解釋程序是在源程序進入計算機時，通過解釋程序邊掃描邊解釋，逐句輸入，逐句翻譯，計程序是在源程序進入計算機時，通過解釋程序邊掃描邊解釋，逐句輸入，逐句翻譯，計算機一句句執(zhí)行，并不產(chǎn)生目標程序。算機一句句執(zhí)行，并不產(chǎn)生目標程序。共用體共用體數(shù)據(jù)類型數(shù)據(jù)類型基本類型基本類型整整型型實型實型字符型字符型單精度單精度雙精度雙精度非基本類型非基本類型數(shù)組數(shù)組結構體結構體指針類型指針類型枚舉型枚舉型3.3.數(shù)據(jù)類型數(shù)據(jù)類型l整型整型 ：int(如如 0,67, -2)l實型：實型：float、double(如如 2

7、.3, 1.2e-5)l字符型：字符型：char(如如 z, 3, $, 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”,&ai); for(i=0;i5;i+) printf(“%d”, ai); l數(shù)組元素求和數(shù)組元素求和int i,sum=0,a5=1,2,3,4,5;for(i=0;i

8、5;i+) sum=sum+ai; l 結構化程序設計結構化程序設計l 面向對象的程序設計面向對象的程序設計4.4.程序設計方法程序設計方法l 自頂向下自頂向下l 逐步求精逐步求精l 模塊化模塊化l 限制使用限制使用goto語句語句結構化程序設計結構化程序設計ABBAPPA順序結構順序結構選擇結構選擇結構循環(huán)結構循環(huán)結構程序的三種主要結構程序的三種主要結構PA當型循環(huán)當型循環(huán)直到型循環(huán)直到型循環(huán)一.順序結構#include /*使用標準函數(shù)庫中的輸入輸出函數(shù)時需引用該頭文件*/main() printf(Hello,World!n);程序員的第一個程序順序結構v 輸入整數(shù)輸入整數(shù)a、b并求和并

9、求和#includemain() int a,b; printf(Please input a and b:n); scanf(%d,%d,&a,&b);/* 從鍵盤輸入從鍵盤輸入a、b的值（以空格或者回車分隔）的值（以空格或者回車分隔） */ printf(a+b=%dn,a+b);利用海倫公式可以求得三角形面積為：利用海倫公式可以求得三角形面積為： 其中，其中，s=(a+b+c)/2，a、b、c是三條邊長是三條邊長2. 已知三角形的三條邊長，計算三角形的面積。已知三角形的三條邊長，計算三角形的面積。開始開始對三邊長賦值對三邊長賦值計算計算s值值計算面積計算面積area結束結

10、束輸出三角形面積輸出三角形面積area順序結構【示例示例7-4】輸入三角形的三輸入三角形的三 條邊長，如果能構成三角形則計算三角形的面積，否則，輸出條邊長，如果能構成三角形則計算三角形的面積，否則，輸出“不能構成三角形不能構成三角形”。開始開始輸入三條邊長輸入三條邊長計算計算s值值計算面積計算面積area結束結束輸出三角形面積輸出三角形面積area輸出不能構成三角形的信輸出不能構成三角形的信息信息息信息構成三角形？構成三角形？YN二.選擇結構開始開始對三邊長賦值對三邊長賦值計算計算s值值計算面積計算面積area結束結束輸出三角形面積輸出三角形面積area選擇結構引：輸入一個小寫字母，變成大寫后

11、輸出引：輸入一個小寫字母，變成大寫后輸出#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(“input a letter:”); a=getchar( ); if(a=a&a=z) a=a-32; printf(“%cn”,a);1.判斷輸入的一個字符，如果是小寫字母，變成大寫后輸出判斷輸入的一個字符，如果是小寫字母，變成大寫后輸出#inclu

12、demain() int a,b; printf(Please input 2 numbers:); scanf(%d%d,&a,&b); if(ab) printf(%d,%d,a,b); else printf(%d,%d,b,a);2.2.任意給定兩個數(shù)任意給定兩個數(shù)a a，b b，將它們按從大到小的次序進行排序。，將它們按從大到小的次序進行排序。#includemain() int a; printf(“Please input the day you want to date:”）; scanf(%d,&a); if(a=1|a=3|a=5)printf(NO

13、); else printf(YES); 3. 3.晶晶約會：周一、三、五均有課晶晶約會：周一、三、五均有課4.4.判斷輸入的年份是否為閏年判斷輸入的年份是否為閏年main() int year; printf(Please input the year:); scanf(%d,&year); if (year%4=0&year%100 != 0|year%400=0) printf(%d is a leap year.n,year); else printf(%d is not a leap year.n,year);【例例】輸入輸入5組三角形的三組三角形的三 條邊長，對每組

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

15、 i; float average; for(i=1;i=10;i+) printf(“n Input No.%d score:”, i ); scanf(%d,&score); 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 your number（1-100）：）：);scanf(%d,&g

16、);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,&g); j+;t=time(NULL)-t;printf(nCongratulations！You got the right answer with %d times，uesed %d second。n,j,t);lsrand（time（NULL）使得隨機數(shù)種子隨時間的變化而變

17、化。ltime函數(shù)可以獲取當前的系統(tǒng)時間，返回從CUT（Coordinated Universal Time）時間1970年1月1日00:00:00到當前時刻的秒數(shù)。lrand()返回從0-32767的整數(shù)lsrand 和 rand 應該組和使用 算法（算法（Algorithm）是一組明確的、可以執(zhí)行的步驟的有序集合。）是一組明確的、可以執(zhí)行的步驟的有序集合。l 有窮性有窮性l 確切性確切性l 有有0個或多個輸入個或多個輸入l 有有1個或多個輸出個或多個輸出l 有效性有效性二二. .算法算法 算法評價算法評價l正確性正確性l時間復雜度時間復雜度（計算機上運行所花費的時間）*l空間復雜度空間復雜

18、度（算法運行過程中臨時占用的存儲空間的大?。?測定運行時間最可靠的方法就是計算對運行時間有消耗的基本操作計算對運行時間有消耗的基本操作（如（如“運算運算”、“條件比較條件比較”、“變量代入變量代入”）的執(zhí)行次數(shù)）的執(zhí)行次數(shù)，運行時間與該計數(shù)成正比。 算法的復雜度標記方法一般采用“O記法記法”。在O記法中，算法的復雜度是以處理對象數(shù)據(jù)的數(shù)量n為基準來記述的?！纠壳笄?+2+3+1001+2+3+100 普通求和中，數(shù)據(jù)量為n時，時間復雜度是1+1+(n+1)+n+n=3n+3，操作次數(shù)為3n+3。 當n無限增大時，n的系數(shù)3和需要加的3均可忽略，因此記做時間復雜度為時間復雜度為O(n)。解決

19、方案1（普通求和）int sum = 0, n = 100; for (int i = 1; i sum；步驟2：使i為1；步驟3：將sum與i相加，結果仍放到變量sum中，寫成sum+i=sum；步驟4：使i的值加1，即i+1=i；步驟5：如果i的值不大于11（i10），返回重新執(zhí)行第3步和其后的步驟4和步驟5；否則，算法結束，sum的值即為所求。方法一：方法一：步驟1：先求1與2的和，得到結果3；步驟2：將步驟1得到的和與3相加，得到結果6；步驟3：將步驟2得到的和與4相加，得到結果10；步驟9：將步驟8得到的和與10相加，得到結果55。流程圖是通過箭頭相互連接的幾何圖形來表達的方法。流程

20、圖是通過箭頭相互連接的幾何圖形來表達的方法。ANSI規(guī)定的一些常用流程圖符號。起止框輸入輸出框判斷框處理框流程線1.1.認識算法認識算法算法的算法的描述工具描述工具sum=0n=1n=10sum=sum+nn=n+1輸出輸出sumNY結束結束開始開始【示例示例7-1】求求1+2+3+10，即，即101nn流程圖流程圖sum=0，n=1sum=sum+nn=n+1輸出輸出sum的值的值當當i=10時，做時，做N-S圖圖用流程圖用流程圖/N-S/N-S圖表示算法圖表示算法【示例示例7-1】求求1+2+3+10，即，即101nn#include main() int sum=0,n=1; for(n

21、=1;n=10;n+) sum=sum+n; printf(sum=%dn,sum);用計算機語言表示算法用計算機語言表示算法【算法思想算法思想】l掃描整個序列，從中選出最小的元素，將它與序列的第一個元素交換；l然后再在余下的元素中找出最小數(shù)據(jù)的元素，與序列的第二個元素相互交換位置l然后對剩下的序列采用同樣的方法，直到序列空為止。2.經(jīng)典算法 排序算法：選擇排序#include main() int i,index,k,n,temp,a5; printf(“Please input 5 numbers:n”); for(k=0;k5;k+) scanf(%d,&ak); for(k=0

22、;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在每一輪的排序過程中從第一個數(shù)開始，相鄰兩數(shù)依次比較，當發(fā)現(xiàn)前一個數(shù)據(jù)比后一個數(shù)據(jù)大時，即將這兩個數(shù)據(jù)進行互換。l較小的數(shù)據(jù)就會逐個向前移動，大者往后移動，最后將序列中的最大值換到了序列的最后。經(jīng)典排序算法：冒泡法經(jīng)典排序算法：冒泡法排序#includ

23、emain()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 array isn);for(i=0;in;i+)printf(%d ,ai); 冒泡法排序冒泡法排序設數(shù)組為設數(shù)組為an：1. 初始時，a0自成1個有序區(qū)，無序區(qū)為a1.n-1。令i=12. 將ai并入當前的有序區(qū)a0i-1中形成a0i的有序區(qū)間。3. i

24、+并重復第二步直到i=n-1。排序完成。經(jīng)典排序算法：插入法經(jīng)典排序算法：插入法排序【算法思想算法思想】 每次將一個待排序的記錄，按其關鍵字大小插入到前面已經(jīng)排好序的子序列中的適當位置，直到全部記錄插入完成為止。main() int i,j,n=7,temp,a7=12,15,9,20,6,31,24; for (i = 1; i n; i+) if (ai = 0 & aj temp; j-) aj + 1 = aj; aj + 1 = temp; 插入法排序插入法排序【算法思想算法思想】l逐一將數(shù)組的數(shù)據(jù)與輸入數(shù)進行比較l如果相等，說明找到，宣布查找成功，記錄數(shù)組下標，算法結束；l

25、如果不相等，說明沒有找到，此時應判斷是否還有剩余的數(shù)據(jù)，如果還有剩余的數(shù)據(jù)則繼續(xù)和剩余的數(shù)據(jù)比較，如果沒有剩余的數(shù)據(jù)，則宣布查找失敗，算法結束輸入：輸入： 2 9 8 10 6查找：查找： 9輸出：輸出：2輸入：輸入：2 9 8 10 6查找：查找：7輸出：輸出：Not Found 經(jīng)典查找算法：順序查找經(jīng)典查找算法：順序查找-輸入一組數(shù)據(jù)，再輸入需要查找的數(shù)x，如果找到，輸出相應的位置，否則，輸出Not Found。 #includemain() int i,x,a5; printf(Please input 5 numbers:n); for(i=0;i5;i+) scanf(%d,&ai); printf(Please input the number you want to find:n); scanf(%d,&x);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。第