第8章-數(shù)論算法及計(jì)算幾何算法

1、第八章 數(shù)論算法及計(jì)算幾何算法,,教學(xué)目標(biāo),理解求最大公約數(shù)的算法掌握歐幾里德公式的推廣掌握求解同余方程的算法掌握運(yùn)用中國(guó)剩余定理解決實(shí)際問(wèn)題理解線段相交的概念掌握線段是否相交的判定算法理解凸包的概念及窮舉搜索的解決方法掌握凸包問(wèn)題及最接近點(diǎn)對(duì)問(wèn)題的分治法,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是兩個(gè)整數(shù)，b≠0，則存在唯一的兩個(gè)整數(shù)q和r，使得a=bq+r，0≤r<|b|。（證明略）定義2 在定理1的表達(dá)式a=bq+r中，稱q是a被b除的商，r是a被b除的余數(shù)。最大公約數(shù)是指兩個(gè)或兩個(gè)以上整數(shù)的公共約數(shù)中最大者。,8.1.1歐幾里德算法,歐幾里德定理 任意給定兩個(gè)整數(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ù)）歐幾里德遞歸公式的推廣 來(lái)解決“已知a, b求解一組x，y使得ax+by=gcd(a, b) ”問(wèn)題 令gcd(a, b)=d，則ax+by=d；gcd(b,a mod b)=d (8-1)（1）當(dāng)b=0時(shí)，則gcd(a,b)=a；ax+by=a，即ax=

4、a，則x=1，y取任意實(shí)數(shù)。簡(jiǎn)單起見(jiàn)，算法取y=0；（2）當(dāng)b≠0時(shí)，令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)對(duì)應(yīng)項(xià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：初始時(shí)，令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對(duì)模m同余。記為 或同余式的簡(jiǎn)單性質(zhì)

7、 （1）若a b(m)，則m|(b-a)。反過(guò)來(lái)，若m|(b-a)，則a b(m)；（2）如果a=km+b(k為整數(shù))，則a b(m)；（3）每個(gè)整數(shù)恰與0,1,…，m-1這m個(gè)整數(shù)中的某一個(gè)對(duì)模m同余；（4）同余關(guān)系是一種等價(jià)關(guān)系：反身性 a a(m)；對(duì)稱性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ù)多項(xiàng)式，m是正整數(shù)，稱f(x)

9、 0(mod m) (8-4) 是關(guān)于未知數(shù)x的模m的同余方程，簡(jiǎn)稱為模m的同余方程。若 則稱式(8-4)為n次同余方程 同余方程的解設(shè)x0是整數(shù)，當(dāng)x＝x0時(shí)式(8-4)成立，則稱x0是同余方程(8-4)的解。凡對(duì)于模m同余的解，被視為同一個(gè)解,,,,,一次同余方程 設(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)個(gè)解。證明（見(jiàn)板書(shū)）一次同余方程的求解步驟,步驟1：求gcm(a，m)；步驟2：令d= gcm(a，m)，如果d b，則式(8-5)無(wú)解，算法結(jié)束；如果 ,則轉(zhuǎn)步驟3；步驟3：根據(jù)歐幾里德公式的推廣

11、，求出式(8-5)的一個(gè)解x0。步驟3-1：根據(jù)歐幾里德公式的推廣算法求得滿足ax' +my'=d的x'，y'；具體方法：將ax'+my'=d變形可得到：ax'=d-my' (8-8)式（8-8）兩邊同時(shí)模m得： (8-9)可見(jiàn)，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個(gè)解為 ，i=1,2,…,d-1。算法結(jié)束。,,,

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

14、題實(shí)質(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同時(shí)滿足n個(gè)同余方程： ，則r稱為這n個(gè)同余方程組成的同余方程組的解,,,定理 對(duì)同余方程組記 ， 其中， 表示m

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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