第二章 作業(yè)管理

1、算法設(shè)計與分析第三章第三章 常用算法分析常用算法分析目錄n第一節(jié)第一節(jié) 枚舉算法枚舉算法n第二節(jié)第二節(jié) 回溯算法回溯算法n第三節(jié)第三節(jié) 貪心算法貪心算法n第四節(jié)第四節(jié) 分治算法分治算法n第五節(jié)第五節(jié) 數(shù)值計算數(shù)值計算n第六節(jié)第六節(jié) 計算幾何計算幾何n第七節(jié)第七節(jié) 模擬題解法模擬題解法 第一節(jié) 枚舉算法n所謂枚舉算法，是指從可能的集合中一所謂枚舉算法，是指從可能的集合中一一枚舉各元素，用題目給定的檢驗條件一枚舉各元素，用題目給定的檢驗條件判定哪些是有用的，哪些是無用的。能判定哪些是有用的，哪些是無用的。能使命題成立者，即為問題的解。使命題成立者，即為問題的解。第一節(jié) 枚舉算法n采用枚舉算法解題的

2、基本思路如下：采用枚舉算法解題的基本思路如下：（1）建立問題的數(shù)學(xué)模型，確定問題的可能）建立問題的數(shù)學(xué)模型，確定問題的可能解的集合（可能解的空間）。解的集合（可能解的空間）。（2）逐一枚舉可能解集合中的元素，驗證是）逐一枚舉可能解集合中的元素，驗證是否是問題的解。否是問題的解。第一節(jié) 枚舉算法使用偽代碼可以描述為：for each s in S /S是問題所有可能解的集合是問題所有可能解的集合 if s is a solution then begin Write(s); exit the program; end;第一節(jié) 枚舉算法例例3.1題：經(jīng)典的百雞問題：有一個人有一百塊題：經(jīng)典的百雞問

3、題：有一個人有一百塊錢，打算買一百只雞。到市場一看，公雞三塊錢，打算買一百只雞。到市場一看，公雞三塊錢一只，母雞兩塊錢一個，小雞一塊錢三只。錢一只，母雞兩塊錢一個，小雞一塊錢三只?，F(xiàn)在，請你編一程序，幫他計劃一下，怎么樣現(xiàn)在，請你編一程序，幫他計劃一下，怎么樣買法，才能剛好用一百塊錢買一百只雞？買法，才能剛好用一百塊錢買一百只雞？第一節(jié) 枚舉算法n分析分析 :按照枚舉算法的思路，首先應(yīng)該構(gòu)造可能解的按照枚舉算法的思路，首先應(yīng)該構(gòu)造可能解的集合：集合：S=(x,y,z)|0 x,y,z100，其中三元組，其中三元組(x,y,z)表表示買公雞示買公雞x只，母雞只，母雞y只和小雞只和小雞z只。因為一

4、共需要買只。因為一共需要買100只雞，因此，買公雞、母雞和小雞的數(shù)量都不會只雞，因此，買公雞、母雞和小雞的數(shù)量都不會超過超過100。然后確定驗證解的條件：。然后確定驗證解的條件：x+y+z=100 and 3x+2y+z/3=100。第一節(jié) 枚舉算法n下面是解這百雞問題的程序：Program ex2_3_1;$APPTYPE CONSOLEUses SysUtils;Var x,y,z:integer;begin /枚舉可能解空間的元素枚舉可能解空間的元素第一節(jié) 枚舉算法 for x:=0 to 100 do for y:=0 to 100 do for z:=0 to 100 do if (

5、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é) 枚舉算法n程序輸出結(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)=( 20, 8, 72)(x,y,z)=( 25, 0, 75)n有有6種可選的方案。種可選的方案。第一節(jié) 枚舉算法程序需要循環(huán)程序需要循

6、環(huán)1003，即，即|S|=1003。我們通過條件。我們通過條件x+y+z=100來約束求解空間，縮小可能解的集合的規(guī)模：來約束求解空間，縮小可能解的集合的規(guī)模：Program ex2_3_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é) 枚舉算法n 程序程序ex2_3_2的運行結(jié)果和程序的運行結(jié)果和程序ex2_3_1相同，但是循環(huán)次數(shù)

7、為（相同，但是循環(huán)次數(shù)為（100*101/2），是），是程序程序ex2_3_1循環(huán)次數(shù)的循環(huán)次數(shù)的1/200左右。左右。n從上面的對比可以看出，對于枚舉算法，從上面的對比可以看出，對于枚舉算法，程序優(yōu)化的主要考慮方向是：通過加強約程序優(yōu)化的主要考慮方向是：通過加強約束條件，縮小可能解的集合的規(guī)模。束條件，縮小可能解的集合的規(guī)模。第二節(jié) 回溯算法n所謂的回溯技術(shù)就是像人走迷宮一樣，先選擇一所謂的回溯技術(shù)就是像人走迷宮一樣，先選擇一個前進方向嘗試，一步步往前試探，在遇到死胡個前進方向嘗試，一步步往前試探，在遇到死胡同不能再往前的時候就回退到上一個分叉點，選同不能再往前的時候就回退到上一個分叉點，選

8、另一個方向嘗試，而在前進和回撤的路上都設(shè)置另一個方向嘗試，而在前進和回撤的路上都設(shè)置一些標記，以便能正確返回，直到達到目標或者一些標記，以便能正確返回，直到達到目標或者所有的可行方案都已經(jīng)嘗試完為止。所有的可行方案都已經(jīng)嘗試完為止。n在通常的情況下，我們使用遞歸方式來實現(xiàn)回溯在通常的情況下，我們使用遞歸方式來實現(xiàn)回溯技術(shù)，也就是在每一個分叉點進行遞歸嘗試。在技術(shù)，也就是在每一個分叉點進行遞歸嘗試。在回溯時通常采用棧來記錄回溯過程，使用?？墒够厮輹r通常采用棧來記錄回溯過程，使用?？墒垢F舉過程能回溯到所要位置，并繼續(xù)在指定層次窮舉過程能回溯到所要位置，并繼續(xù)在指定層次上往下枚舉所有可能的解。上往下

9、枚舉所有可能的解。第二節(jié) 回溯算法n回溯算法可以用偽碼描述如下：回溯算法可以用偽碼描述如下： Proc Search(當前狀態(tài)當前狀態(tài)); begin If 當前狀態(tài)等于目標狀態(tài)當前狀態(tài)等于目標狀態(tài) then exit; for 對所有可能的對所有可能的 Search(新狀態(tài)新狀態(tài))； end;第二節(jié) 回溯算法n回溯算法是一種十分常用的算法，象一些經(jīng)典回溯算法是一種十分常用的算法，象一些經(jīng)典問題如八皇后問題、騎士周游問題、地圖著色問題如八皇后問題、騎士周游問題、地圖著色問題都可以采用回溯算法來解。問題都可以采用回溯算法來解。 n例題：求馬的不同走法總數(shù)問題描述：在一個例題：求馬的不同走法總數(shù)問

10、題描述：在一個4*5的棋盤上，馬的起始位置坐標（縱，橫）的棋盤上，馬的起始位置坐標（縱，橫）位置由鍵盤輸入，求馬能返回初始位置的所有位置由鍵盤輸入，求馬能返回初始位置的所有不同走法的總數(shù)不同走法的總數(shù)(馬走過的位置不能重復(fù)，馬馬走過的位置不能重復(fù)，馬走走“日日”字字)。第二節(jié) 回溯算法n算法分析：算法分析：由于棋盤的大小只有由于棋盤的大小只有4*5，所以只需使用，所以只需使用回溯算法，搜索馬能返回初始位置的所有回溯算法，搜索馬能返回初始位置的所有不同走法，效率基本上能達到要求。不同走法，效率基本上能達到要求。n遞歸的回溯算法可描述為：遞歸的回溯算法可描述為：第二節(jié) 回溯算法 procedure

11、 search(now:position); now是當前位置是當前位置 begin for 馬從當前位置馬從當前位置now出發(fā)走一步到位置出發(fā)走一步到位置next的每一的每一種走法種走法 dobegin if next在棋盤內(nèi)在棋盤內(nèi) and next位置沒有走過位置沒有走過 then if next=出發(fā)點出發(fā)點 then 不同走法總數(shù)加不同走法總數(shù)加1 else begin 標記標記next已經(jīng)走過了已經(jīng)走過了; search(next); 取消位置取消位置next的標記的標記; end; end; end;第二節(jié) 回溯算法n棋盤用坐標表示，點棋盤用坐標表示，點P(x,y)表示棋盤上任一

12、個表示棋盤上任一個點，點，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 total:=0; fillchar(pass,sizeof(pass)

13、,0); write(Start position:); readln(start.x,start.y); search(start); writeln(Total=,total); readln;end.作業(yè)n作業(yè)作業(yè)3.1nSicily 1152 簡單的馬周游問題簡單的馬周游問題n在一個在一個5 * 6的棋盤中的某個位置有一只馬，如果它走的棋盤中的某個位置有一只馬，如果它走29步正好經(jīng)步正好經(jīng)過除起點外的其他位置各一次，這樣一種走法則稱馬的周游路線，過除起點外的其他位置各一次，這樣一種走法則稱馬的周游路線，試設(shè)計一個算法，從給定的起點出發(fā)，找出它的一條周游路線。試設(shè)計一個算法，從給定的起點

14、出發(fā)，找出它的一條周游路線。n為了便于表示一個棋盤，我們按照從上到下，從左到右對棋盤的為了便于表示一個棋盤，我們按照從上到下，從左到右對棋盤的方格編號，如下所示：方格編號，如下所示：n123456n789101112n131415161718n192021222324n252627282930作業(yè)n馬的走法是馬的走法是“日日”字形路線，例如當馬在位置字形路線，例如當馬在位置15的時的時候，它可以到達候，它可以到達2、4、7、11、19、23、26和和28。但。但是規(guī)定馬是不能跳出棋盤外的，例如從位置是規(guī)定馬是不能跳出棋盤外的，例如從位置1只能到只能到達達9和和14。n輸入輸入 標準輸入標準輸入

15、stdinn輸入有若干行。每行一個整數(shù)輸入有若干行。每行一個整數(shù)N(1=N=30)，表示馬，表示馬的起點。最后一行用的起點。最后一行用-1表示結(jié)束，不用處理。表示結(jié)束，不用處理。n4n-1作業(yè)n輸出輸出 標準輸出標準輸出 stdoutn對輸入的每一個起點，求一條周游線路。對應(yīng)對輸入的每一個起點，求一條周游線路。對應(yīng)地輸出一行，有地輸出一行，有30個整數(shù)，從起點開始按順序個整數(shù)，從起點開始按順序給出馬每次經(jīng)過的棋盤方格的編號。相鄰的數(shù)給出馬每次經(jīng)過的棋盤方格的編號。相鄰的數(shù)字用一個空格分開。字用一個空格分開。n注意：如果起點和輸入給定的不同，重復(fù)多次注意：如果起點和輸入給定的不同，重復(fù)多次經(jīng)過同

16、一方格或者有的方格沒有被經(jīng)過，都會經(jīng)過同一方格或者有的方格沒有被經(jīng)過，都會被認為是錯誤的。被認為是錯誤的。第三節(jié) 貪心算法n所謂貪心算法是指：在對問題求解時，總是作所謂貪心算法是指：在對問題求解時，總是作出在當前看來是最好的選擇。也就是說，不從出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅是在某種整體最優(yōu)上加以考慮，它所做出的僅是在某種意義上的局部最優(yōu)解。意義上的局部最優(yōu)解。n貪心算法不是對所有問題都能得到整體最優(yōu)解，貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題它能產(chǎn)生整體最但對范圍相當廣泛的許多問題它能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

17、優(yōu)解或者是整體最優(yōu)解的近似解。n貪心算法時間復(fù)雜度較低，算法較易實現(xiàn)。貪心算法時間復(fù)雜度較低，算法較易實現(xiàn)。第三節(jié) 貪心算法n采用貪心算法的基本思路如下：采用貪心算法的基本思路如下：（1）建立數(shù)學(xué)模型來描述問題。）建立數(shù)學(xué)模型來描述問題。（2）把求解的問題分成若干個子問題。）把求解的問題分成若干個子問題。（3）對每一子問題求解，得到子問題的局部最）對每一子問題求解，得到子問題的局部最優(yōu)解。優(yōu)解。（4）把子問題的局部最優(yōu)解合成原求解問題的）把子問題的局部最優(yōu)解合成原求解問題的一個解。一個解。 第三節(jié) 貪心算法n例例3.3.1：無向圖的最小生成樹問題。無向圖的最小生成樹問題。設(shè)設(shè)G=V,E是一個無

18、向圖，如果是一個無向圖，如果T=V,E是由是由G的全部頂點及其一部分邊組成的子圖，的全部頂點及其一部分邊組成的子圖，T是樹，是樹，則稱則稱T是是G的一個生成樹。記的一個生成樹。記L（T）為）為T的長的長度，即樹度，即樹T的各邊之和。求的各邊之和。求G的所有生成樹中的所有生成樹中L（T）最小的生成樹。）最小的生成樹。第三節(jié) 貪心算法35242V1V2V3V4V5V63524121V1V2V3V4V5V624121V1V2V3V4V5V6圖GL(T1)=16L(T2)=10圖圖3.5 無向圖無向圖G及其生成樹：及其生成樹：下面的兩棵樹都是圖下面的兩棵樹都是圖G的生成樹，其中的生成樹，其中T2是所有

19、圖是所有圖G的最小的生成樹。的最小的生成樹。第三節(jié) 貪心算法n最小生成樹的算法思路是：由于最小生成樹的算法思路是：由于n個頂點的圖，個頂點的圖，其最小生成樹共有其最小生成樹共有n-1條邊，因此尋找最小生條邊，因此尋找最小生成樹的問題就是選這成樹的問題就是選這n-1條邊的過程，我們可條邊的過程，我們可以把這個過程分解為以把這個過程分解為n-1次的選擇，每次選擇次的選擇，每次選擇都選一條邊。在每次選邊的時候，我們采用貪都選一條邊。在每次選邊的時候，我們采用貪心的原則：選擇一條權(quán)值最小而未被選過，且心的原則：選擇一條權(quán)值最小而未被選過，且和已選定的邊不會構(gòu)成圈的邊。和已選定的邊不會構(gòu)成圈的邊。第三節(jié)

20、 貪心算法最小生成樹的算法如下：最小生成樹的算法如下： T=空空; for i:=1 to n-1 do begin 尋找在圖尋找在圖G中選取權(quán)值最小，不在中選取權(quán)值最小，不在T中，中，而且與而且與T中的邊不構(gòu)成圈的邊中的邊不構(gòu)成圈的邊ei; 把把ei加入加入T中中; end; T就是圖就是圖G的最小生成樹。的最小生成樹。最小生成樹程序?qū)崿F(xiàn)如下：最小生成樹程序?qū)崿F(xiàn)如下：第三節(jié) 貪心算法program ex2_5_1;$APPTYPE CONSOLEuses SysUtils;var F:Text;N,M,i,j:Integer; /圖圖G的點數(shù)的點數(shù)N和邊數(shù)和邊數(shù)MSelected:Array

21、 1.100 of Integer; /對已選擇的邊對已選擇的邊ei,Selectedi為為1,否則為否則為0E:Array 1.100,1.2 of Integer;/*邊的起點邊的起點和終點和終點*/Value:Array 1.100 of Integer; /邊的權(quán)值邊的權(quán)值T:Array 1.100 of Integer; /若若Vi是生成中的結(jié)點是生成中的結(jié)點,Ti=1,否則為否則為0Min,MinE,ValueT:Integer; /分別是當前選邊的權(quán)值、選邊的編號和樹的長度分別是當前選邊的權(quán)值、選邊的編號和樹的長度第三節(jié) 貪心算法begin /讀入圖讀入圖G，圖，圖G采用邊目錄表

22、示法。采用邊目錄表示法。 Assign(F,ex2_4_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,sizeof(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 t

23、hen /不構(gòu)成圈不構(gòu)成圈 if (TEj,1=0) xor (TEj,2=0) or (i=1) then 第三節(jié) 貪心算法 /權(quán)值最小權(quán)值最小 if ValuejMin then begin Min:=Valuej; MinE:=j; end; /做選中的標記做選中的標記 SelectedMinE:=1; TEMinE,1:=1; TEMinE,2:=1; ValueT:=ValueT+Min; end;第三節(jié) 貪心算法 WriteLn(T:,:10,Length=,ValueT); for i:=1 to m do if Selectedi=1 then begin WriteLn(,E

24、i,1,Ei,2,); end; Close(F); ReadLn;end.第三節(jié) 貪心算法n測試數(shù)據(jù)如下（即例子中的圖）：測試數(shù)據(jù)如下（即例子中的圖）：6 71 2 31 6 22 3 52 5 23 4 14 5 45 6 1第三節(jié) 貪心算法n程序運行結(jié)果如下：程序運行結(jié)果如下：T: Length=10(1,6)(2,5)(3,4)(4,5)(5,6)第四節(jié) 遞歸和分治算法n遞歸是一種重要的思想，如果一個問題可以轉(zhuǎn)遞歸是一種重要的思想，如果一個問題可以轉(zhuǎn)化成一個結(jié)構(gòu)相同、規(guī)模更小的問題，則用遞化成一個結(jié)構(gòu)相同、規(guī)模更小的問題，則用遞歸來解決。歸來解決。n遞歸典型例子：遞歸典型例子：Hano

25、i Tower問題問題（見第一章（見第一章）n分治算法，是指將一個規(guī)模較大的問題分解為分治算法，是指將一個規(guī)模較大的問題分解為若干個規(guī)模較小的部分（這些小問題的難度應(yīng)若干個規(guī)模較小的部分（這些小問題的難度應(yīng)該比原問題?。蟪龈鞑糠值慕?，然后再把該比原問題小），求出各部分的解，然后再把各部分的解組合成整個問題的解。各部分的解組合成整個問題的解。第四節(jié) 分治算法n分治算法基本思路：分治算法基本思路：（1）對求解建立數(shù)學(xué)模型和問題規(guī)模描述。）對求解建立數(shù)學(xué)模型和問題規(guī)模描述。（2）建立把一個規(guī)模較大的問題劃分為規(guī)模較）建立把一個規(guī)模較大的問題劃分為規(guī)模較小問題的途徑。小問題的途徑。（3）定義可以立

26、即解決（規(guī)模最小）的問題的）定義可以立即解決（規(guī)模最?。┑膯栴}的解決方法。解決方法。（4）建立把若干個小問題的解合成大問題的方）建立把若干個小問題的解合成大問題的方法。法。第四節(jié) 分治算法n例例3.4.1：求正整數(shù)集合（求正整數(shù)集合（a1,a2,.,an）的最大值和最小）的最大值和最小值。值。建立數(shù)學(xué)模型和問題規(guī)模的描述：題目本身有建立數(shù)學(xué)模型和問題規(guī)模的描述：題目本身有很強的數(shù)學(xué)背景，數(shù)學(xué)模型應(yīng)該是該問題的一很強的數(shù)學(xué)背景，數(shù)學(xué)模型應(yīng)該是該問題的一般數(shù)學(xué)解釋。我們可以定義問題（般數(shù)學(xué)解釋。我們可以定義問題（f，t）表示）表示求集合（求集合（af,af+1,.,at）中的最大值和最小值。）中的

27、最大值和最小值。我們需要解決的問題是（我們需要解決的問題是（1，n）第四節(jié) 分治算法n當需要求解問題（當需要求解問題（f，t）（共）（共t-f+1個元素），個元素），我們可以把這個集合（我們可以把這個集合（af,af+1,.,at）分成兩）分成兩半，即設(shè)半，即設(shè)m=f+(f-t)/2，集合分為（，集合分為（af,.,am）和（和（am+1,.,at）兩個集合）兩個集合;n這兩個集合中只含有這兩個集合中只含有(f-t)/2或者或者(f-t)/2+1個元素。個元素。n將問題（將問題（f，t）劃分成兩個規(guī)模較小的問題（）劃分成兩個規(guī)模較小的問題（f，m）和（）和（m+1，t）。）。第四節(jié) 分治算法n

28、顯然，當集合中只有一個元素時，問題立刻有解，集顯然，當集合中只有一個元素時，問題立刻有解，集合的最大值和最小值都是集合中唯一的元素。合的最大值和最小值都是集合中唯一的元素。n建立把若干個小問題的解合成大問題的方法建立把若干個小問題的解合成大問題的方法1) 問題（問題（f，m）的最大值和問題（）的最大值和問題（m+1，t）的最大值）的最大值中的大者就是問題（中的大者就是問題（f，t）的最大值；）的最大值；2)問題（問題（f，m）的最小值和問題（）的最小值和問題（m+1，t）的最小值）的最小值中的小者就是問題（中的小者就是問題（f，t）的最小值。）的最小值。 第四節(jié) 分治算法n主要算法描述主要算法

29、描述:program ex2_6_1;var a:array 1.10000 of Integer;procedure MaxMin(f,t:Integer;varrMax,rMin:Integer);var m:Integer; Max1,Max2,Min1,Min2:Integer;begin if f=t then begin rMax:=af; rMin:=at; end第四節(jié) 分治算法elsebegin m:=(t-f) div 2 + f; MaxMin(f,m,Max1,Min1); MaxMin(m+1,t,Max2,Min2); rMax:=Max(Max1,Max2); r

30、Min:=Min(Min1,Min2);end;end;第四節(jié) 分治算法var Fin:Text;var i,n,rMax,rMin:Integer;begin 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é) 分治算法nex_2_6_1.txt測試用例：測試用例：72 34 32 19 1 39 4

31、程序運行結(jié)果如下：程序運行結(jié)果如下：Max=39,Min=1第五節(jié) 高精度計算n計算機計算的精確范圍是有限的，例如計算機計算的精確范圍是有限的，例如,整型整型的精確度為的精確度為Int64時，值域是時，值域是-263263-1如果需要精度更高的計算，就需要編程實現(xiàn)。如果需要精度更高的計算，就需要編程實現(xiàn)。在本節(jié)中，主要介紹正整數(shù)的高精度計算（加，在本節(jié)中，主要介紹正整數(shù)的高精度計算（加，減，乘和除），至于整數(shù)，有理數(shù)乃至實數(shù)的減，乘和除），至于整數(shù)，有理數(shù)乃至實數(shù)的高精度運算，可參考這一部分所介紹的正整數(shù)高精度運算，可參考這一部分所介紹的正整數(shù)高精度運算。高精度運算。第五節(jié) 高精度計算n正整數(shù)

32、高精度加法正整數(shù)高精度加法n加法和減法都是最基本的運算，乘除法運算是加法和減法都是最基本的運算，乘除法運算是建立在加減法之上的。建立在加減法之上的。n加法算法如下加法算法如下：第五節(jié) 高精度計算步驟步驟說明說明舉例（舉例（S1+S2） 表示參與運算或被改變的表示參與運算或被改變的數(shù)字數(shù)字S1=82S2=741對位。在被加數(shù)和加數(shù)前面對位。在被加數(shù)和加數(shù)前面適當補適當補0，使他們的包含，使他們的包含相同的位數(shù)。相同的位數(shù)。82742前面再補一個前面再補一個0，確定和的最，確定和的最多位數(shù)。多位數(shù)。0820743從低位開始，對應(yīng)位相加，從低位開始，對應(yīng)位相加，結(jié)果寫入被加數(shù)中。如果結(jié)果寫入被加數(shù)中

33、。如果有進位，直接給被加數(shù)前有進位，直接給被加數(shù)前一位加一位加1。0860741560741560744刪除和前面多余的刪除和前面多余的0156074第五節(jié) 高精度計算n2正整數(shù)高精度減法正整數(shù)高精度減法n減法和加法的最大區(qū)別在于：減法是從高位開減法和加法的最大區(qū)別在于：減法是從高位開始相減，而加法是從低位開始相加。始相減，而加法是從低位開始相加。n減法算法如下：減法算法如下：第五節(jié) 高精度計算步驟步驟說明說明舉例（舉例（S1-S2） 表示參與運算或被改變表示參與運算或被改變的數(shù)字的數(shù)字S1=82S2=741對位。在被減數(shù)和減數(shù)前對位。在被減數(shù)和減數(shù)前面適當補面適當補0，使他們的包，使他們的包

34、含相同的位數(shù)。含相同的位數(shù)。82742從高位開始，對應(yīng)位相減，從高位開始，對應(yīng)位相減，結(jié)果寫入被減數(shù)中。如結(jié)果寫入被減數(shù)中。如果需要借位，直接給被果需要借位，直接給被減數(shù)前一位減減數(shù)前一位減1。127408743刪除和前面多余的刪除和前面多余的0874第五節(jié) 高精度計算n3正整數(shù)高精度乘法正整數(shù)高精度乘法n乘法的主要思想是把乘法轉(zhuǎn)化為加法進行運算。乘法的主要思想是把乘法轉(zhuǎn)化為加法進行運算。請先看下面的等式：請先看下面的等式：12345*4=12345+12345+12345+1234512345*20=123450*212345*24=12345*20+12345*4第五節(jié) 高精度計算n等式（

35、等式（1）說明，多位數(shù)乘一位數(shù)，可以直接使用加）說明，多位數(shù)乘一位數(shù)，可以直接使用加法完成。法完成。n等式（等式（2）說明，多位數(shù)乘形如）說明，多位數(shù)乘形如d*10n的數(shù)，可以轉(zhuǎn)的數(shù)，可以轉(zhuǎn)換成多位數(shù)乘一位數(shù)來處理。換成多位數(shù)乘一位數(shù)來處理。n等式（等式（3）說明，多位數(shù)乘多位數(shù)，可以轉(zhuǎn)換為若干）說明，多位數(shù)乘多位數(shù)，可以轉(zhuǎn)換為若干個個“多位數(shù)乘形如多位數(shù)乘形如d*10n的數(shù)的數(shù)”之和。之和。n因此，多位數(shù)乘多位數(shù)最終可以全部用加法來實現(xiàn)。因此，多位數(shù)乘多位數(shù)最終可以全部用加法來實現(xiàn)。第五節(jié) 高精度計算n算法描述如下：算法描述如下：function multiply(s1,s2:string)

36、:string;var i:Integer; C:Char;begin Result:=0;/多位數(shù)乘多位數(shù)，可以轉(zhuǎn)換為若干個多位數(shù)乘多位數(shù)，可以轉(zhuǎn)換為若干個“多位數(shù)乘多位數(shù)乘形如形如d*10n的數(shù)的數(shù)”之和之和 for i:=Length(s2) downto 1 do 第五節(jié) 高精度計算begin /多位數(shù)乘一位數(shù)，可以直接相加多位數(shù)乘一位數(shù)，可以直接相加 for C:=1 to S2i do Result:=addition(Result,S1);/多位數(shù)乘形如多位數(shù)乘形如d*10n的數(shù)轉(zhuǎn)換成多位數(shù)乘一位數(shù)來處理的數(shù)轉(zhuǎn)換成多位數(shù)乘一位數(shù)來處理 S1:=S1+0; end;Result:=

37、Clear(Result);multiply:=Result;end;第五節(jié) 高精度計算執(zhí)行步數(shù)S1S2Result0121201121224212012144 例如例如12*12，算法執(zhí)行過程如下（多位數(shù)乘一位數(shù)看成，算法執(zhí)行過程如下（多位數(shù)乘一位數(shù)看成是一步完成）；是一步完成）；第五節(jié) 高精度計算n4正整數(shù)高精度除法正整數(shù)高精度除法n高精度除法是基于精度減法的，主要的思想是高精度除法是基于精度減法的，主要的思想是“試商試商”，模仿筆算除法的方法。，模仿筆算除法的方法。n算法描述如下：算法描述如下：第五節(jié) 高精度計算function division(s1,s2:string):string

38、;begin /Result中存放的是商中存放的是商 Result:=; /S中存放的是余數(shù)，中存放的是余數(shù)，S1是被除數(shù)，是被除數(shù)，S2是除數(shù)是除數(shù) S:=; /逐位試商逐位試商 for i:=1 to Length(S1) do begin S:=S+S1i; 第五節(jié) 高精度計算/先試商先試商0Result:=Result+0;/然后從然后從1開始不斷往上試開始不斷往上試While Bigger(S,S2) do begin Inc(ResultLength(Result); S:=Subtraction(S,S2); end;end;/刪除多余的刪除多余的0Result:=Clear(R

39、esult);division:=Result;end; 第五節(jié) 高精度計算執(zhí)行步執(zhí)行步數(shù)數(shù)S1S2SResult說明說明014412開始狀態(tà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ù)的大小，如果比較兩個數(shù)的大小，如果S1=S2，結(jié)果返回為真。，結(jié)果返回為真。function bigger(s1,s2:string):boolean;begin bigger:=true; if l

40、ength(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 thenbegin Dec(S1i,10); Inc(S1i-1);end;end; Result:=Clear(S1);addi

41、tion:=Result;end;第五節(jié) 高精度計算begin/逐位相加逐位相加Inc(S1i,Ord(S2i)-Ord(0);/處理進位處理進位if S1i9 then begin Dec(S1i,10); Inc(S1i-1); end;end;Result:=Clear(S1);addition:=Result;end;第五節(jié) 高精度計算/減法減法/這里假設(shè)這里假設(shè)S1=S2，如果不滿足這個條件，如果不滿足這個條件，/函數(shù)返回結(jié)果不正確函數(shù)返回結(jié)果不正確function Subtraction(s1,s2:string):string;var i:integer;begin /對位對位

42、while Length(S1)Length(S2) do S1:=0+S1; while Length(S2)=S2i then Dec(S1i,Ord(S2i)-Ord(0) else /有借位的情況有借位的情況 begin Inc(S1i,10); Dec(S1i-1); Dec(S1i,Ord(S2i)-Ord(0) end; Result:=Clear(S1);Subtraction:=Result;end;第五節(jié) 高精度計算/乘法乘法function multiply(s1,s2:string):string;var i:Integer;C:Char;begin Result:=0

43、; 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è)除數(shù)不為這里假設(shè)除數(shù)不為0，如果除數(shù)為，如果除數(shù)為0，函數(shù)進入死循環(huán)。，函數(shù)進入死循環(huán)。function division(s1,s2:string):string;var i:integer; s:String;begin Result:=; S:=; for i:=1

44、to Length(S1) do第五節(jié) 高精度計算beginS:=S+S1i;Result:=Result+0;While Bigger(S,S2) dobegin Inc(ResultLength(Result); S:=Subtraction(S,S2);end;end; Result:=Clear(Result);division:=Result;end;第五節(jié) 高精度計算begin WriteLn(Addition(999,1); WriteLn(Subtraction(890,99); WriteLn(Multiply(99,99); WriteLn(Division(9899,99

45、); ReadLn;end.第五節(jié) 高精度計算n程序運行結(jié)果：程序運行結(jié)果：1000791980199 第五節(jié) 高精度計算n特別說明，上面的程序中的減法和除法沒有判斷是否特別說明，上面的程序中的減法和除法沒有判斷是否夠減和除數(shù)為夠減和除數(shù)為0，如果對于一般問題，調(diào)用減法和除，如果對于一般問題，調(diào)用減法和除法之前應(yīng)該做檢查，如下例所示：法之前應(yīng)該做檢查，如下例所示：/判斷夠減（結(jié)果不出現(xiàn)負數(shù)）判斷夠減（結(jié)果不出現(xiàn)負數(shù)）if Bigger(s1,s2) then Result:=Subtraction(s1,s2);/判斷除數(shù)不為判斷除數(shù)不為0if Clear(s2)0 then Result:=

46、Division(s1,s2);第六節(jié) 求解線性方程組n解線性方程組是一類常用的基礎(chǔ)問題。例如，在計算解線性方程組是一類常用的基礎(chǔ)問題。例如，在計算幾何中，需要求直線的交點，在列出直線方程后，就幾何中，需要求直線的交點，在列出直線方程后，就直接轉(zhuǎn)化為解線性方程組問題了；又如線性規(guī)劃問題，直接轉(zhuǎn)化為解線性方程組問題了；又如線性規(guī)劃問題，解線性方程組也是其中的一個基礎(chǔ)子問題。解線性方程組也是其中的一個基礎(chǔ)子問題。n解線性方程組的方法很多，例如解線性方程組的方法很多，例如Gauss消元法，消元法，LU法，求逆陣法，法，求逆陣法，Gauss-Seidel(迭代迭代)法等等，其中法等等，其中Gauss消

47、元法需要的數(shù)學(xué)背景知識最少，而且比較容消元法需要的數(shù)學(xué)背景知識最少，而且比較容易實現(xiàn)，下面主要介紹使用易實現(xiàn)，下面主要介紹使用Gauss消元法求解線性方消元法求解線性方程組問題。程組問題。第六節(jié) 求解線性方程組n下面簡單介紹一下關(guān)于線性方程組的一些下面簡單介紹一下關(guān)于線性方程組的一些背景知識：背景知識：na1x1+.+anxn=b線性方程式線性方程式(Linearequation)，其中，其中a1,.,an為系數(shù)，為系數(shù)，x1,.,xn為未知數(shù)或變量為未知數(shù)或變量(unknowns)，b為常數(shù)。為常數(shù)。第六節(jié) 求解線性方程組ln元元m次聯(lián)立方程式：次聯(lián)立方程式：mnmnmnnnnbxaxabx

48、axabxaxa.112212111111第六節(jié) 求解線性方程組n上式有上式有m個方程式及個方程式及n個未知元所形成的線性方程個未知元所形成的線性方程組。組。 mmmnmmnnbbbxxxaaaaaaaaa.*.2121212222111211第六節(jié) 求解線性方程組n其中 n稱為系數(shù)矩陣稱為系數(shù)矩陣 mnmmnnaaaaaaaaa.212222111211第六節(jié) 求解線性方程組為未知向量未知向量， mxxx.21第六節(jié) 求解線性方程組為常數(shù)向量常數(shù)向量。 mbbb.21第六節(jié) 求解線性方程組n上面的矩陣也可以表示為增廣的形式：上面的矩陣也可以表示為增廣的形式：mmnmmnnbbbaaaaaaa

49、aa.21212222111211第六節(jié) 求解線性方程組nGauss消元法主要是基于增廣矩陣的變換。算法如下：消元法主要是基于增廣矩陣的變換。算法如下：n設(shè)所有行都為設(shè)所有行都為“未處理行未處理行”，然后從第，然后從第1列到第列到第n列依列依次掃描矩陣次掃描矩陣a。n當掃描到第當掃描到第k列時，在矩陣列時，在矩陣a所有未處理過的行中找出所有未處理過的行中找出第第k列中的最大值，和最大值所在行列中的最大值，和最大值所在行p。n如果最大值為如果最大值為0，說明方程組無解或者有無窮多組解。，說明方程組無解或者有無窮多組解。否則，繼續(xù)下面操作。否則，繼續(xù)下面操作。第六節(jié) 求解線性方程組n設(shè)置行設(shè)置行p

50、為已處理行，同時對其他的每一行，找到一為已處理行，同時對其他的每一行，找到一個適當?shù)臄?shù)，然后把行個適當?shù)臄?shù)，然后把行p乘以這個適當?shù)臄?shù)加到該行乘以這個適當?shù)臄?shù)加到該行中，使得通過上述變換后，該行第中，使得通過上述變換后，該行第k列的元素為列的元素為0。顯。顯然，對第然，對第i行，這個適當?shù)臄?shù)為行，這個適當?shù)臄?shù)為-ai,k/ap,k。n經(jīng)過上面的從第經(jīng)過上面的從第1列到第列到第n列的掃描后，矩陣列的掃描后，矩陣a中每行中每行僅又一個非僅又一個非0值，記第值，記第i行的非行的非0值為值為ai,j，則有，則有xj:=bi/ai,j。n算法舉例：算法舉例：n求解方程：求解方程：第六節(jié) 求解線性方程組x

51、1+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 2.00 3.00 1.00 | 4.00第六節(jié) 求解線性方程組n在第在第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é) 求解線性方程組n在第

52、在第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é) 求解線性方程組n在第在第3列中，最大值為列中，最大值為a1,3（因為此時未處（因為此時未處理行只有第一行），類似上面的做法處理。理行只有第一行），類似上面的做法處理。0.00 0.00 0.09 | 0.363.00 0.00 0.00 | 9.000.00 3.67 0.0

53、0 | -7.33第六節(jié) 求解線性方程組n最后的結(jié)果為：最后的結(jié)果為：nx1= 3.000000 x2=-2.000000 x3=4.000000第六節(jié) 求解線性方程組n實現(xiàn)實現(xiàn)Gauss消元法算法描述如下：消元法算法描述如下：program ex2_7_2;/定義一維向量和二維向量定義一維向量和二維向量const maxn=100;type tmatrix=array1.maxn,1.maxn of real; tvector=array1.maxn of real;第六節(jié) 求解線性方程組/用用Gauss消元法求解線性方程組消元法求解線性方程組ax=b/Input: 數(shù)組數(shù)組a1.n,1.n

54、，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列中，絕對值最大值對應(yīng)的（列中，絕對值最大值對應(yīng)的（p） p:=0;max:=0; for i:=1 to n do if (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