第8章算法與程序設計語言

算法與程序設計語言一算法與程序什么是程序？按一定的順序安排的工作即操作序列描述完成某項功能所涉及的對象和動作規(guī)則計算機學科中,程序描述了計算機處理數(shù)據(jù)、解決問題的過程2程序和算法的關系是怎樣的？

引例:從存放教職工檔案的“d:\zgxx.txt”文件中，顯示出教齡滿30年的女教工的姓名和所在部門3程序=數(shù)據(jù)結(jié)構(gòu)+算法程序包括兩方面的內(nèi)容：（1）對數(shù)據(jù)的描述:指定欲處理的數(shù)據(jù)類型和數(shù)據(jù)的組織形式，也就是數(shù)據(jù)結(jié)構(gòu)。例如教職工的姓名,部門,教齡等都具有相應的數(shù)據(jù)類型文件d:\zgxx.txt指定了數(shù)據(jù)的組織形式。（2）對操作的描述:指定操作步驟，例如“fopen”打開文件、“fscanf”讀入數(shù)據(jù)、“If”判斷是否滿足條件等。這些操作的先后順序以及它們所作用的數(shù)據(jù)，要遵守一定的規(guī)則，即求解問題的的算法。二算法的概念1什么是算法?計算機來解決的某一類問題的方法或步驟算法是程序的核心例:小球稱重

9個編號小球中有一個的質(zhì)量偏小，其余的質(zhì)量標準。用一天平,無需砝碼，檢出質(zhì)量偏小的小球。4解法一：9個小球分成5堆，（1,2）,（3,4）,（5,6）,（7,8）,（9）解法二：可將9個小球分成3堆進行稱量,(1,2,3),(4,5,6),(7,8,9),若1,2相等,則稱量第三堆中,否則對偏輕的一堆繼續(xù)稱量。5哪種方法稱量次數(shù)最少?解法三：先將小球分成（1，2，3，4）與（5，6，7，8）兩堆，若兩堆的質(zhì)量的相等則偏小的小球是第9個，否則將偏輕的小球分成兩堆進行稱量。例:圓周率的計算(1)割圓法6S正12邊形=12×△S=3圓周率=S正12邊形/R/R=3算法步驟：①量出圓的半徑R②做圓的內(nèi)接正n邊形③求小三角形的面積△S④求圓的內(nèi)接正n邊形面積S=△S×n⑤求圓周率=S/R/R⑥結(jié)束公元3世紀，劉徽利用“割圓術”，也就是利用圓內(nèi)接正六邊形算起，依次將邊數(shù)加倍，一直算到內(nèi)接正3072邊形的面積，從而得到圓周率的近似值為=3.1416，祖沖之把圓周率精確到小數(shù)點后15位7(2)利用求圓周率公式

同一個問題，可用不同的算法來求解算法不同，求解的效率不同選擇效率高、容易理解和編程實現(xiàn)的算法2算法的兩個要素算法是由操作與控制結(jié)構(gòu)兩個要素組成（1）操作①算術運算：加、減、乘、除等。②關系運算：大于、大于等于、小于、小于等于、等于、不等于等。③邏輯運算：與、或、非等。④數(shù)據(jù)傳送：輸入、輸出、賦值等。8(a)順序結(jié)構(gòu)

(b)選擇結(jié)構(gòu)（2）控制結(jié)構(gòu)各操作之間的執(zhí)行順序順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，稱為算法的三種基本結(jié)構(gòu)9

A

B

條件

B

A

成立

不成立

(c)當型循環(huán)結(jié)構(gòu)(d)直到型循環(huán)結(jié)構(gòu)10成立

不成立

A

成立

不成立

條件

A

條件

輸出count開始置初態(tài)：累加器count←0;到文件結(jié)尾了嗎？輸出職工信息,Count++結(jié)束falsetrue從整體上看是順序結(jié)構(gòu)11打開文件教齡>30且性別為女？從文件中讀入一行truefalse當型循環(huán)3算法的特點有窮性

任意一個算法在執(zhí)行有窮個計算步驟后必須終止。每一個計算步驟，必須是精確地定義、無二義性可行性

有限多個步驟應該在一個合理的范圍內(nèi)進行輸入

一般有0個或多個輸入，它們?nèi)∽阅骋惶囟ǖ募?。輸?/p>

一般有若干個輸出信息，是反映對輸入數(shù)據(jù)加工后的結(jié)果。124算法的分類（1）數(shù)值計算算法

用于科學計算特點是少量的輸入、輸出，復雜的運算。例如：計算圓周率，積分（2）非數(shù)值計算算法

對數(shù)據(jù)的管理特點是大量的輸入、輸出，簡單的算術運算和大量的邏輯運算。例如：排序查找替換

隨著計算機技術的發(fā)展和應用面的普及，非數(shù)值計算算法涉及面更廣，研究的任務更重。135算法的表示自然語言傳統(tǒng)流程圖N-S流程圖偽代碼計算機語言14利用求圓周率公式

計算圓周率分析:對通項式：ti=，i=1，2，…，進行累加，直到某項ti絕對值小于精度即|t|<10-8為止。15自然語言①置初態(tài)：累加器pi←0，計數(shù)器i←1，第1項t←1，正負符號變化s←1；②重復執(zhí)行下面的語句，直到某項絕對值小于精度，轉(zhuǎn)③；求累加和：pi←pi+t；為下一項作準備：i←i+1、s←-1*s、t←s*1/(2*i-1)；③輸出：顯示結(jié)果pi*4。④結(jié)束優(yōu)點:通俗易懂缺陷：（1）不太嚴格，易產(chǎn)生歧義性。（2）繁瑣、冗長，并且很難清楚地表達算法的邏輯流程，不直觀。16傳統(tǒng)流程圖采用一些圖框、線條以及文字說明來形象地、直觀地描述算法處理過程。17false輸出pi*4開始pi←0;s←1i←1;t←1|t|≥10-8pi←pi+ts←-1*si←i+1t←s*1/(2*i-1)結(jié)束true計算圓周率的流程圖缺陷：制作費時優(yōu)點:較好地體現(xiàn)程序設計的邏輯18N-S流程圖由美國學者I.Nassi和B.Shneideman提出去掉了傳統(tǒng)流程圖中帶箭頭的流向線,全部算法以一個大的矩形框表示，該框內(nèi)還可以包含一些從屬于它的小矩形框適于結(jié)構(gòu)化程序設計。19

計算圓周率N-S圖

N-S圖的三種控制結(jié)構(gòu)20BEGIN

pi←0//變量賦初值

s←1

i←1

t←1

While(|t|≥10-8)

{

pi←pi+t//計算累加和

s←-1*si←i+1t←s*1/(2*i-1)//計算通項}Printpi*4//輸出圓周率值End有如下簡單約定：用Begin開始、End結(jié)束；每一條指令占一行“//”標志表示注釋輸入/輸出以Input/Print表示；用“”表示賦值；用縮進表示代碼塊結(jié)構(gòu)，塊中多句語句用一對{}括起；數(shù)組形式：數(shù)組名[下界‥上界]；數(shù)組元素：數(shù)組名[序號]；一些函數(shù)調(diào)用或者處理簡單任務可以用一句自然語言代替。偽代碼:用介于自然語言和計算機語言之間的文字和符號來描述算法。21計算機語言#include"iostream.h" //文件包含，作用為輸入和輸出#include"iomanip.h" //文件包含，作用為輸入和輸出#include"math.h" //包含數(shù)學函數(shù)voidmain(){ ints,i; //s為控制正負號變化，i為第i項

doublepi,t; //pi存放累加和項，t當前某項

pi=0; s=i=t=1; while(abs(t)>=0.00000001)//當當前項還沒有到達精度，繼續(xù)求和

{ pi=pi+t; //求和

s=-1*s; //為下一項作準備，符號變化/ i++; // t=s*1.0/(2*i-1); //下一項值

} cout<<setprecision(8)<<pi*4<<endl;}只有用計算機語言編寫的程序才能被計算機執(zhí)行必須嚴格遵循所選擇的編程語言的語法規(guī)則22三常用算法枚舉法迭代法排序選擇法冒泡法查找順序查找二分查找23枚舉法亦稱窮舉法或試湊法。例：計算機破案

張三在家中遇害，偵查中發(fā)現(xiàn)A、B、C、D四人到過現(xiàn)場。A說：“我沒有殺人?！盉說：“C是兇手。”C說：“殺人者是D”D說：“C在冤枉好人?！眰刹閱T經(jīng)過判斷四人中有三人說的是真話，四人中有且只有一人是兇手，兇手到底是誰？24分析

用0表示不是兇手，1表示兇手，則每個人的取值范圍就是[0，1]25算法

在每個人的取值范圍[0，1]的所有可能中進行搜索，如果表格的組合條件同時滿足，即為兇手。相應的偽代碼為：ForA=0To1ForB=0TO1ForC=0To1ForD=0To1If((A=0)+(C=1)+(D=1)+(D=0))=3And(A+B+C+D=1)PrintA,B,C,D//輸出的值是1的為兇手，要同時滿足26例:安排考試3門課程為A、B、C，考試安排在周一到周六，先考A，后考B，最后考C課程；一天只能安排一門課程考試；最后課程只能安排在周5或周6，請列出安排考試的所有方案。分析：解決該問題關鍵是根據(jù)安排日期的規(guī)定，每門課程搜索的日期范圍不同；ForA=1To4ForB=A+1To5//B課程總比A晚考

ForC=5To6//C最早周5考

If(B<C)//排除B=C的情況，不能在同一天考

PrintA,B,C//輸出的值是A、B、C分別安排的考試周的星期幾27總結(jié)枚舉法基本思想:采用搜索的方法，根據(jù)題目的部分條件確定答案的大致搜索范圍在此范圍內(nèi)對所有可能的情況逐一驗證若某個情況符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解。枚舉法是一種比較耗時的算法。為提高效率，根據(jù)解決問題的情況，盡量減少內(nèi)循環(huán)層數(shù)或每層循環(huán)次數(shù)。28迭代法又稱遞推法，利用問題本身所具有的某種遞推關系求解問題。例：猴子吃桃問題

小猴有桃若干，當天吃掉一半多一個；第二天接著吃了剩下的桃子的一半多一個；以后每天都吃尚存桃子的一半零一個，到第7天早上只剩下1個了，問小猴原有多少個桃子？29設第n天的桃子為xn，它是前一天的桃子數(shù)的一半少1個，即xn-1=(xn+1)×2（遞推公式）30總結(jié)迭代法的基本思想:

從初值出發(fā)，歸納出新值與舊值間直到最后值為止存在的關系，從而把一個復雜的計算過程轉(zhuǎn)化為簡單過程的多次重復，每次重復都從舊值的基礎上遞推出新值，并由新值代替舊值。31排序常用排序算法選擇法冒泡法插入排序合并排序快速排序32(1)選擇法將N個數(shù)按照從小到大的順序排序原始數(shù)據(jù)869327過程演示算法思想:每次在無序數(shù)中找最?。ㄟf增）數(shù)的下標，然后存放在無序數(shù)的第一個位置Fori=0Ton-2//n個數(shù)進行n-1輪比較

{min←i//每一輪內(nèi)，假定當前個最小

Forj=i+1Ton-1Ifa[j]<a[min]min←j//記錄當前的最小元素，替換mina[i]元素與a[min]元素交換//一輪結(jié)束，最小的元素放在a[i]位置

}33(2)冒泡法①從第一個元素開始，對數(shù)組中兩兩相鄰的元素比較，即a[0]與a[1]比若為逆序，則a[0]與a[1]交換；然后a[1]與a[2]比較，…，直到最后a[n-2]與a[n-1]比較，這時一輪比較完畢，一個最大的數(shù)“沉底”，成為數(shù)組中的最后一個元素a[n-1]，一些較小的數(shù)如同氣泡一樣“上浮”一個位置。②然后對a[0]～a[n-2]的n-1個數(shù)進行同①的操作，次最大數(shù)放入a[n-2]元素內(nèi)，完成第二輪排序；依次類推，進行n-1輪排序后，所有數(shù)均有序，第3輪比較后，實際數(shù)組已經(jīng)有序，后面兩輪比較是多余,如何解決?34Fori=0Ton-2//n個數(shù)進行n-1輪比較

Forj=0Ton-2-i//每一輪內(nèi)

Ifa[j]>a[j+1]//若相鄰兩個次序不對

a[j]與a[j+1]元素交換//則交換位置，小數(shù)上浮，大數(shù)下沉Fori=0Ton-2//n個數(shù)進行n-1輪比較{noswap←true//數(shù)據(jù)不需交換,即已經(jīng)有序

Forj=0Ton-2-i//每一輪內(nèi)

Ifa[j]>a[j+1]//若相鄰兩個次序不對

{a[j]與a[j+1]元素交換//則交換位置，小數(shù)上浮，大數(shù)下沉

noswap←false//一旦交換過，noswap設置為flase}Ifnoswap數(shù)據(jù)已經(jīng)有序提前結(jié)束//一輪比較結(jié)束，根據(jù)noswap值判斷數(shù)據(jù)有序否

}數(shù)據(jù)已經(jīng)有序后,后續(xù)的比較可省略查找35已知姓名,怎么查找某個學生?已知學號,怎么查找某個學生?1251252高靖遙男交通運輸類1251254李一鳴男交通運輸類1251259張曉敏女交通運輸類1251269施奕辰男交通運輸類1251270方堯男交通運輸類1251271應一丹女交通運輸類1251273王子恒男交通運輸類1251278黃彬男交通運輸類1251281朱一鳴男交通運輸類1251283陳鈺女交通運輸類1251285王羿童男交通運輸類1251298鄧能靜女交通運輸類1251306王寒冰男交通運輸類1251314陳彥旭男交通運輸類1251328溫馨女交通運輸類1251329劉建興男交通運輸類1251330彭洋男交通運輸類(1)順序查找

適用于無序序列，按順序逐一比對。例：輸入一個數(shù)key，查找它是否在數(shù)列中，如在，輸出是第幾個數(shù)。36(2)二分查找二分法查找只適合于在已排好序的數(shù)組中進行。①待查區(qū)間的下界low為1，上界high為N。②求待查區(qū)間中間元素的下標mid=(low+high)/2，x和a[mid]比較。③若x==a[mid]，則查找完畢，結(jié)束程序；若x>a[mid]，low=mid+1；若x<a[mid]，high=mid-1；④重復第2、3步，直到找到x；或low>high無查找區(qū)域，找不到3738程序設計語言

解決某個問題的算法設計完成后，必須要使用合適的程序設計語言來實現(xiàn)這一算法，即編寫解決該問題的程序，運行該程序以獲得結(jié)果。系統(tǒng)軟件

40操作系統(tǒng)語言處理程序?qū)嵱贸绦蚍g工具作用：將源程序翻譯成計算機能識別的機器語言程序。程序設計語言：機器語言匯編語言高級語言典型的程序設計語言有：FORTRAN、Pascal、C與C++、BASIC、Java、C#等。匯編程序編譯程序解釋程序411.機器語言

由“0”、“1”二進制代碼按一定規(guī)則組成的、能被機器直接理解、執(zhí)行的指令集合。

缺點：編程工作量大，難學、難記、難修改；

不同計算機的指令系統(tǒng)不同，機器語言通用性差優(yōu)點：代碼不需要翻譯，所占空間少，執(zhí)行速度快。例如，計算A=15+10的機器語言程序如下：1011000000001111 ：把15放入累加器A中0010110000001010 ：10與累加器A的值相加，結(jié) 果仍放入A中11110100 ：結(jié)束，停機422.匯編語言使用反映機器指令功能的助記符代替機器語言的符號語言。例如用ADD表示加、SUB表示減、JMP表示程序跳轉(zhuǎn)等等。優(yōu)點：克服了機器語言難讀等缺點，保持了其編程質(zhì)量高、占存儲空間少，執(zhí)行速度快的優(yōu)點。缺點：仍然依賴于機器，通用性差。特點：源程序必須通過匯編程序翻譯成機器語言。常用于過程控制等編程。例如，計算A=15+10的匯編語言程序：MOV A，15 ：把15放入累加器A中ADD A，10 ：10與累加器A相加，結(jié)果存入A中HLT ：結(jié)束，停機類比：

IP地址46機器語言域名匯編語言433.高級語言接近于自然語言和數(shù)學公式的程序設計語言。優(yōu)點：接近算法語言，易學、易掌握，可讀性好，可維護性強，可靠性高；可移植性好，重用率高自動化程度高，編程效率高。缺點：源程序要通過翻譯程序翻譯成機器語言，代碼不最優(yōu)。例如，計算A=15+10的BASIC語言程序如下：A=15+10 ‘15與10相加的結(jié)果放入A中PRINTA ‘輸出AEND ‘程序結(jié)束語言處理程序44機器語言源程序匯編語言源程序機器語言程序（目標程序）匯編程序翻譯低級語言處理程序高級語言翻譯程序45高級語言源程序計算結(jié)果解釋程序數(shù)據(jù)高級語言源程序計算結(jié)果連接程序數(shù)據(jù)目標程序可執(zhí)行程序編譯程序解釋方式編譯方式BasicC++程序庫可脫離編譯程序和源程序獨立存在并反復使用程序設計的一般過程46分析問題確定數(shù)學模型程序編寫、編輯、編譯和連接算法設計運行和測試程序設計方法結(jié)構(gòu)化程序設計面向?qū)ο蟪绦蛟O計47結(jié)構(gòu)化程序設計思想最早由荷蘭科學家E.W.Dijkstra提出任何程序都基于順序、選擇、循環(huán)三種基本的控制結(jié)構(gòu)程序具有模塊化特征，每個程序模塊具有惟一的入口和出口取消GOTO語句結(jié)構(gòu)化程序的結(jié)構(gòu)簡單清晰，可讀性好，模塊化強。48結(jié)構(gòu)化編程主要包括兩個方面提倡采用自頂向下、逐步