第8章 数论算法及计算几何算法优秀PPT.ppt
《第8章 数论算法及计算几何算法优秀PPT.ppt》由会员分享,可在线阅读,更多相关《第8章 数论算法及计算几何算法优秀PPT.ppt(32页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第8章数论算法及计算几何算法现在学习的是第1页,共32页教学目标教学目标理解求最大公约数的算法掌握欧几里德公式的推广掌握求解同余方程的算法掌握运用中国剩余定理解决实际问题理解线段相交的概念掌握线段是否相交的判定算法理解凸包的概念及穷举搜索的解决方法掌握凸包问题及最接近点对问题的分治法现在学习的是第2页,共32页8.1最大公约数最大公约数定义定义1设a,b是整数,b0,如果存在整数c,使得a=bc成立则称a被b整除,a是b的倍数,b是a的约数(因数或除数),可记为b|a;如果不存在整数c使得abc成立,则称a不被b整除,记为ba。定理定理1(带余数除法)设a与b是两个整数,b0,则存在唯一的两个
2、整数q和r,使得a=bq+r,0r0)。现c筒装满水,问能否在c简中量出d升水(cd0)。若能,请列出一种方案。算法分析:量水过程实际上就是倒来倒去,每次倒的时候总有如下几个特点:总有一个筒中的水没有变动;不是一个筒被倒满就是另一个筒被倒光;c筒仅起中转作用。而本身容积除了必须足够装下a筒和b筒的全部水外,别无其它限制。通过上述分析知:问题实质上是将a筒倒满x次,b筒倒满y次,使得总结果有ax十byd(8-10)设a3,b7,c10,求x,y现在学习的是第12页,共32页8.3同余方程组同余方程组若数r同时满足n个同余方程:,则r称为这n个同余方程组成的同余方程组的解现在学习的是第13页,共3
3、2页定理对同余方程组记,其中,表示m1和m2的最小公倍数。若d(a1-a2),则此同余方程组无解;若d|(a1-a2),则此同余方程组有对模M的一类剩余解。中国剩余定理(即孙子定理)设是两两互质的正整数,记M=,则同余方程组现在学习的是第14页,共32页有对模M的唯一解其中证明(见板书)例:早在几千年前中国的一本孙子算经就已经提及这个问题的解法了,原文为:“今有物,不知其数,三三数之,剩二;五五数之,剩三;七七数之,剩二,问物几何?”答曰:“二十三”。现在学习的是第15页,共32页8.4线段相交线段相交线段性质有向线段P1为始点,P2为终点,长度如果P1(0,0),则记为无向线段为P1P2叉积
4、的概念叉积是一种向量乘法,向量叉乘向量得到另一个向量,则=方向为右手直角坐标系现在学习的是第16页,共32页几何意义以和为边的平行四边形的面积叉积定义为一个矩阵行列式思考1:叉积何时小于0?何时大于0?又何时等于0?思考2:对公共点P0而言,如何知道有向线段在有向线段的什么方向?通过叉积可以知道现在学习的是第17页,共32页确定两条线段是否相交第一步:通过快速排斥实验来确定两条线段是否不相交;第二步:在快速排斥实验判断有可能相交的前提下进行跨立实验,来确定两条线段是否相互跨立确定任意一对线段相交对应给定的一个线段集合,确定其中任意两条线段是否相交。该算法输入由若干条线段组成的集合,若这组线段中
5、存在任意一对线段相交,则返回true;否则,返回false两点假设(1)线段集合中的所有线段都不是竖直的;(2)未有三条输入线段相交于同一点的情形。现在学习的是第18页,共32页算法思想假设一条垂直扫描线沿X轴方向从左到右顺序移动、穿过已知的若干线段。移动过程中,每遇到一个线段端点,它就将穿过扫描线的所有线段放入一个动态数据结构中,并利用它们之间的关系进行排序,核查是否有相交点存在。该算法要求安排两个集合,一个是T序列,另一个是扫描线的一系列位置,即线段端点位置,并且要标记端点为线段的左端点还是线段的右端点。遇到左端点时将线段插入序列T中,并考察与其相邻的线段是否相交;遇到右端点时将线段从序列
6、T中删除,此时考察被删除线段的左右两条线段是否相交。现在学习的是第19页,共32页8.5凸包问题凸包问题给定一个点集SP0,P1,Pn-1,它的凸包是一个最小的凸多边形P,且满足S中的每个点或者在P的边界上或者在P的内部如果点集S是两个点的集合,显然它的凸包是连接这两个点的线段;如果S是由三个不共线的点组成的集合,那么凸包是以这三个点为顶点的三角形;如果三点共线,则凸包是以距离最远的两个点为端点的线段。对于更大的集合,在直观上,可以把S中的每个点看作订在地上的木桩,那么凸包就是将所有木桩围起来的一个拉紧的橡皮绳的形状,如图8-1所示。现在学习的是第20页,共32页8.5.1凸包问题的穷举搜索法
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第8章 数论算法及计算几何算法优秀PPT 数论 算法 计算 几何 优秀 PPT
限制150内