资源描述：
《数论算法及计算几何算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第八章数论算法及计算几何算法教学目标理解求最大公约数的算法掌握欧几里德公式的推广掌握求解同余方程的算法掌握运用中国剩余定理解决实际问题理解线段相交的概念掌握线段是否相交的判定算法理解凸包的概念及穷举搜索的解决方法掌握凸包问题及最接近点对问题的分治法8.1最大公约数定义1设a，b是整数，b≠0，如果存在整数c，使得a=bc成立．则称a被b整除，a是b的倍数，b是a的约数(因数或除数)，可记为b
2、a；如果不存在整数c使得a＝bc成立，则称a不被b整除，记为ba。定理1(带余数除法)设a与b是两个整数，b≠0，则存在唯一的两个整数q和r，使得a=bq+r，0≤r<
3、b
4、
5、。（证明略）定义2在定理1的表达式a=bq+r中，称q是a被b除的商，r是a被b除的余数。最大公约数是指两个或两个以上整数的公共约数中最大者。8.1.1欧几里德算法欧几里德定理任意给定两个整数a,b，不妨假设a≥b。它们的最大公约数用gcd(a，b)表示，则gcd(a，b)=gcd(b，amodb)，其中amodb表示a被b除所得的余数欧几里德递归定义式应用举例（求100和210最大公约数）欧几里德递归公式的推广来解决“已知a,b求解一组x，y使得ax+by=gcd(a,b) ”问题令gcd(a,b)=d，则ax+by=d；gcd(b,amodb)=d(8-1)（
6、1）当b=0时，则gcd(a,b)=a；ax+by=a，即ax=a，则x=1，y取任意实数。简单起见，算法取y=0；（2）当b≠0时，令a'=b，b'=amodb，则gcd(a',b')=d，a'x'+b'y'=d。由于b'=amodb=，则a'x'+b'y'=bx'+()y'=ay'+b(x'-y')=d(8-2)让式(8-1)和式(8-2)对应项相等，则x=y'，y=x'-y'。8.1.2Stein算法基于的两条结论（1）gcd(a，0)=a。（2）gcd(ka，kb)=kgcd(a，b)算法步骤步骤1：初始时，令c=1；步骤2：如果a=0，c=b*c；如果b
7、=0，c=a*c；算法结束。步骤3：令a1=a，b1=b；步骤4：a和b奇偶性的判断。如果a和b都是偶数，则a=a/2，b=b/2，c=2*c；如果a是偶数，b不是偶数，则a=a/2；如果b是偶数，a不是偶数，则b=b/2；如果a和b都不是偶数，则a=
8、a1–b1
9、，b=min(a1,b1)；转步骤2。应用举例求15和9的最大公约数8.2同余方程同余式设a、b和m为整数，其中m＞0。若a和b被m除得的余数相同，则称a和b对模m同余。记为或同余式的简单性质（1）若ab(m)，则m
10、(b-a)。反过来，若m
11、(b-a)，则ab(m)；（2）如果a=km+b(k为整数)
12、，则ab(m)；（3）每个整数恰与0,1,…，m-1这m个整数中的某一个对模m同余；（4）同余关系是一种等价关系：反身性aa(m)；对称性ab(m)，则ba(m)，反之亦然；传递性ab(m)，bc(m)，则ac(m)。（5）如果ab(m)，xy(m)，则①ax(by)(m);②特别地。例1：使2n+1能被3整除的一切自然数n例2：求2999最后两位数码同余方程设是整系数多项式，m是正整数，称f(x)0(modm)(8-4)是关于未知数x的模m的同余方程，简称为模m的同余方程。若则称式(8-4)为n次同余方程同余方程的解设x0是整数，当x＝x0时式(8-4)成立，则
13、称x0是同余方程(8-4)的解。凡对于模m同余的解，被视为同一个解一次同余方程设a，b为整数，且，则称同余方程axb(modm)(8-5)为一次同余方程。定义7设a1,a2,…,an是非零整数，b是整数，称关于未知数x1,x2,…,xn的方程a1x1+a2x2+…+anxn=b是n元一次不定方程。定理3一次同余方程有解的充要条件是gcd(a,m)
14、b。若有解，则恰有d=gcd(a，m)个解。证明（见板书）一次同余方程的求解步骤步骤1：求gcm(a，m)；步骤2：令d=gcm(a，m)，如果db，则式(8-5)无解，算法结束；如果,则转步骤3；步骤3：根据欧几里德公
15、式的推广，求出式(8-5)的一个解x0。步骤3-1：根据欧几里德公式的推广算法求得满足ax'+my'=d的x'，y'；具体方法：将ax'+my'=d变形可得到：ax'=d-my'(8-8)式（8-8）两边同时模m得：(8-9)可见，x'是一次同余方程(8-9)的解。步骤3-2：根据x'求x0。具体方法：由于，设，则根据同余式的性质得：即：。因此，x0=px'=x'(modm)。步骤4：根据(8-7)式可得(8-5)式的其它d-1个解为，i=1,2,…,d-1。算法结束。量水有三个分别装有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)。现c筒装
16、满水，问能
