數(shù)論算法及計算幾何算法

1、第八章 數(shù)論算法及計算幾何算法,,教學(xué)目標(biāo),理解求最大公約數(shù)的算法掌握歐幾里德公式的推廣掌握求解同余方程的算法掌握運用中國剩余定理解決實際問題理解線段相交的概念掌握線段是否相交的判定算法理解凸包的概念及窮舉搜索的解決方法掌握凸包問題及最接近點對問題的分治法,8.1最大公約數(shù),定義1 設(shè)a，b是整數(shù)，b≠0，如果存在整數(shù)c，使得a=bc成立．則稱a被b整除，a是b的倍數(shù)，b是a的約數(shù)(因數(shù)或除數(shù))，可記為b|a；如果不存在

2、整數(shù)c使得a＝bc成立，則稱a不被b整除，記為ba。定理1(帶余數(shù)除法) 設(shè)a與b是兩個整數(shù)，b≠0，則存在唯一的兩個整數(shù)q和r，使得a=bq+r，0≤r<|b|。（證明略）定義2 在定理1的表達(dá)式a=bq+r中，稱q是a被b除的商，r是a被b除的余數(shù)。最大公約數(shù)是指兩個或兩個以上整數(shù)的公共約數(shù)中最大者。,8.1.1歐幾里德算法,歐幾里德定理 任意給定兩個整數(shù)a,b，不妨假設(shè)a≥b。它們的最大公約數(shù)用gcd(a，b)表

3、示，則gcd(a，b)=gcd(b，a mod b) ，其中a mod b表示a被b除所得的余數(shù) 歐幾里德遞歸定義式,,應(yīng)用舉例（求100和210最大公約數(shù)）歐幾里德遞歸公式的推廣 來解決“已知a, b求解一組x，y使得ax+by=gcd(a, b) ”問題 令gcd(a, b)=d，則ax+by=d；gcd(b,a mod b)=d (8-1)（1）當(dāng)b=0時，則gcd(a,b)=a；ax+by=a，即ax=

4、a，則x=1，y取任意實數(shù)。簡單起見，算法取y=0；（2）當(dāng)b≠0時，令a'=b，b'=a mod b，則gcd(a', b')=d，a'x'+b'y'=d。由于b' =a mod b = ，則a'x'+b'y'=bx'+( )y'=ay' +b(x' -y&#

5、39;)=d (8-2) 讓式(8-1)和式(8-2)對應(yīng)項相等，則x=y'，y= x' -y'。,,8.1.2 Stein算法,基于的兩條結(jié)論（1）gcd(a，0)=a。（2）gcd(ka，kb)=k gcd(a，b) 算法步驟 步驟1：初始時，令c=1；步驟2：如果a=0，c=b*c；如果b=0，c=a*c；算法結(jié)束。 步驟3：令a1=a，b1=b；步驟4：a和b奇偶性的判斷。

6、,如果a和b都是偶數(shù)，則a=a/2，b=b/2，c=2*c；如果a是偶數(shù)，b不是偶數(shù)，則a=a/2；如果b是偶數(shù)，a不是偶數(shù)，則b=b/2；如果a和b都不是偶數(shù)，則a =|a1 –b1|，b=min(a1,b1)；轉(zhuǎn)步驟2。應(yīng)用舉例求15和9的最大公約數(shù),8.2同余方程,同余式 設(shè)a、b和m為整數(shù)，其中m＞0。若a和b被m除得的余數(shù)相同，則稱a和b對模m同余。記為 或同余式的簡單性質(zhì)

7、 （1）若a b(m)，則m|(b-a)。反過來，若m|(b-a)，則a b(m)；（2）如果a=km+b(k為整數(shù))，則a b(m)；（3）每個整數(shù)恰與0,1,…，m-1這m個整數(shù)中的某一個對模m同余；（4）同余關(guān)系是一種等價關(guān)系：反身性 a a(m)；對稱性a b(m)，則b a(m)，反之亦然；傳遞性a b(m)，b c(m)，則a c(m)。

8、（5）如果a b(m)，x y(m)，則① a x (b y)(m);② 特別地 。,,,,,,,,例1：使2n+1能被3整除的一切自然數(shù)n 例2：求2999最后兩位數(shù)碼同余方程 設(shè) 是整系數(shù)多項式，m是正整數(shù)，稱f(x)

9、 0(mod m) (8-4) 是關(guān)于未知數(shù)x的模m的同余方程，簡稱為模m的同余方程。若 則稱式(8-4)為n次同余方程 同余方程的解設(shè)x0是整數(shù)，當(dāng)x＝x0時式(8-4)成立，則稱x0是同余方程(8-4)的解。凡對于模m同余的解，被視為同一個解,,,,,一次同余方程 設(shè)a，b為整數(shù)，且，則稱同余方程ax b(mod m) (8-5)為一次同余方程。定義7 設(shè)a1,

10、a2,…,an是非零整數(shù)，b是整數(shù)，稱關(guān)于未知數(shù)x1,x2,…,xn的方程a1x1+a2x2+…+anxn=b是n元一次不定方程。定理3 一次同余方程有解的充要條件是gcd(a,m)|b。若有解，則恰有d=gcd(a，m)個解。證明（見板書）一次同余方程的求解步驟,步驟1：求gcm(a，m)；步驟2：令d= gcm(a，m)，如果d b，則式(8-5)無解，算法結(jié)束；如果 ,則轉(zhuǎn)步驟3；步驟3：根據(jù)歐幾里德公式的推廣

11、，求出式(8-5)的一個解x0。步驟3-1：根據(jù)歐幾里德公式的推廣算法求得滿足ax' +my'=d的x'，y'；具體方法：將ax'+my'=d變形可得到：ax'=d-my' (8-8)式（8-8）兩邊同時模m得： (8-9)可見，x'是一次同余方程(8-9

12、)的解。步驟3-2：根據(jù)x'求x0。具體方法：由于 ，設(shè) ，則根據(jù)同余式的性質(zhì)得： 即： 。因此，x0=px'= x'(mod m)。步驟4：根據(jù)(8-7)式可得(8-5)式的其它d-1個解為 ，i=1,2,…,d-1。算法結(jié)束。,,,

13、,,,,,,,量水 有三個分別裝有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)?，F(xiàn)c筒裝滿水，問能否在c簡中量出d升水(c>d>0)。若能，請列出一種方案。算法分析：量水過程實際上就是倒來倒去，每次倒的時候總有如下幾個特點：總有一個筒中的水沒有變動；不是一個筒被倒?jié)M就是另一個筒被倒光；c筒僅起中轉(zhuǎn)作用。而本身容積除了必須足夠裝下a筒和b筒的全部水外，別無其它限制。通過上述分析知：問

14、題實質(zhì)上是將a筒倒?jié)Mx次，b筒倒?jié)My次，使得總結(jié)果有 ax十by＝d (8-10)設(shè)a＝3，b＝7，c＝10，求x,y,8.3同余方程組,若數(shù)r同時滿足n個同余方程： ，則r稱為這n個同余方程組成的同余方程組的解,,,定理 對同余方程組記 ， 其中， 表示m

15、1和m2的最小公倍數(shù)。①若d(a1-a2)，則此同余方程組無解；②若d|( a1-a2)，則此同余方程組有對模M的一類剩余解。中國剩余定理（即孫子定理） 設(shè) 是兩兩互質(zhì)的正整數(shù)，記M= ，則同余方程組,,,,,,有對模M的唯一解其中證明（見板書）例：早在幾千年前中國的一本《孫子算經(jīng)》就已經(jīng)提

16、及這個問題的解法了，原文為：“今有物，不知其數(shù)，三三數(shù)之，剩二；五五數(shù)之，剩三；七七數(shù)之，剩二，問物幾何？” 答曰：“二十三”。,,,,8.4線段相交,線段性質(zhì) 有向線段 P1為始點，P2為終點，長度如果P1(0,0)，則 記為無向線段為P1P2 叉積的概念叉積是一種向量乘法 ，向量 叉乘向量 得到另一個向量 ，則 = × = 方向為右手

17、直角坐標(biāo)系,,,,,,,,幾何意義以 和 為邊的平行四邊形的面積 叉積定義為一個矩陣行列式 思考1：叉積何時小于0？何時大于0？又何時等于0？思考2：對公共點P0而言，如何知道有向線段 在有向線段 的什么方向？ 通過叉積可以知道,,,,確定兩條線段是否相交 第一步：通過快速排斥實驗來確定兩條線段是否不相交；第二步：在快速排斥實驗判斷有可能相交的前提下進行跨立實驗，來確定兩條線段是否相互跨立確定

18、任意一對線段相交 對應(yīng)給定的一個線段集合，確定其中任意兩條線段是否相交。該算法輸入由若干條線段組成的集合，若這組線段中存在任意一對線段相交，則返回true；否則，返回false 兩點假設(shè)（1）線段集合中的所有線段都不是豎直的；（2）未有三條輸入線段相交于同一點的情形。,算法思想假設(shè)一條垂直掃描線沿X軸方向從左到右順序移動、穿過已知的若干線段。移動過程中，每遇到一個線段端點，它就將穿過掃描線的所有線段放入一個動態(tài)數(shù)據(jù)結(jié)構(gòu)中，并利

19、用它們之間的關(guān)系進行排序，核查是否有相交點存在。該算法要求安排兩個集合，一個是T序列，另一個是掃描線的一系列位置，即線段端點位置，并且要標(biāo)記端點為線段的左端點還是線段的右端點。遇到左端點時將線段插入序列T中，并考察與其相鄰的線段是否相交；遇到右端點時將線段從序列T中刪除，此時考察被刪除線段的左右兩條線段是否相交。,8.5凸包問題,給定一個點集S＝{P0,P1,…,Pn-1}，它的凸包是一個最小的凸多邊形P，且滿足S中的每個點或者在P的

20、邊界上或者在P的內(nèi)部 如果點集S是兩個點的集合，顯然它的凸包是連接這兩個點的線段；如果S是由三個不共線的點組成的集合，那么凸包是以這三個點為頂點的三角形；如果三點共線，則凸包是以距離最遠(yuǎn)的兩個點為端點的線段。對于更大的集合，在直觀上，可以把S中的每個點看作訂在地上的木樁，那么凸包就是將所有木樁圍起來的一個拉緊的橡皮繩的形狀，如圖8-1所示。,,,8.5.1凸包問題的窮舉搜索法,算法思想 根據(jù)凸多邊形的定義，對于一個由n個點組成

21、的集合S中的任意兩個點Pi和Pj，當(dāng)且僅當(dāng)該集合中的其它點要么位于穿過Pi和Pj直線的同側(cè)，要么位于線段PiPj上。則線段PiPj是該集合凸多邊形邊界的一部分。對每一個點都做一遍檢驗之后，滿足條件的線段就構(gòu)成了該凸包的邊界算法求解步驟 對于集合中的任意兩點Pi和Pj ，定義穿過它們直線方程 。將點集S中的其余點代入直線方程，然后檢查是否位于線段同側(cè)，如果不是，說明線段PiPj不是點集S的凸多邊形的邊界。否則，PiPj是凸多邊形的邊

22、界。對點集中的每個點，重復(fù)上述步驟，直到找出全部多邊形的邊界,算法分析點集中的點構(gòu)成的線段數(shù)目最多為n(n-1)/2，對每一條線段，最壞情況要檢查點集中其余n-2個點屬于哪個半平面，故算法的時間復(fù)雜性為O(n3),8.5.2凸包問題的分治法,算法思想將點集S中的點按照x坐標(biāo)升序排序，x坐標(biāo)相同的按照y坐標(biāo)升序排序，排好序的序列存放在點結(jié)構(gòu)數(shù)組P中。那么最左邊的點P0、最右邊的點Pn-1肯定是凸包上的點。線段P0Pn-1將集合S中的

23、點分成兩個集合S1和S2。,子集S1的凸包由線段P0Pn-1作為下邊界、多節(jié)鏈條作為上邊界組成。這條上邊界稱為上包。子集S2的凸包由線段P0Pn-1作為上邊界、多節(jié)鏈條作為下邊界組成。這條下邊界稱為下包。整個集合的凸包由上包和下包構(gòu)成。如圖8-2所示。,,算法求解步驟 構(gòu)造上包 找到子集S1中的點Pmax，它是距離線段P0Pn-1最遠(yuǎn)的點 連接 ，找出S1中位于直線

24、 左邊的點，這些點構(gòu)成集合S11；找出S1中位于直線 左邊的點，這些點構(gòu)成集合S12；△P0PmaxPn-1內(nèi)部的點不予考慮遞歸構(gòu)造S11和S12的上包，然后簡單地將它們連接起來，得到S1的上包 構(gòu)造下包找到子集S2中的點Pmin，它是距離線段P0Pn-1最遠(yuǎn)的點 連接 ，找出S2中位于直線 右邊的點，這些點構(gòu)成集合S21；找出S2中位于直線

25、 右邊的點，這些點構(gòu)成集合S22；△P0PminPn-1內(nèi)部的點不予考慮遞歸構(gòu)造S21和S22的上包，然后簡單地將它們連接起來，得到S2的上包,,,8.6最接近點對問題,最接近點對問題要求給定平面上n個點組成的集合S，找出其中n個點組成的點對中距離最近的一對點 。,8.6.1最接近點對問題的窮舉搜索法,算法思想分別計算點集中每一對點的距離，從中找出值最小的那對點。為了避免點對的重復(fù)計算，算法只考慮i<j的情況

26、,8.6.2最接近點對問題的分治法,算法分析從算法描述可知循環(huán)體內(nèi)的時間是常數(shù)時間，循環(huán)次數(shù) ， 因此算法的時間復(fù)雜性為O(n2),,算法思想將所給平面上的n個點的集合S分成規(guī)模大致相等的兩個子集S1和S2。遞歸求解S1和S2中的最接近點對；集合S中的最接近點對或者是子問題S1的解，或者是子問題S2的解，或者是一個點在S1中，一個點在S2中的情況組成的最接近點對。,一維情形用xm將x1,x2,…,xn分成兩部

27、分S1和S2 遞歸求S1中最接近點對，其距離為d1遞歸求S2中最接近點對，其距離為d2求S1中的最大值p，S2中的最小值q比較|p-q|,d1,d2確定哪個是最接近點對。算法分析解此遞歸方程可得T(n)=O(nlogn)。,,二維情形選取一垂直線l：x=xm作為分割線。其中xm為S中各點x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2遞歸求S1中最接近點對，其距離為d1遞歸求S2中最接近點對，其距離為d2令d=min(

28、d1,d2)找出S1中的某個點p和S2中的某個點q組成的點對(p,q) （難點）比較|p-q|,d1,d2確定哪個是最接近點對思考：如何找出點對(p,q) ？如果|p-q|小于d，則p點分布在P1帶形區(qū)域內(nèi)(左虛線和分割線l所夾的區(qū)域)，q點分布在P2帶形區(qū)域內(nèi)(右虛線和分割線l所夾的區(qū)域)。如圖8-5所示,,對于P1中任意一點p，與它距離小于d的點分布在以p點為圓心，以d為半徑的圓內(nèi)。因此，與點p構(gòu)成最接近點對的P2中的點一定

29、落在一個d×2d的矩形R中。如圖8-6所示。,,,,由d的意義可知，矩形R中任何兩個S中的點的距離都大于等于d。由此可知，至少可以將d×2d的矩形R分割成如圖8-7所示的六部分，其中任何一部分包含P2中的點最多有一個 因此，在矩形R中最多只有6個P2中的點與p構(gòu)成最接近點對,,思考：針對P1中的任意一點p，檢查P2中的哪6個點，從而可以找出最接近點對呢 ？可以將p和P2中所有點到垂直線l上。由于能與p點一起構(gòu)成