利用辗转相除法求最大公约数:
#include <stdio.h> int hcf(int a,int b) { int r=0; while(b!=0) { r=a%b; a=b; b=r; } return(a); } int lcd(int u,int v,int h) { return(u*v/h); } int main() { int u,v,h,l; scanf("%d%d",&u,&v); h=hcf(u,v); printf("H.C.F=%d\n",h); l=lcd(u,v,h); printf("L.C.D=%d\n",l); system("pause"); }
减少代码的冗余:
int hcf(int x,int y) { return (!y) ? x : GCD(y,x%y); }
但是对于大整数会出现一些问题,换用位运算即 f(x,y)=f(x-y,y);深入考虑一下发现在算法运行的过程可能会出现x<y的情况,这时候要交换x和y,但是结果不受影响。
BigInt hcf(BigInt x,BigInt y) { if(x < y) return hcf(y,x); return (!y) ? x : hcf(x-y,y); }
代码中用到的BigInt是大整数类,可以存储成百上千位的整数,这个算法引入了另外一个问题,那就是当x和y相差很多时,算法的迭代次数会过高,导致了算法的效率较低,例如计算GCD(100000000000001,1)。这种情况确实存在啊,于是我们要考虑其他的优化了。
每种情况都有自己的适应场景,下面对以上不适合场景做一些改变:
(1)如果y=k*y1,x=k*x1.那么有f(x,y)=k*f(x1,y1)
(2)如果x=p*x2,p为素数,并且y%p != 0,那么f(x,y) = f(p*x2,y) = f(x2,y)
于是我们得到下面的解决方法:
将p = 2,
若x,y均为偶数,f(x,y) = 2*f(x/2,y/2) = 2*f(x>>1,y>>1);
若x是偶数,y是奇数,f(x,y) = f(x/2,y) = f(x>>1,y);
若x是奇数,y偶数,f(x,y) = f(x,y/2) = f(x,y>>1);
若x和y均为奇数,f(x,y) = f(y,x-y)。这时x-y一定是偶数,下一步一定会除以2。
因此,可以看出这种算法的时间复杂度是O(log2(max(x,y))。
BigInt hcf(BigInt x,BigInt y) { if(x < y) return GCD(y,x); if(y == 0) return x; else { if(IsEven(x)) { if(IsEven(y)) return (hcf(x>>1,y>>1)<<1); return hcf(x>>!,y); } else { if(IsEven(y)) return hcf(x,y>>1); return hcf(y,x-y) } } }
相关推荐
最大公约数与最小公倍数的求法。简单明了,通俗易懂,是不错的算法
实现求两个整数的最大公约数和最小公倍数。求两个数的最大公约数和最小公倍数的方法有很多种,常用的有欧几里得算法和Stein算法。
一个简单的最大公约数与最小公倍数程序,希望会对大家有帮助。
关于如何求最大公约数和最小公倍数的c语言程序
最大公因数与最小公倍数
最大公约数、最小公倍数 * 最大公约数(a,b) * 12的因数:1、2、3、4、6、12 * 18的因数:1、2、3、6、9、18 * 12和18的最大公约数... * 两个数的积等于这两个数的的最大公约数与最小公倍数的积。即(a,b)*[a,b]=a*b
python 输入两个正整数计算最大公约数和最小公倍数 示例
用LabVIEW求最大公约数和最小公倍数。可以自行选择数据。
1.最小公倍数、最大公约数1.最小公倍数、最大公约数1.最小公倍数、最大公约数
java 最大公约数与最小公倍数代码 使用的for 方法
7-3 最大公约数和最小公倍数
计算最大公约数和最小公倍数的常见算法计算最大公约数和最小公倍数的常见算法计算最大公约数和最小公倍数的常见算法计算最大公约数和最小公倍数的常见算法计算最大公约数和最小公倍数的常见算法计算最大公约数和最小...
Java求最大公约数、最小公倍数,输入两个正整数m和n,求其最大公约数和最小公倍数。最小公倍数可由原数除以最大公约数计算得到,这里使用了辗除法。
python求最大公约数和最小公倍数 #辗转相除法 def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input()....
基于FPGA开发板的两位数求最大公约数和最小公倍数的设计,该设计中利用辗转相减法求得公约数与公倍数,且两个数的数值可通过按键修改,设计灵活可靠。该设计基于vivado开发,并带有testbench文件,方便仿真学习。
用c语言编写输入两个数,求其最大公约数与最小公倍数
求最大公约数和最小公倍数. 相信你们会找到的。
C++编写最大公约数与最小公倍数,使用函数的调用,可以有其他程序衔接调用