第八章 数论算法及计算几何算法
教学目标
理解求最大公约数的算法 掌握欧几里德公式的推广 掌握求解同余方程的算法
掌握运用中国剩余定理解决实际问题 理解线段相交的概念
掌握线段是否相交的判定算法
理解凸包的概念及穷举搜索的解决方法 掌握凸包问题及最接近点对问题的分治法
8.1最大公约数
★定义1 设a,b是整数,b≠0,如果存在整数c,使得a=bc成立.则称a被b整除,a是b的倍数,b是a的约数(因数或除数),可记为b|a;如果不存在整数c使得a=bc成立,则称a不被b整除,记为b。
★定理1(带余数除法) 设a与b是两个整数,b≠0,则存在唯一的两个整数q和r,使得a=bq+r,0≤r<|b|。(证明略)
★定义2 在定理1的表达式a=bq+r中,称q是a被b除的商,r是a被b除的余数。 最大公约数是指两个或两个以上整数的公共约数中最大者。任意给定两个整数,如何找出它们的最大公约数呢?下面介绍两种找最大公约数的方法。
8.1.1欧几里德算法
1.欧几里德定理
★定理2 任意给定两个整数a,b,不妨假设a≥b。它们的最大公约数用gcd(a,b)表示,则gcd(a,b)=gcd(b,a mod b) ,其中a mod b表示a被b除所得的余数。
证明:根据定理1,a可以表示成a=kb+r,k是整数,0≤r<|b|,则r=a mod b; 假设d是a,b的一个公约数,则d|a, d|b,而r=a-kb,因此d|r。由此可见,d是b和a mod b的公约数。
同理,假设d'是b和amodb的公约数,则d'|b, d'|r。又由于a=kb+r,故d'|a。因此d'也是a和b的公约数。故a和b的公约数与b和amodb的公约数是一样的,其最大公约数也必然相等,证毕。
欧几里德递归定义式如下:
ab 0
gcd(a,b)
gcd(b,amodb)b 0
2.欧几里德算法描述
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。数论算法及计算几何算法,凸包问题及最接近点对问题的分治法第八章 数论算法及计算几何算法 教学目标 ? ...
第8章 数论算法及计算几何算法_数学_自然科学_专业资料。第八章 数论算法及计算几何算法 教学目标 ? 理解求最大公约数的算法 ? 掌握欧几里德公式的推广 ? ...
第八章 数论算法及计算几何算法 8.5 凸包问题 1、问题提出 ? 给定一个点集S={P0,P1,…,Pn-1},它的凸包是一 个最小的凸多边形P,且满足S中的每个点...
数论和计算几何_数学_自然科学_专业资料。pascal数论和计算几何数论和计算几何 ... 第八章 数论算法及计算几... 28页 免费 数论计算 引言 57页 免费 计算与...
第八章 数论算法及计算几... 28页 免费 奥数几何,数论,行程专题 8页 7...快速幂是用来快速计算a^n mod p的一种方 法。 如果n是偶数则a^n=a^(n/...
离散数学--11.1-2初等数论 24页 免费 数论-第八章 14页 1财富值 108第八章数论及其猜想的意... 41页 1财富值 第八章 数论算法及计算几何... 暂无...
第八章 数论算法及计算几何... 第九章 NP完全理论1/2 相关文档推荐 第2章 贪心法 56页 5财富值 第2章 贪心法 暂无评价 42页 1财富值 第2章 贪心法 ...
[编辑本段] 算法分类 算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论 的算法、动态规划以及数值分析、加密算法、排序算法、检索...
三角形几何运算 7页 免费 第8章 数论算法及计算几何... 暂无评价 32页 免费 CAGD第八章曲线的几何处理... 5页 5财富值 计算几何 67页 免费喜欢此文档的...
224 第八章 数论算法及计算几何算法 ... 226 8.1 最大公约数......
热门文档