第八章 数论算法及计算几何算法 233
Mix 1(modmi) (i=1,2,…,n)都有解,于是必存在M'i,使得MiM'i 1(mod mi),又因
M miMi,mj|Mi(i j),所以对模mi(i 1,2, ,n)有x0 MiMiai ai(mod mi),
'
1 i n。故式(8-11)是式(8-12)的解。
若x1,x2是式(8-11)的任意两个解,则x1 x2(mod mi),i=1,2,…,n,因gcd(mi,mj)=1 (i j)。故x1 x2(mod m1m2…mn),即x1 x2(mod M)。因此,式(8-11)是式(8-12)的唯一解。
由中国剩余定理可设计如下求同余方程组的算法:
int tyz() {
int i, M=1, Mi', y, sum=0, Mi; for (i=0; i<n; i++) M *= m[i];//计算M for (i=0; i<n; i++) {
Mi=M/m[i];//计算Mi
exgcd(Mi, m[i], Mi', y);//计算Mi' sum += a[i]*Mi*Mi';
}
return (sum+M)%M; //计算同余方程组的解。 }
【例8-4】早在几千年前中国的一本《孙子算经》就已经提及这个问题的解法了,原文为:“今有物,不知其数,三三数之,剩二;五五数之,剩三;七七数之,剩二,问物几何?”
答曰:“二十三”。
解:设物有x个,则有一次同余方程组:
x 2(mod3)
x 3(mod5) x 2(mod7)
根据孙子定理可知:M=105,M1=35,M2=21,M3=15。 由35M1' 1(mod 3)得M1'=-1(mod 3) 由21M2'=1(mod 5)得M2'=1(mod 5) 由15M3'=1(mod 7)得M3'=1(mod 7)
x MiMi'ai(modM) (35*( 1)*2 21*1*3 15*1*2)(mod105) 23(mod105)
i 1
3
8.4线段相交
1.线段性质
从平面上取一固定点Pl(P1=(x1,y1)),从P1出发向某点P2(P2=(x2,y2))引一条线段,该
第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 最大公约数......
热门文档