算法設(shè)計(jì)及其應(yīng)用第三章

1、算法設(shè)計(jì)及其應(yīng)用目錄第一節(jié) 枚舉算法第二節(jié) 回溯算法第三節(jié) 貪心算法第四節(jié) 分治算法第五節(jié) 數(shù)值計(jì)算第六節(jié) 計(jì)算幾何第七節(jié) 模擬題解法 第一節(jié) 枚舉算法所謂枚舉算法，是指從可能的集合中一一枚舉各元素，用題目給定的檢驗(yàn)條件判定哪些是有用的，哪些是無(wú)用的。能使命題成立者，即為問(wèn)題的解。第一節(jié) 枚舉算法采用枚舉算法解題的基本思路如下：（1）建立問(wèn)題的數(shù)學(xué)模型，確定問(wèn)題的可能解的集合（可能解的空間）。（2）逐一枚舉可能解集合中的元素，驗(yàn)證是否是問(wèn)題的解。第一節(jié) 枚舉算法使用偽代碼可以描述為：for each s in S/S是問(wèn)題所有可能解的集合 if s is a solution then beg

2、in Write(s); exit the program; end;第一節(jié) 枚舉算法例3.1：尋找水仙花數(shù)一個(gè)三位數(shù)其各位數(shù)字的立方和等于它本身，這樣的數(shù)稱為水仙花數(shù)。要求找出所有的水仙花數(shù)分析：所求一定是三位數(shù)，所以范圍一定在100-999之間，只要將這些數(shù)逐一列舉，符合條件者為解第一節(jié) 枚舉算法For a:=100 to 999 do b:=a mod 10; /取出個(gè)位 c:=(a div 10) mod 10 /取出十位 d: a div 100 /取出百位 if (a=b*b*b+c*c*c+d*d*d) then writeln(a) 例3.2：經(jīng)典的百雞問(wèn)題：有一個(gè)人有一百塊錢

3、，打算買一百只雞。到市場(chǎng)一看，公雞三塊錢一只，母雞兩塊錢一個(gè)，小雞一塊錢三只?，F(xiàn)在，請(qǐng)你編一程序，幫他計(jì)劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？第一節(jié) 枚舉算法分析 :按照枚舉算法的思路，首先應(yīng)該構(gòu)造可能解的集合：S=(x,y,z)|0 x,y,z100，其中三元組(x,y,z)表示買公雞x只，母雞y只和小雞z只。因?yàn)橐还残枰I100只雞，因此，買公雞、母雞和小雞的數(shù)量都不會(huì)超過(guò)100。然后確定驗(yàn)證解的條件：x+y+z=100 and 3x+2y+z/3=100。第一節(jié) 枚舉算法下面是解這百雞問(wèn)題的程序：Program ex3_1_1;Var x,y,z:integer;begin

4、/枚舉可能解空間的元素第一節(jié) 枚舉算法 for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do if (x+y+z=100) and (x*3+y*2+zdiv 3=100) and (z mod 3=0) /驗(yàn)證可能解 then WriteLn(Format(x,y,z)=(%3d,%3d,%3d),x,y,z);end.第一節(jié) 枚舉算法程序輸出結(jié)果為：(x,y,z)=( 0, 40, 60)(x,y,z)=( 5, 32, 63)(x,y,z)=( 10, 24, 66)(x,y,z)=( 15, 16, 69)(x,y,z)=(

5、20, 8, 72)(x,y,z)=( 25, 0, 75)有6種可選的方案。第一節(jié) 枚舉算法程序需要循環(huán)1003，即|S|=1003。我們通過(guò)條件x+y+z=100來(lái)約束求解空間，縮小可能解的集合的規(guī)模：Program ex3_1_2;begin /枚舉可能解空間的元素 for (x=0;x=100;x+) for (y=0;y=100-x;y+) begin z:=100-x-y;if (x+y+z=100) and (x*3+y*2+z div 3=100) and (z mod 3=0) end;end.第一節(jié) 枚舉算法 程序ex3_1_2的運(yùn)行結(jié)果和程序ex3_1_1相同，但是循環(huán)次

6、數(shù)為（100*101/2），是程序ex3_1_1循環(huán)次數(shù)的1/200左右。第一節(jié) 枚舉算法枚舉算法適用范圍：簡(jiǎn)單數(shù)值判斷題；簡(jiǎn)單邏輯判斷題；數(shù)據(jù)規(guī)模不大的問(wèn)題；沒(méi)有想到更好解法的題，可用枚舉求出一定范圍內(nèi)的解。對(duì)于枚舉算法，程序優(yōu)化的主要考慮方向是：通過(guò)加強(qiáng)約束條件，縮小可能解的集合的規(guī)模。第二節(jié) 回溯算法所謂的回溯技術(shù)就是像人走迷宮一樣，先選擇一個(gè)前進(jìn)方向嘗試，一步步往前試探，在遇到死胡同不能再往前的時(shí)候就回退到上一個(gè)分叉點(diǎn)，選另一個(gè)方向嘗試，而在前進(jìn)和回撤的路上都設(shè)置一些標(biāo)記，以便能正確返回，直到達(dá)到目標(biāo)或者所有的可行方案都已經(jīng)嘗試完為止。在通常的情況下，我們使用遞歸方式來(lái)實(shí)現(xiàn)回溯技術(shù)，也

7、就是在每一個(gè)分叉點(diǎn)進(jìn)行遞歸嘗試。在回溯時(shí)通常采用棧來(lái)記錄回溯過(guò)程，使用?？墒垢F舉過(guò)程能回溯到所要位置，并繼續(xù)在指定層次上往下窮舉所有可能的解。第二節(jié) 回溯算法回溯算法可以用偽碼描述如下： Proc Search(當(dāng)前狀態(tài)); begin If 當(dāng)前狀態(tài)等于目標(biāo)狀態(tài) then exit; for 對(duì)所有可能的 Search(新?tīng)顟B(tài))； end;第二節(jié) 回溯算法回溯算法是一種十分常用的算法，象一些經(jīng)典問(wèn)題如八皇后問(wèn)題、騎士周游問(wèn)題、地圖著色問(wèn)題都可以采用回溯算法來(lái)解。 例題：求馬的不同走法總數(shù)問(wèn)題描述：在一個(gè)4*5的棋盤(pán)上，馬的起始位置坐標(biāo)（縱，橫）位置由鍵盤(pán)輸入，求馬能返回初始位置的所有不同走法

8、的總數(shù)(馬走過(guò)的位置不能重復(fù)，馬走“日”字)。第二節(jié) 回溯算法算法分析：由于棋盤(pán)的大小只有4*5，所以只需使用回溯算法，搜索馬能返回初始位置的所有不同走法，效率基本上能達(dá)到要求。遞歸的回溯算法可描述為：第二節(jié) 回溯算法 procedure search(now:position); now是當(dāng)前位置 begin for 馬從當(dāng)前位置now出發(fā)走一步到位置next的每一種走法 do begin if next在棋盤(pán)內(nèi) and next位置沒(méi)有走過(guò) then if next=出發(fā)點(diǎn) then 不同走法總數(shù)加1 else begin 標(biāo)記next已經(jīng)走過(guò)了; search(next); 取消位置ne

9、xt的標(biāo)記; end; end; end;第二節(jié) 回溯算法棋盤(pán)用坐標(biāo)表示，點(diǎn)P(x,y)表示棋盤(pán)上任一個(gè)點(diǎn)，x,y的范圍是：1=x=4，1=y=1) and (next.x=1) and (next.y = 5) and (passnext.x,next.y=0) then if (next.x=start.x) and (next.y=start.y) then inc(total) 第二節(jié) 回溯算法else begin passnext.x,next.y:=1; search(next); passnext.x,next.y:=0; end; end; end;第二節(jié) 回溯算法begin

10、total:=0; fillchar(pass,sizeof(pass),0); write(Start position:); readln(start.x,start.y); search(start); writeln(Total=,total); readln;end.作業(yè)作業(yè)3.1Sicily 1152 簡(jiǎn)單的馬周游問(wèn)題在一個(gè)5 * 6的棋盤(pán)中的某個(gè)位置有一只馬，如果它走29步正好經(jīng)過(guò)除起點(diǎn)外的其他位置各一次，這樣一種走法則稱馬的周游路線，試設(shè)計(jì)一個(gè)算法，從給定的起點(diǎn)出發(fā)，找出它的一條周游路線。為了便于表示一個(gè)棋盤(pán)，我們按照從上到下，從左到右對(duì)棋盤(pán)的方格編號(hào)，如下所示：1234567

11、89101112131415161718192021222324252627282930作業(yè)馬的走法是“日”字形路線，例如當(dāng)馬在位置15的時(shí)候，它可以到達(dá)2、4、7、11、19、23、26和28。但是規(guī)定馬是不能跳出棋盤(pán)外的，例如從位置1只能到達(dá)9和14。輸入 標(biāo)準(zhǔn)輸入stdin輸入有若干行。每行一個(gè)整數(shù)N(1=N=30)，表示馬的起點(diǎn)。最后一行用-1表示結(jié)束，不用處理。4-1作業(yè)輸出 標(biāo)準(zhǔn)輸出 stdout對(duì)輸入的每一個(gè)起點(diǎn)，求一條周游線路。對(duì)應(yīng)地輸出一行，有30個(gè)整數(shù)，從起點(diǎn)開(kāi)始按順序給出馬每次經(jīng)過(guò)的棋盤(pán)方格的編號(hào)。相鄰的數(shù)字用一個(gè)空格分開(kāi)。注意：如果起點(diǎn)和輸入給定的不同，重復(fù)多次經(jīng)過(guò)同一

12、方格或者有的方格沒(méi)有被經(jīng)過(guò)，都會(huì)被認(rèn)為是錯(cuò)誤的。第三節(jié) 貪心算法所謂貪心算法是指：在對(duì)問(wèn)題求解時(shí)，總是作出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，它所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。貪心算法時(shí)間復(fù)雜度較低，算法較易實(shí)現(xiàn)。第三節(jié) 貪心算法采用貪心算法的基本思路如下：（1）建立數(shù)學(xué)模型來(lái)描述問(wèn)題。（2）把求解的問(wèn)題分成若干個(gè)子問(wèn)題。（3）對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。（4）把子問(wèn)題的局部最優(yōu)解合成原求解問(wèn)題的一個(gè)解。 第三節(jié) 貪心算法例3.3.1：無(wú)向圖

13、的最小生成樹(shù)問(wèn)題。設(shè)G=V,E是一個(gè)無(wú)向圖，如果T=V,E是由G的全部頂點(diǎn)及其一部分邊組成的子圖，T是樹(shù)，則稱T是G的一個(gè)生成樹(shù)。記L（T）為T(mén)的長(zhǎng)度，即樹(shù)T的各邊之和。求G的所有生成樹(shù)中L（T）最小的生成樹(shù)。第三節(jié) 貪心算法圖3.3.1無(wú)向圖G及其生成樹(shù)：下面的兩棵樹(shù)都是圖G的生成樹(shù)，其中T2是所有圖G的最小的生成樹(shù)。第三節(jié) 貪心算法最小生成樹(shù)的算法思路是：由于n個(gè)頂點(diǎn)的圖，其最小生成樹(shù)共有n-1條邊，因此尋找最小生成樹(shù)的問(wèn)題就是選這n-1條邊的過(guò)程，我們可以把這個(gè)過(guò)程分解為n-1次的選擇，每次選擇都選一條邊。在每次選邊的時(shí)候，我們采用貪心的原則：選擇一條權(quán)值最小而未被選過(guò)，且和已選定的邊不

14、會(huì)構(gòu)成圈的邊。第三節(jié) 貪心算法最小生成樹(shù)的算法如下： T=空; for i:=1 to n-1 do begin 尋找在圖G中選取權(quán)值最小，不在T中，而且與T中的邊不構(gòu)成圈的邊ei; 把ei加入T中; end; T就是圖G的最小生成樹(shù)。最小生成樹(shù)程序?qū)崿F(xiàn)如下：第三節(jié) 貪心算法program ex3_3_1;var F:Text;N,M,i,j:Integer; /圖G的點(diǎn)數(shù)N和邊數(shù)MSelected:Array 1.100 of Integer; /對(duì)已選擇的邊ei,Selectedi為1,否則為0E:Array 1.100,1.2 of Integer; /邊的起點(diǎn)和終點(diǎn)Value:Arra

15、y 1.100 of Integer; /邊的權(quán)值T:Array 1.100 of Integer; /若Vi是生成中的結(jié)點(diǎn),Ti=1,否則為0Min,MinE,ValueT:Integer; /分別是當(dāng)前選邊的權(quán)值、選邊的編號(hào)和樹(shù)的長(zhǎng)度第三節(jié) 貪心算法begin /讀入圖G，圖G采用邊目錄表示法。 Assign(F,ex3_3_1.in); Reset(F); ReadLn(F,N,M); for i:=1 to M do ReadLn(F,Ei,1,Ei,2,Valuei); /初始化 fillchar(Selected,sizeof(Selected),0); fillchar(T,si

16、zeof(T),0); ValueT:=0;第三節(jié) 貪心算法 /n-1次選邊過(guò)程for i:=1 to N-1 do begin Min:=Maxint; MinE:=0; for j:=1 to m do /未被選中 if Selectedj=0 then /不構(gòu)成圈 if (TEj,1=0) xor (TEj,2=0) or (i=1) then 第三節(jié) 貪心算法/權(quán)值最小 if ValuejMin then begin Min:=Valuej; MinE:=j; end; /做選中的標(biāo)記 SelectedMinE:=1; TEMinE,1:=1; TEMinE,2:=1; ValueT:

17、=ValueT+Min; end;第三節(jié) 貪心算法 WriteLn(T:,:10,Length=,ValueT); for i:=1 to m do if Selectedi=1 then begin WriteLn(,Ei,1,Ei,2,); end; Close(F); ReadLn;end.第三節(jié) 貪心算法測(cè)試數(shù)據(jù)如下（即例子中的圖）：6 71 2 31 6 22 3 52 5 23 4 14 5 45 6 1第三節(jié) 貪心算法程序運(yùn)行結(jié)果如下：T: Length=10(1,6)(2,5)(3,4)(4,5)(5,6)第三節(jié) 貪心算法貪心算法適用范圍：整個(gè)問(wèn)題求解過(guò)程有明顯階段性。經(jīng)一次貪

18、心后原問(wèn)題變成相似的但規(guī)模更小的問(wèn)題；最優(yōu)性：即一個(gè)最優(yōu)解的子集也是相應(yīng)子問(wèn)題的最優(yōu)解。第四節(jié) 遞歸和分治算法遞歸是一種重要的思想，如果一個(gè)問(wèn)題可以轉(zhuǎn)化成一個(gè)結(jié)構(gòu)相同、規(guī)模更小的問(wèn)題，則用遞歸來(lái)解決。遞歸典型例子：Hanoi Tower問(wèn)題（見(jiàn)第一章）分治算法，是指將一個(gè)規(guī)模較大的問(wèn)題分解為若干個(gè)規(guī)模較小的部分（這些小問(wèn)題的難度應(yīng)該比原問(wèn)題小），求出各部分的解，然后再把各部分的解組合成整個(gè)問(wèn)題的解。第四節(jié) 遞歸和分治算法基本思路：（1）對(duì)求解建立數(shù)學(xué)模型和問(wèn)題規(guī)模描述。（2）建立把一個(gè)規(guī)模較大的問(wèn)題劃分為規(guī)模較小問(wèn)題的途徑。（3）定義可以立即解決（規(guī)模最?。┑膯?wèn)題的解決方法。（4）建立把若干個(gè)

19、小問(wèn)題的解合成大問(wèn)題的方法。第四節(jié) 遞歸和分治算法例3.4.1：求正整數(shù)集合（a1,a2,.,an）的最大值和最小值。建立數(shù)學(xué)模型和問(wèn)題規(guī)模的描述：題目本身有很強(qiáng)的數(shù)學(xué)背景，數(shù)學(xué)模型應(yīng)該是該問(wèn)題的一般數(shù)學(xué)解釋。我們可以定義問(wèn)題（f，t）表示求集合（af,af+1,.,at）中的最大值和最小值。我們需要解決的問(wèn)題是（1，n）第四節(jié) 遞歸和分治算法當(dāng)需要求解問(wèn)題（f，t）（共t-f+1個(gè)元素），我們可以把這個(gè)集合（af,af+1,.,at）分成兩半，即設(shè)m=f+(f-t)/2，集合分為（af,.,am）和（am+1,.,at）兩個(gè)集合;這兩個(gè)集合中只含有(f-t)/2或者(f-t)/2+1個(gè)元素。

20、將問(wèn)題（f，t）劃分成兩個(gè)規(guī)模較小的問(wèn)題（f，m）和（m+1，t）。第四節(jié) 遞歸和分治算法顯然，當(dāng)集合中只有一個(gè)元素時(shí)，問(wèn)題立刻有解，集合的最大值和最小值都是集合中唯一的元素。建立把若干個(gè)小問(wèn)題的解合成大問(wèn)題的方法1) 問(wèn)題（f，m）的最大值和問(wèn)題（m+1，t）的最大值中的大者就是問(wèn)題（f，t）的最大值；2)問(wèn)題（f，m）的最小值和問(wèn)題（m+1，t）的最小值中的小者就是問(wèn)題（f，t）的最小值。 第四節(jié) 遞歸和分治算法主要算法描述:program ex3_4_1;var a:array 1.10000 of Integer;procedure MaxMin(f,t:Integer;var rMa

21、x,rMin:Integer);var m:Integer; Max1,Max2,Min1,Min2:Integer;begin if f=t then begin rMax:=af; rMin:=at; end第四節(jié) 遞歸和分治算法else begin m:=(t-f) div 2 + f; MaxMin(f,m,Max1,Min1); MaxMin(m+1,t,Max2,Min2); rMax:=Max(Max1,Max2); rMin:=Min(Min1,Min2); end; end;第四節(jié) 遞歸和分治算法var Fin:Text;var i,n,rMax,rMin:Integer;b

22、egin Assign(Fin,ex2_5_1.txt); Reset(Fin); ReadLn(Fin,n); For i:=1 to n do Read(Fin,aI); Close(Fin); MaxMin(1,n,rMax,rMin); WriteLn(Format(Max=%d,Min=%d,rMax,rMin); Readln;end.第四節(jié) 遞歸和分治算法ex_3_4_1.txt測(cè)試用例：72 34 32 19 1 39 4程序運(yùn)行結(jié)果如下：Max=39,Min=1第五節(jié) 數(shù)值計(jì)算3.5.1 精度計(jì)算計(jì)算機(jī)精確計(jì)算的范圍是有限的，例如,整型的精確度為Int64時(shí)，值域是-2632

23、63-1如果需要精度更高的計(jì)算，就需要編程實(shí)現(xiàn)。在本節(jié)中，主要介紹正整數(shù)的高精度計(jì)算（加，減，乘和除），至于整數(shù)，有理數(shù)乃至實(shí)數(shù)的高精度運(yùn)算，這一部分所介紹的方法和技巧還是很有參考價(jià)值的。第五節(jié) 數(shù)值計(jì)算正整數(shù)高精度加法加法和減法都是最基本的運(yùn)算，乘除法運(yùn)算是建立在加減法之上的。加法算法如下：第五節(jié) 數(shù)值計(jì)算步驟說(shuō)明舉例（S1+S2） 表示參與運(yùn)算或被改變的數(shù)字S1=82S2=741對(duì)位。在被加數(shù)和加數(shù)前面適當(dāng)補(bǔ)0，使他們的包含相同的位數(shù)。82742前面再補(bǔ)一個(gè)0，確定和的最多位數(shù)。0820743從低位開(kāi)始，對(duì)應(yīng)位相加，結(jié)果寫(xiě)入被加數(shù)中。如果有進(jìn)位，直接給被加數(shù)前一位加1。0860741560

24、741560744刪除和前面多余的0156074第五節(jié) 數(shù)值計(jì)算2正整數(shù)高精度減法減法和加法的最大區(qū)別在于：減法是從高位開(kāi)始相減，而加法是從低位開(kāi)始相加。減法算法如下：第五節(jié) 數(shù)值計(jì)算步驟說(shuō)明舉例（S1-S2） 表示參與運(yùn)算或被改變的數(shù)字S1=82S2=741對(duì)位。在被減數(shù)和減數(shù)前面適當(dāng)補(bǔ)0，使他們的包含相同的位數(shù)。82742從高位開(kāi)始，對(duì)應(yīng)位相減，結(jié)果寫(xiě)入被減數(shù)中。如果需要借位，直接給被減數(shù)前一位減1。127408743刪除和前面多余的0874第五節(jié) 數(shù)值計(jì)算3正整數(shù)高精度乘法乘法的主要思想是把乘法轉(zhuǎn)化為加法進(jìn)行運(yùn)算。請(qǐng)先看下面的等式：12345*4=12345+12345+12345+12

25、34512345*20=123450*212345*24=12345*20+12345*4第五節(jié) 數(shù)值計(jì)算等式（1）說(shuō)明，多位數(shù)乘一位數(shù)，可以直接使用加法完成。等式（2）說(shuō)明，多位數(shù)乘形如d*10n的數(shù)，可以轉(zhuǎn)換成多位數(shù)乘一位數(shù)來(lái)處理。等式（3）說(shuō)明，多位數(shù)乘多位數(shù)，可以轉(zhuǎn)換為若干個(gè)“多位數(shù)乘形如d*10n的數(shù)與多位數(shù)乘一位數(shù)”之和。因此，多位數(shù)乘多位數(shù)最終可以全部用加法來(lái)實(shí)現(xiàn)。第五節(jié) 數(shù)值計(jì)算算法描述如下：function multiply(s1,s2:string):string;var i:Integer; C:Char;begin Result:=0;/多位數(shù)乘多位數(shù)，可以轉(zhuǎn)換為若干個(gè)

26、“多位數(shù)乘形如d*10n的數(shù)與多位數(shù)乘一位數(shù)”之和 for i:=Length(s2) downto 1 do 第五節(jié) 數(shù)值計(jì)算begin /多位數(shù)乘一位數(shù)，可以直接相加 for C:=1 to S2i do Result:=addition(Result,S1);/多位數(shù)乘形如d*10n的數(shù)轉(zhuǎn)換成多位數(shù)乘一位數(shù)來(lái)處理 S1:=S1+0; end;Result:=Clear(Result);multiply:=Result;end;第五節(jié) 數(shù)值計(jì)算執(zhí)行步數(shù)S1S2Result0121201121224212012144 例如12*12，算法執(zhí)行過(guò)程如下（多位數(shù)乘一位數(shù)看成是一步完成）；第五節(jié)

27、數(shù)值計(jì)算4正整數(shù)高精度除法高精度除法是基于精度減法的，主要的思想是“試商”，模仿筆算除法的方法。算法描述如下：第五節(jié) 數(shù)值計(jì)算function division(s1,s2:string):string;begin /Result中存放的是商 Result:=; /S中存放的是余數(shù)，S1是被除數(shù)，S2是除數(shù) S:=; /逐位試商 for i:=1 to Length(S1) do begin S:=S+S1i; 第五節(jié) 數(shù)值計(jì)算/先試商0 Result:=Result+0; /然后從1開(kāi)始不斷往上試 While Bigger(S,S2) do begin Inc(ResultLength(Re

28、sult); S:=Subtraction(S,S2); end; end; /刪除多余的0 Result:=Clear(Result);division:=Result;end; 第五節(jié) 數(shù)值計(jì)算執(zhí)行步數(shù)S1S2SResult說(shuō)明014412開(kāi)始狀態(tài)1144121S從S1中取得第1位21441210試商0，然后由于10) and (s1=0) do delete(s,1,1); if s= then s:=0; clear:=s;end; 第五節(jié) 數(shù)值計(jì)算/比較兩個(gè)數(shù)的大小，如果S1=S2，結(jié)果返回為真。function bigger(s1,s2:string):boolean;begin

29、bigger:=true; if length(s1)length(s2) then exit; if (length(s1)=length(s2) and (s1=s2) then exit; bigger:=false;end;第五節(jié) 數(shù)值計(jì)算/加法function addition(s1,s2:string):string;var i:integer;begin /對(duì)位 while Length(S1)Length(S2) do S1:=0+S1; while Length(S2)9 then begin S1i= S1i-10; S1i-1= S1i-1+1; end; end; Re

30、sult:=Clear(S1);addition:=Result;end;第五節(jié) 數(shù)值計(jì)算/減法/這里假設(shè)S1=S2，如果不滿足這個(gè)條件，/函數(shù)返回結(jié)果不正確function Subtraction(s1,s2:string):string;var i:integer;begin /對(duì)位 while Length(S1)Length(S2) do S1:=0+S1; while Length(S2)=S2i then S1i= S1i-S2i) else /有借位的情況 begin S1i= S1i+10 -S2i; S1i-1= S1i-1-1; end; Result:=Clear(S1)

31、;Subtraction:=Result;end;第五節(jié) 數(shù)值計(jì)算/乘法function multiply(s1,s2:string):string;var i:Integer;C:Char;begin Result:=0; for i:=Length(s2) downto 1 do begin for C:=1 to S2i do Result:=addition(Result,S1); S1:=S1+0; end; Result:=Clear(Result);multiply:=Result;end;第五節(jié) 數(shù)值計(jì)算/除法/這里假設(shè)除數(shù)不為0，如果除數(shù)為0，函數(shù)進(jìn)入死循環(huán)。function

32、 division(s1,s2:string):string;var i:integer; s:String;begin Result:=; S:=; for i:=1 to Length(S1) do第五節(jié) 數(shù)值計(jì)算begin S:=S+S1i; Result:=Result+0; While Bigger(S,S2) do begin ResultLength(Result)=ResultLength(Result)+1; S:=Subtraction(S,S2); end;end; Result:=Clear(Result);division:=Result;end;第五節(jié) 數(shù)值計(jì)算be

33、gin WriteLn(Addition(999,1); WriteLn(Subtraction(890,99); WriteLn(Multiply(99,99); WriteLn(Division(9899,99); ReadLn;end.第五節(jié) 數(shù)值計(jì)算程序運(yùn)行結(jié)果：1000791980199 第五節(jié) 數(shù)值計(jì)算特別說(shuō)明，上面的程序中的減法和除法沒(méi)有判斷是否夠減和除數(shù)為0，如果對(duì)于一般問(wèn)題，調(diào)用減法和除法之前應(yīng)該做檢查，如下例所示：/判斷夠減（結(jié)果不出現(xiàn)負(fù)數(shù)）if Bigger(s1,s2) then Result:=Subtraction(s1,s2);/判斷除數(shù)不為0if Clear(s

34、2)0 then Result:=Division(s1,s2);第五節(jié) 數(shù)值計(jì)算3.5.2 求解線性方程組解線性方程組是一類常用的基礎(chǔ)問(wèn)題。例如，在計(jì)算幾何中，需要求直線的交點(diǎn)，在列出直線方程后，就直接轉(zhuǎn)化為解線性方程組問(wèn)題了；又如線性規(guī)劃問(wèn)題，解線性方程組也是其中的一個(gè)基礎(chǔ)子問(wèn)題。解線性方程組的方法很多，例如Gauss消元法，LU法，求逆陣法，Gauss-Seidel(迭代)法等等，其中Gauss消元法需要的數(shù)學(xué)背景知識(shí)最少，而且比較容易實(shí)現(xiàn)，下面主要介紹使用Gauss消元法求解線性方程組問(wèn)題。第五節(jié) 數(shù)值計(jì)算下面簡(jiǎn)單介紹一下關(guān)于線性方程組的一些背景知識(shí)：a1x1+.+anxn=b線性方程

35、式(Linearequation)，其中a1,.,an為系數(shù)，x1,.,xn為未知數(shù)或變量(unknowns)，b為常數(shù)。第五節(jié) 數(shù)值計(jì)算n元m次聯(lián)立方程式：第五節(jié) 數(shù)值計(jì)算上式有m個(gè)方程式及n個(gè)未知元所形成的線性方程組。 第五節(jié) 數(shù)值計(jì)算其中 稱為系數(shù)矩陣 第五節(jié) 數(shù)值計(jì)算為未知向量， 第五節(jié) 數(shù)值計(jì)算為常數(shù)向量。 第五節(jié) 數(shù)值計(jì)算上面的矩陣也可以表示為增廣的形式：第五節(jié) 數(shù)值計(jì)算Gauss消元法主要是基于增廣矩陣的變換。算法如下：設(shè)所有行都為“未處理行”，然后從第1列到第n列依次掃描矩陣a。當(dāng)掃描到第k列時(shí)，在矩陣a所有未處理過(guò)的行中找出第k列中的最大值，和最大值所在行p。如果最大值為0，

36、說(shuō)明方程組無(wú)解或者有無(wú)窮多組解。否則，繼續(xù)下面操作。第五節(jié) 數(shù)值計(jì)算設(shè)置行p為已處理行，同時(shí)對(duì)其他的每一行，找到一個(gè)適當(dāng)?shù)臄?shù)，然后把行p乘以這個(gè)適當(dāng)?shù)臄?shù)加到該行中，使得通過(guò)上述變換后，該行第k列的元素為0。顯然，對(duì)第i行，這個(gè)適當(dāng)?shù)臄?shù)為-ai,k/ap,k。經(jīng)過(guò)上面的從第1列到第n列的掃描后，矩陣a中每行僅又一個(gè)非0值，記第i行的非0值為ai,j，則有xj:=bi/ai,j。算法舉例：求解方程：第五節(jié) 數(shù)值計(jì)算x1+2x2+x3=33x1-x2-3x3=-12x1+3x2+x3=4增廣矩陣表示如下： 1.00 2.00 1.00 | 3.00 3.00 -1.00 -3.00 | -1.00

37、2.00 3.00 1.00 | 4.00第五節(jié) 數(shù)值計(jì)算在第1列中，最大值為a2,1，把第2行乘以-1/3后加到第一行，同時(shí)把第2行乘以-2/3后加到第三行;0.00 2.33 2.00 | 3.333.00 -1.00 -3.00 | -1.000.00 3.67 3.00 | 4.67第五節(jié) 數(shù)值計(jì)算在第2列中，最大值為a3,2，把第3行乘以-2.33/3.67后加到第一行，同時(shí)把第3行乘以1/3.67后加到第二行 0.00 0.00 0.09 | 0.36 3.00 0.00 -2.18 | 0.27 0.00 3.67 3.00 | 4.67第五節(jié) 數(shù)值計(jì)算在第3列中，最大值為a1,

38、3（因?yàn)榇藭r(shí)未處理行只有第一行），類似上面的做法處理。0.00 0.00 0.09 | 0.363.00 0.00 0.00 | 9.000.00 3.67 0.00 | -7.33第五節(jié) 數(shù)值計(jì)算最后的結(jié)果為：x1= 3.000000 x2=-2.000000 x3=4.000000第五節(jié) 數(shù)值計(jì)算實(shí)現(xiàn)Gauss消元法算法描述如下：program ex3_5_2;/定義一維向量和二維向量const maxn=100;type tmatrix=array1.maxn,1.maxn of real; tvector=array1.maxn of real;第五節(jié) 數(shù)值計(jì)算/用Gauss消元法求解

39、線性方程組ax=b/Input: 數(shù)組a1.n,1.n，b1.n/Output: 解x1.nfunction GaussElimination(n:integer;a:tmatrix;b:tvector;var x:tvector):Boolean;var q:array 1.maxn of integer; i,j,k,p:Integer; max,l:real;第五節(jié) 數(shù)值計(jì)算begin fillchar(q,sizeof(q),0); for k:=1 to n do begin /選出第k列中，絕對(duì)值最大值對(duì)應(yīng)的（p） p:=0;max:=0; for i:=1 to n do if

40、(qi=0) and (max+1e-10abs(ai,k) then第五節(jié) 數(shù)值計(jì)算begin max:=abs(ai,k); p:=i; end; /如果絕對(duì)值最大為0，說(shuō)明方程組無(wú)解或者有無(wú)窮多組解。 if p=0 then begin Result:=False; exit; end第五節(jié) 數(shù)值計(jì)算 /做上處理過(guò)的標(biāo)記 else qp:=1; /把p行乘上一個(gè)適當(dāng)?shù)南禂?shù)后加到其他行上，使第k列中只有一個(gè)非0值 for i:=1 to n do if ip then begin l:=ai,k/ap,k; for j:=1 to n do ai,j:=ai,j-l*ap,j; bi:=b

41、i-l*bp; end; end;第五節(jié) 數(shù)值計(jì)算/求解x for i:=1 to n do for j:=1 to n do if abs(ai,j)1e-10 then xj:=bi/ai,j; Result:=True;end;第六節(jié) 計(jì)算幾何計(jì)算幾何是計(jì)算機(jī)科學(xué)中新的分支，它的形成和發(fā)展與計(jì)算機(jī)圖形學(xué)、超大規(guī)模集成電路設(shè)計(jì)、計(jì)算機(jī)輔助設(shè)計(jì)和機(jī)器人等學(xué)科的發(fā)展都有密切的聯(lián)系。3.6.1 線段問(wèn)題兩條線段的交點(diǎn)問(wèn)題關(guān)于平面上的線段的若干性質(zhì)。 第六節(jié) 計(jì)算幾何已知A（x1，y1）和B（x2，y2）是平面上任意兩點(diǎn)，則線段AB上的任意一點(diǎn)P（x，y），存在實(shí)數(shù)a(0a1)，滿足：x=ax1+

42、(1-a)x2，y=ay1+(1-a)y2第六節(jié) 計(jì)算幾何第六節(jié) 計(jì)算幾何下面就正式轉(zhuǎn)入如何判斷兩條線段AB和CD是否相交和求線段的交點(diǎn)。假設(shè)AB和CD交于P點(diǎn)，那么下面的方程組：x=d1xA+(1-d1)xBy=d1yA+(1-d1)yBx=d2xC+(1-d2)xDy=d2yC+(1-d2)yD如果線段相交當(dāng)且僅當(dāng)方程組有解，而且0d1,d21。接下來(lái)的工作就是解上面的四元齊次方程組了（解方程組的算法可以參考上節(jié)“求解線性方程組”部分，當(dāng)然也可以手工先求解方程組）。 第六節(jié) 計(jì)算幾何程序如下：program ex3_6_1;type TPoint=record x,y:real end;/

43、by rei/判斷線段s1,e1和s2,e2是否相交/Input: 線段s1,e1和s2,e2/Output: Intersect = false 線段s1,e1和s2,e2不相交/ true 線段s1,e1和s2,e2相交，交點(diǎn)用全局參數(shù)d1,d2給出/ 交點(diǎn)坐標(biāo)(x,y)的計(jì)算: x=s1.x+d1*(s2.x-s1.x)/ y=s1.y+d1*(s2.y-s1.y) 第六節(jié) 計(jì)算幾何function Intersect(s1,e1,s2,e2:TPoint):boolean;var a1,a2,b1,b2,c1,c2:real;begin Intersect:=false; a1:=e1

44、.x-s1.x; a2:=e1.y-s1.y; b1:=s2.x-e2.x; b2:=s2.y-e2.y; c1:=s2.x-s1.x; c2:=s2.y-s1.y;第六節(jié) 計(jì)算幾何if Same(a1*b2,a2*b1) then exit; d1:=(c1*b2-c2*b1)/(a1*b2-a2*b1); d2:=(c1*a2-c2*a1)/(b1*a2-b2*a1); Intersect:=true;end;第六節(jié) 計(jì)算幾何2.8.2 凸包問(wèn)題設(shè)平面上有一點(diǎn)集S，存在一最小的凸多邊形P，使得S中的每一點(diǎn)或在P的邊界上或是P的內(nèi)點(diǎn)。這個(gè)多邊形P便稱為S的凸包。第六節(jié) 計(jì)算幾何下面介紹Gra

45、bam掃描法求解凸包問(wèn)題。Graham掃描法是從凸包的一個(gè)角點(diǎn)開(kāi)始，通常選取Pi(xi,yi)(i=1,2,.,n)中yi達(dá)到最小的點(diǎn)。不失一般性，令這一點(diǎn)為P1(x1,y1)，而且使得閉n邊形P1P2.PnP1滿足P1Pi的線段和x軸正向的夾角是一單調(diào)遞增序列，上面的要求可以通過(guò)對(duì)傾斜角的排序來(lái)實(shí)現(xiàn)。第六節(jié) 計(jì)算幾何然后依次多邊形中的頂點(diǎn)，刪去不必要的頂點(diǎn)，使得最后留下來(lái)的是所求的凸包。什么是不必要的點(diǎn)呢？如下圖所示:P4點(diǎn)是一個(gè)不必要的點(diǎn)，因?yàn)镻5P4到P4P1是順時(shí)針的，而其他都是逆時(shí)針的。第六節(jié) 計(jì)算幾何Graham掃描法算法描述如下：對(duì)點(diǎn)集進(jìn)行重新排序，滿足，P1的y座標(biāo)最小，而且P

46、iP1的對(duì)x軸正向的夾角是單調(diào)遞增的。把前3個(gè)點(diǎn)壓入堆棧中。第六節(jié) 計(jì)算幾何實(shí)現(xiàn)Graham掃描法的程序如下：program ex3_6_2;/ by splutter/ 掃描法求凸包/ Input: List=點(diǎn)集數(shù)組 Len=點(diǎn)的總數(shù)/ Output: List=以逆時(shí)針?lè)较蚪o出的凸多邊形頂點(diǎn)數(shù)組 Len=頂點(diǎn)數(shù)目$apptype consoleuses sysutils;第六節(jié) 計(jì)算幾何const maxn=1000;type tpoint=record x,y:integer end;第六節(jié) 計(jì)算幾何tarrpoint=array1.maxn of tpoint; var top:in

47、teger; stack:array1.maxn of integer;第六節(jié) 計(jì)算幾何/求線段內(nèi)積，從而可以判斷順時(shí)針或者逆時(shí)針function multi(var p1,p2,p0:tpoint):integer;begin multi:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);end;第六節(jié) 計(jì)算幾何/交換兩個(gè)點(diǎn)procedure swap(var a,b:TPoint);var t:tpoint;begin t:=a; a:=b; b:=tend;第六節(jié) 計(jì)算幾何procedure scan(var list:tarrpoint; var len:integer); /比較兩個(gè)點(diǎn)的位置關(guān)系 function comp(var p1,p2:tpoint):boolean; var t:integer; begin t:=multi(p1,p2,list1); comp:=(t0) or (t=0) and ( sqr(p1.x-list1.x) +sqr(p1.y-list1.y) sqr(p2.x-list1.x) +sqr(p2.y-list1.y); end;第六節(jié) 計(jì)算幾何 /排序（快速排序） procedure sort(p,r:integer); var i,j:integer; x:tp