文档介绍：第8章 数论算法及计算几何算法
第1页，本讲稿共32页
教学目标
理解求最大公约数的算法
掌握欧几里德公式的推广
掌握求解同余方程的算法
掌握运用中国剩余定理解决实际问题
理解线段相交的概念
掌握线段是否相交的判定算法
理解凸) (8-5)为一次同余方程。
定义7 设a1,a2,…,an是非零整数，b是整数，称关于未知数x1,x2,…,xn的方程
a1x1+a2x2+…+anxn=b是n元一次不定方程。
定理3 一次同余方程有解的充要条件是gcd(a,m)|b。若有解，则恰有d=gcd(a，m)个解。
证明（见板书）
一次同余方程的求解步骤
第10页，本讲稿共32页
步骤1：求gcm(a，m)；
步骤2：令d= gcm(a，m)，如果d b，则式(8-5)无解，算法结束；如果 ,则转步骤3；
步骤3：根据欧几里德公式的推广，求出式(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'(mod m)。
步骤4：根据(8-7)式可得(8-5)式的其它d-1个解为 ，i=1,2,…,d-1。算法结束。
第11页，本讲稿共32页
量水
有三个分别装有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)。现c筒装满水，问能否在c简中量出d升水(c>d>0)。若能，请列出一种方案。
算法分析：
量水过程实际上就是倒来倒去，每次倒的时候总有如下几个特点：
总有一个筒中的水没有变动；
不是一个筒被倒满就是另一个筒被倒光；
c筒仅起中转作用。而本身容积除了必须足够装下a筒和b筒的全部水外，别无其它限制。
通过上述分析知：问题实质上是将a筒倒满x次，b筒倒满y次，使得总结果有
ax十by＝d (8-10)
设a＝3，b＝7，c＝10，求x,y
第12页，本讲稿共32页
若数r同时满足n个同余方程： ，则r称为这n个同余方程组成的同余方程组的解
第13页，本讲稿共32页
定理 对同余方程组
记 ， 其中， 表示m1和m2的最小公倍数。
①若d(a1-a2)，则此同余方程组无解；
②若d|( a1-a2)，则此同余方程组有对模M的一类剩余解。
中国剩余定理（即孙子定理）
设 是两两互质的正整数，记
M= ，则同余方程组
第14页，本讲稿共32页
有对模M的唯一解
其中
证明（见板书）
例：早在几千年前中国的一本《孙子算经》就已经提及这个问题的解法了，原文为：“今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二，问物几何？”
答曰：“二十三”。
第15页，本讲稿共32页
线段性质
有向线段 P1为始点，P2为终点，长度
如果P1(0,0)，则 记为
无向线段为P1P2
叉积的概念
叉积是一种向量乘法 ，向量 叉乘向量 得到另一个向量 ，则 = × = 方向为右手直角坐标系
第16页，本讲稿共32页
几何意义
以 和 为边的平行四边形的面积
叉积定义为一个矩阵行列式
思考1：叉积何时小于0？何时大于0？又何时等于0？
思考2：对公共点P0而言，如何知道有向线段 在有向线段 的什么方向？
通过叉积可以知道
第17页，本讲稿共32页
确定两条线段是否相交
第一步：通过快速排斥实验来确定两条线段是否不相交；
第二步：在快速排斥实验判断有可能相交的前提下进行跨立实验，来确定两条线段是否相互跨立
确定任意一