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

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

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

3、程序如下：的機(jī)器語言程序如下：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ī)器語言 匯編語言匯編語言用一些簡潔的英文字母、符號串來替代一個特定的指令的二進(jìn)制串，例如，用一些簡潔的英文字母、符號串來替代一個特定的指令的二進(jìn)制串，例如，用用“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的值相加，結(jié)果仍放入的值相加，結(jié)果仍放入A A中中HLT HLT 結(jié)束，停機(jī)結(jié)束，停機(jī)匯編語言 高級語言高級語言例如，計算例如，計算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ù)構(gòu)成，有且有一個主函數(shù)程序由函數(shù)構(gòu)成，有且有一個主函數(shù)l 程序執(zhí)行時總是從程序執(zhí)行時總是從main()函數(shù)開始函數(shù)開始l 語句必須以語句必須以“；”結(jié)束，書寫格式自由結(jié)束，書寫格式自由l “#”開頭的為編譯預(yù)處理命令開頭的為編譯預(yù)處理命令l 利用利用/* */作為注釋作為注釋機(jī)器語言機(jī)器語言高級語言高級語言書寫書寫翻譯翻譯執(zhí)行執(zhí)行編譯編譯是指事先編好的一個稱為編譯程序的機(jī)器語言程序，通過編譯程序把高級語言書寫的源是指事先編好的一個稱為編譯程序的機(jī)器語言程序，通過編譯程序把高級語言書寫的源程序整個地翻譯

6、成用機(jī)器語言表示的與之等價的目標(biāo)程序。程序整個地翻譯成用機(jī)器語言表示的與之等價的目標(biāo)程序。解釋解釋程序是在源程序進(jìn)入計算機(jī)時，通過解釋程序邊掃描邊解釋，逐句輸入，逐句翻譯，計程序是在源程序進(jìn)入計算機(jī)時，通過解釋程序邊掃描邊解釋，逐句輸入，逐句翻譯，計算機(jī)一句句執(zhí)行，并不產(chǎn)生目標(biāo)程序。算機(jī)一句句執(zhí)行，并不產(chǎn)生目標(biāo)程序。共用體共用體數(shù)據(jù)類型數(shù)據(jù)類型基本類型基本類型整整型型實型實型字符型字符型單精度單精度雙精度雙精度非基本類型非基本類型數(shù)組數(shù)組結(jié)構(gòu)體結(jié)構(gòu)體指針類型指針類型枚舉型枚舉型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 ) 用用開頭的字符為轉(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”,&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 結(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è)計ABBAPPA順序結(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)PA當(dāng)型循環(huán)當(dāng)型循環(huán)直到型循環(huán)直到型循環(huán)一.順序結(jié)構(gòu)#include /*使用標(biāo)準(zhǔn)函數(shù)庫中的輸入輸出函數(shù)時需引用該頭文件*/main() printf(Hello,World!n);程序員的第一個程序順序結(jié)構(gòu)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結(jié)束結(jié)

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

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，將它們按從大到小的次序進(jìn)行排序。，將它們按從大到小的次序進(jìn)行排序。#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ù)進(jìn)行判斷，如果能構(gòu)成三角形則計條邊長，對每組數(shù)據(jù)進(jìn)行判斷，如果能構(gòu)成三角形則計算三角形的面積，否則，輸出算三角形的面積，否則，輸出“不能構(gòu)成三角形不能構(gòu)成三角形”。YNY開始開始輸入三條邊長輸入三條邊長計算面積并輸出計算面積并輸出結(jié)束結(jié)束輸出相應(yīng)信息輸出相應(yīng)信息構(gòu)成三角形？構(gòu)成三角形？循環(huán)變量循環(huán)變量i=1i5？i=i+1N三.控制結(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)控制#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）使得隨機(jī)數(shù)種子隨時間的變化而變

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

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

19、方案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：將步驟2得到的和與4相加，得到結(jié)果10；步驟9：將步驟8得到的和與10相加，得到結(jié)果55。流程圖是通過箭頭相互連接的幾何圖形來表達(dá)的方法。流程

20、圖是通過箭頭相互連接的幾何圖形來表達(dá)的方法。ANSI規(guī)定的一些常用流程圖符號。起止框輸入輸出框判斷框處理框流程線1.1.認(rèn)識算法認(rèn)識算法算法的算法的描述工具描述工具sum=0n=1n=10sum=sum+nn=n+1輸出輸出sumNY結(jié)束結(jié)束開始開始【示例示例7-1】求求1+2+3+10，即，即101nn流程圖流程圖sum=0，n=1sum=sum+nn=n+1輸出輸出sum的值的值當(dāng)當(dāng)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);用計算機(jī)語言表示算法用計算機(jī)語言表示算法【算法思想算法思想】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ù)依次比較，當(dāng)發(fā)現(xiàn)前一個數(shù)據(jù)比后一個數(shù)據(jù)大時，即將這兩個數(shù)據(jù)進(jìn)行互換。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ù)組為設(shè)數(shù)組為an：1. 初始時，a0自成1個有序區(qū)，無序區(qū)為a1.n-1。令i=12. 將ai并入當(dāng)前的有序區(qū)a0i-1中形成a0i的有序區(qū)間。3. i

24、+并重復(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 = 1; i n; i+) if (ai = 0 & aj temp; j-) aj + 1 = aj; aj + 1 = temp; 插入法排序插入法排序【算法思想算法思想】l逐一將數(shù)組的數(shù)據(jù)與輸入數(shù)進(jìn)行比較l如果相等，說明找到，宣布查找成功，記錄數(shù)組下標(biāo)，算法結(jié)束；l

25、如果不相等，說明沒有找到，此時應(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)典查找算法：順序查找-輸入一組數(shù)據(jù)，再輸入需要查找的數(shù)x，如果找到，輸出相應(yīng)的位置，否則，輸出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表示查找范圍的起點(diǎn)位置，b代表查找范圍的末尾，m id表示查找范圍的中間位置，mid=(t+b)/2。第