首页 / 算法 / 欧几里得算法及其扩展
欧几里得算法及其扩展
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了欧几里得算法及其扩展,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2490字,纯文字阅读大概需要4分钟。
内容图文
一、欧几里得算法
传统的求最大公约数的方法直接枚举,对于较大的数时间复杂度较高,不符合要求。欧几里得算法,又称辗转相除法,是求最大公约数的算法,可以有效提高算法效率。
辗转相除法基于原理:两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。例如,252和105的最大公约数是21( 252 = 21 × 12 ; 105 = 21 × 5 ),因为 252 ? 105 = 21 × (12 ? 5) = 147 ,所以147和105的最大公约数也是21(这只是基于此原理的举例)。
简述算法内容:基于上述原理,我们可以将两个数进行转化,将较大的数不断变小,直至这两个数中的其中一个变为0,那么剩下的那个不为0的数就是两数的最大公约数。
算法描述:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。
递归代码:1 int Gcd(int x,int y)//x要大于y 2 { 3 return y==0?x : Gcd(y, x%y); 4 }
形象点的递归代码:
1 int Gcd(int x,int y) 2 { 3 if(y==0) 4 return x; 5 return Gcd(y, x%y); 6 }
非递归代码:
1 int Gcd(int x,int y)//x要大于y 2 { 3 int tmp; 4 while(y) 5 { 6 tmp=x%y; 7 x=y; 8 y=tmp; 9 } 10 return x; 11 }
二、扩展欧几里得算法
1.定义:扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式a x + b y = gcd ( a , b ) .(贝祖等式也叫贝祖定理,即给定二个整数a、b,必存在整数x、y使得ax + by = gcd(a,b)) 。
2.具体说一下,由ax+by=gcd(a,b),可知,
当b=0的时候, gcd(a,b)=a,此时x=1,y=0为一组解。
当b!=0时,设ax1+by1 =gcd(a,b),由之前的辗转相除法可知 gcd(a,b)=gcd(b,a%b),
设bx2+(a%b)y2=gcd(b,a%b)=gcd(a,b), 则①bx2+(a%b)y2=ax1+by1
由之前的b=0时的式子已经知道了x2=1和y2=0,(假设a和a%b为最终状态),那么我们需要知道x1 , y1,这个可以在函数递归返回的时候得到,而现在我们手头做的是递推的到解。
式子可以化为a%b=a-(a/b)*b(注意,a/b是向下取整且优先级第一),将其带入①式,得到
b*x2+(a-(a/b)*b)*y2=ax1+by1
进而可以得到a*y2+b*y2=a*x1+b*y1,所以,在知道x2和y2 之后,可以推出②x1=y2 ,③y1=x2 - (a/b)*y2 ,逆向推导回去即可。
3.通解:式子ax+by=k*gcd(a,b)的通解(当k=1时就是上面的情况),设ax0+by0=gcd(a,b),则a(x0k)+b(y0k)=k*gcd(a,b),那么其通解为x=x0k+t*b/gcd(a,b) , y=y0k-t*gcd(a,b),t在计算中是可以消掉的
下面给出代码:
1 int ex_gcd(int a,int b,int &x,int &y) 2 { 3 if(b==0) 4 { 5 x=1; 6 y=0; 7 return a; 8 } 9 int r=ex_gcd(b,a%b,x,y); 10 int tmp=x; 11 x=y;//这是②式 12 y=tmp-(a/b)*y;//这是③式 13 return r; 14 }
内容总结
以上是互联网集市为您收集整理的欧几里得算法及其扩展全部内容,希望文章能够帮你解决欧几里得算法及其扩展所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。