1 / 32
文档名称:

第8章 数论算法及计算几何算法.ppt

格式:ppt   大小:1,443KB   页数:32页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

第8章 数论算法及计算几何算法.ppt

上传人:文库新人 2022/2/2 文件大小:1.41 MB

下载得到文件列表

第8章 数论算法及计算几何算法.ppt

相关文档

文档介绍

文档介绍:第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页
确定两条线段是否相交
第一步:通过快速排斥实验来确定两条线段是否不相交;
第二步:在快速排斥实验判断有可能相交的前提下进行跨立实验,来确定两条线段是否相互跨立
确定任意一