第八章 数论算法及计算几何算法 227
(1)递归算法描述如下:
int gcd(int a, int b) {
if(b==0) return a; return gcd(b, a % b); }
(2)迭代算法描述如下:
int gcd(int a, int b) {
while(b!=0) {
int r=b; b=a % b; a=r; } return a; }
3.欧几里德递归公式的推广
扩展欧几里德算法是用来解决“已知a, b求解一组x,y使得ax+by=gcd(a, b) ”问题,常用在一次同余方程及方程组的求解中。
令gcd(a, b)=d,则ax+by=d;gcd(b,amodb)=d (8-1)
(1)当b=0时,则gcd(a,b)=a;ax+by=a,即ax=a,则x=1,y取任意实数。简单起见,算法取y=0;
(2)当b≠0时,令a'=b,b'=a mod b,则gcd(a', b')=d,a'x'+b'y'=d。 由于b' =amodb=a b,则a'x'+b'y'=bx'+(a b)y'=ay' +b(x' - y')=d (8-2)
bbb
让式(8-1)和式(8-2)对应项相等,则x=y',y= x' - y'。
b4.欧几里德公式的推广算法描述:
int exgcd(int a, int b, int &x, int &y) {
if(b==0) {
x=1; y=0; return a; }
int r=exgcd(b, a % b, x, y); int t=x;x=y; y=t-a / b * y; return r; }
a a a
a
第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 最大公约数......
热门文档