算法設計及其應用第三章

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

2、in Write(s); exit the program; end;第一節(jié) 枚舉算法例3.1：尋找水仙花數一個三位數其各位數字的立方和等于它本身，這樣的數稱為水仙花數。要求找出所有的水仙花數分析：所求一定是三位數，所以范圍一定在100-999之間，只要將這些數逐一列舉，符合條件者為解第一節(jié) 枚舉算法For a:=100 to 999 do b:=a mod 10; /取出個位 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：經典的百雞問題：有一個人有一百塊錢

3、，打算買一百只雞。到市場一看，公雞三塊錢一只，母雞兩塊錢一個，小雞一塊錢三只。現(xiàn)在，請你編一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？第一節(jié) 枚舉算法分析 :按照枚舉算法的思路，首先應該構造可能解的集合：S=(x,y,z)|0 x,y,z100，其中三元組(x,y,z)表示買公雞x只，母雞y只和小雞z只。因為一共需要買100只雞，因此，買公雞、母雞和小雞的數量都不會超過100。然后確定驗證解的條件：x+y+z=100 and 3x+2y+z/3=100。第一節(jié) 枚舉算法下面是解這百雞問題的程序：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) /驗證可能解 then WriteLn(Format(x,y,z)=(%3d,%3d,%3d),x,y,z);end.第一節(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。我們通過條件x+y+z=100來約束求解空間，縮小可能解的集合的規(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的運行結果和程序ex3_1_1相同，但是循環(huán)次

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

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

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

9、xt的標記; end; end; end;第二節(jié) 回溯算法棋盤用坐標表示，點P(x,y)表示棋盤上任一個點，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 簡單的馬周游問題在一個5 * 6的棋盤中的某個位置有一只馬，如果它走29步正好經過除起點外的其他位置各一次，這樣一種走法則稱馬的周游路線，試設計一個算法，從給定的起點出發(fā)，找出它的一條周游路線。為了便于表示一個棋盤，我們按照從上到下，從左到右對棋盤的方格編號，如下所示：1234567

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

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

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

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

15、y 1.100 of Integer; /邊的權值T:Array 1.100 of Integer; /若Vi是生成中的結點,Ti=1,否則為0Min,MinE,ValueT:Integer; /分別是當前選邊的權值、選邊的編號和樹的長度第三節(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次選邊過程for i:=1 to N-1 do begin Min:=Maxint; MinE:=0; for j:=1 to m do /未被選中 if Selectedj=0 then /不構成圈 if (TEj,1=0) xor (TEj,2=0) or (i=1) then 第三節(jié) 貪心算法/權值最小 if ValuejMin then begin Min:=Valuej; MinE:=j; end; /做選中的標記 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é) 貪心算法測試數據如下（即例子中的圖）：6 71 2 31 6 22 3 52 5 23 4 14 5 45 6 1第三節(jié) 貪心算法程序運行結果如下：T: Length=10(1,6)(2,5)(3,4)(4,5)(5,6)第三節(jié) 貪心算法貪心算法適用范圍：整個問題求解過程有明顯階段性。經一次貪

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

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

20、將問題（f，t）劃分成兩個規(guī)模較小的問題（f，m）和（m+1，t）。第四節(jié) 遞歸和分治算法顯然，當集合中只有一個元素時，問題立刻有解，集合的最大值和最小值都是集合中唯一的元素。建立把若干個小問題的解合成大問題的方法1) 問題（f，m）的最大值和問題（m+1，t）的最大值中的大者就是問題（f，t）的最大值；2)問題（f，m）的最小值和問題（m+1，t）的最小值中的小者就是問題（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測試用例：72 34 32 19 1 39 4程序運行結果如下：Max=39,Min=1第五節(jié) 數值計算3.5.1 精度計算計算機精確計算的范圍是有限的，例如,整型的精確度為Int64時，值域是-2632

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

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

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

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

27、數值計算4正整數高精度除法高精度除法是基于精度減法的，主要的思想是“試商”，模仿筆算除法的方法。算法描述如下：第五節(jié) 數值計算function division(s1,s2:string):string;begin /Result中存放的是商 Result:=; /S中存放的是余數，S1是被除數，S2是除數 S:=; /逐位試商 for i:=1 to Length(S1) do begin S:=S+S1i; 第五節(jié) 數值計算/先試商0 Result:=Result+0; /然后從1開始不斷往上試 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é) 數值計算執(zhí)行步數S1S2SResult說明014412開始狀態(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é) 數值計算/比較兩個數的大小，如果S1=S2，結果返回為真。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é) 數值計算/加法function addition(s1,s2:string):string;var i:integer;begin /對位 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é) 數值計算/減法/這里假設S1=S2，如果不滿足這個條件，/函數返回結果不正確function Subtraction(s1,s2:string):string;var i:integer;begin /對位 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é) 數值計算/乘法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é) 數值計算/除法/這里假設除數不為0，如果除數為0，函數進入死循環(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é) 數值計算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é) 數值計算be

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

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

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

36、說明方程組無解或者有無窮多組解。否則，繼續(xù)下面操作。第五節(jié) 數值計算設置行p為已處理行，同時對其他的每一行，找到一個適當的數，然后把行p乘以這個適當的數加到該行中，使得通過上述變換后，該行第k列的元素為0。顯然，對第i行，這個適當的數為-ai,k/ap,k。經過上面的從第1列到第n列的掃描后，矩陣a中每行僅又一個非0值，記第i行的非0值為ai,j，則有xj:=bi/ai,j。算法舉例：求解方程：第五節(jié) 數值計算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é) 數值計算在第1列中，最大值為a2,1，把第2行乘以-1/3后加到第一行，同時把第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é) 數值計算在第2列中，最大值為a3,2，把第3行乘以-2.33/3.67后加到第一行，同時把第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é) 數值計算在第3列中，最大值為a1,

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

39、線性方程組ax=b/Input: 數組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é) 數值計算begin fillchar(q,sizeof(q),0); for k:=1 to n do begin /選出第k列中，絕對值最大值對應的（p） p:=0;max:=0; for i:=1 to n do if

40、(qi=0) and (max+1e-10abs(ai,k) then第五節(jié) 數值計算begin max:=abs(ai,k); p:=i; end; /如果絕對值最大為0，說明方程組無解或者有無窮多組解。 if p=0 then begin Result:=False; exit; end第五節(jié) 數值計算 /做上處理過的標記 else qp:=1; /把p行乘上一個適當的系數后加到其他行上，使第k列中只有一個非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é) 數值計算/求解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é) 計算幾何計算幾何是計算機科學中新的分支，它的形成和發(fā)展與計算機圖形學、超大規(guī)模集成電路設計、計算機輔助設計和機器人等學科的發(fā)展都有密切的聯(lián)系。3.6.1 線段問題兩條線段的交點問題關于平面上的線段的若干性質。 第六節(jié) 計算幾何已知A（x1，y1）和B（x2，y2）是平面上任意兩點，則線段AB上的任意一點P（x，y），存在實數a(0a1)，滿足：x=ax1+

42、(1-a)x2，y=ay1+(1-a)y2第六節(jié) 計算幾何第六節(jié) 計算幾何下面就正式轉入如何判斷兩條線段AB和CD是否相交和求線段的交點。假設AB和CD交于P點，那么下面的方程組：x=d1xA+(1-d1)xBy=d1yA+(1-d1)yBx=d2xC+(1-d2)xDy=d2yC+(1-d2)yD如果線段相交當且僅當方程組有解，而且0d1,d21。接下來的工作就是解上面的四元齊次方程組了（解方程組的算法可以參考上節(jié)“求解線性方程組”部分，當然也可以手工先求解方程組）。 第六節(jié) 計算幾何程序如下：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相交，交點用全局參數d1,d2給出/ 交點坐標(x,y)的計算: x=s1.x+d1*(s2.x-s1.x)/ y=s1.y+d1*(s2.y-s1.y) 第六節(jié) 計算幾何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é) 計算幾何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é) 計算幾何2.8.2 凸包問題設平面上有一點集S，存在一最小的凸多邊形P，使得S中的每一點或在P的邊界上或是P的內點。這個多邊形P便稱為S的凸包。第六節(jié) 計算幾何下面介紹Gra

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

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

47、teger; stack:array1.maxn of integer;第六節(jié) 計算幾何/求線段內積，從而可以判斷順時針或者逆時針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é) 計算幾何/交換兩個點procedure swap(var a,b:TPoint);var t:tpoint;begin t:=a; a:=b; b:=tend;第六節(jié) 計算幾何procedure scan(var list:tarrpoint; var len:integer); /比較兩個點的位置關系 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é) 計算幾何 /排序（快速排序） procedure sort(p,r:integer); var i,j:integer; x:tp