第八章 数论算法及计算几何算法 231
ax'=d-my' (8-8)
式(8-8)两边同时模m得:
ax' d(mod m) (8-9)
可见,x'是一次同余方程(8-9)的解。 步骤3-2:根据x'求x0。具体方法:
b
,则根据同余式的性质得:a(px') dp(mod m)即:d
b
a(px') b(mod m)。因此,x0=px'=x'(mod m)。
d
im
步骤4:根据(8-7)式可得(8-5)式的其它d-1个解为xi (x0 m),i=1,2,…d-1。
d
由于db,设p 算法结束。
5.算法描述
bool ty(int a,int b,int m,int *ax) {
int x=0,y=0; int d=exgcd(a,m,x,y); int p=b/d,q=m/d; ax=new int[d]; if(b mod d==0)
ax[0]=p*x; else return 0; for(int i=1;i<d;i++) ax[i]=ax[0]+i*q; return 1; }
【例8-3】量水
有三个分别装有a升水,b升水和c升水的量筒(gcd(a,b)=1,c>b>a>0)。现c筒装满水,问能否在c简中量出d升水(c>d>0)。若能,请列出一种方案。
算法分析:
量水过程实际上就是倒来倒去,每次倒的时候总有如下几个特点: (1)总有一个筒中的水没有变动;
(2)不是一个筒被倒满就是另一个筒被倒光;
(3)c简仅起中转作用。而本身容积除了必须足够装下a筒和b简的全部水外,别无其它限制。
通过上述分析知:问题实质上是将a筒倒满x次,b简倒满y次,使得总结果有 ax十by=d (8-10)
式(8-10)中的x和y为整数,即可以是正整数(表示该筒(a或b)被c筒水倒满的次数)也可以是负整数(表示该筒(a或b)被倒满后倒入c简的次数)。
将式(8-10)化为ax=-by十d,方程两边对模b得ax d(mod b),则问题变成了求解一次同余方程的问题。解x的个数d即为方案总数。其中xi(1 i d)表示第i种方案中a筒倒满的次数。将xi代入axi十byi=d后求出的yi表木b筒倒满的次数。
第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 最大公约数......
热门文档