来源:编程之美2.7
问题:求两数的最大公约数
//求两个数的最大公约数
public class GCD2_7 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int x=4272;
int y=25472;
System.out.println(gcd1(x,y));
System.out.println(gcd2(x,y));
System.out.println(gcd3(x,y));
}
//方法一,辗转相除法 f(x,y)=f(y,x%y),缺点,对于大整数取余运算开销会很大
public static int gcd1(int x,int y){
return (y>0)?gcd1(y,x%y):x;
}
//方法二,f(x,y)=f(x-y,y)(x>y) 缺点,迭代次数会比较多。如x远大于y时
public static int gcd2(int x,int y){
if(x<y)return gcd2(y,x);
if(y==0)return x;
return gcd2(x-y,y);
}
//方法三,结合方法二,主要是减少迭代次数
public static int gcd3(int x,int y){
if(x<y)return gcd3(y,x);
if(y==0)return x;
else{
if(isEven(x)){
if(isEven(y))return(gcd3(x>>1,y>>1)<<1);
else return(gcd3(x>>1,y));
}else{
if(isEven(y))return gcd3(x,y>>1);
else return gcd3(y,x-y);
}
}
}
//判断一个数是否为偶数
private static boolean isEven(int x) {
return (x&1)==0;
}
}
分享到:
相关推荐
求两数最大公约数求两数最大公约数求两数最大公约数
是用vb做的,很简单的一个两数求公约数
用碾压法求出两个数的最大公因数,然后将剩下的分子连乘再乘以最大公因数即可获得最小公倍数
C语言求两个数最大公约数 用C语言 求两个数最大公约数 求两个数最大公约数 求两个数最大公约数
用JAVA写了个关于两个数最大公约数最小公倍数的程序..不晓得质量如何import java.util.*; public class dd { public static void main(String args[]){ Scanner scanner; scanner=new Scanner(System.in); int m...
四年级数学下册第五单元分数的意义和性质5.8求两数最大公因数的方法课时练冀教版
求最大公约数和最小公倍数. 相信你们会找到的。
主要介绍了Python基于递归和非递归算法求两个数最大公约数、最小公倍数,涉及Python递归算法、流程循环控制进行数值运算相关操作技巧,需要的朋友可以参考下
C语言编程实现求两个数的最大公约数和最小公倍数C语言编程实现求两个数的最大公约数和最小公倍数C语言编程实现求两个数的最大公约数和最小公倍数C语言编程实现求两个数的最大公约数和最小公倍数C语言编程实现求两个...
Java求最大公约数、最小公倍数,输入两个正整数m和n,求其最大公约数和最小公倍数。最小公倍数可由原数除以最大公约数计算得到,这里使用了辗除法。
基于FPGA开发板的两位数求最大公约数和最小公倍数的设计,该设计中利用辗转相减法求得公约数与公倍数,且两个数的数值可通过按键修改,设计灵活可靠。该设计基于vivado开发,并带有testbench文件,方便仿真学习。
VB 求多个数的最大公约数,这应该是个比较简单的数学算法例子,求指定多个数的最大公约数,源码中请详细代码。部分代码如下: Private Function big(ByVal m%, ByVal n%) As Integer '自定义函数 If m Do r...
C语言编程练习,需要使用手机APP:C4droid打开
包含两个算法,一个为辗转相除法,一个为连续整数检测法。而且算法中加入计数法对比两种算法的时间复杂度。
用 Java实现 输入两个数 求两个数的最大公约数,如何使用java语言求两个数的最大公约数
求两个数最大公约数,利用欧几里德算法,辗转相除法。详细内容看资料,留作备份。
对输入1-100内的两个整数,求其最大公约数,输入一个0-500的整数,判断其能否被3,5,7整除,并输入下列信息之一: (1) 能够同时被3,5,7整除 (2) 能够同时被其中两个数整除(给出这两个数) 进行白盒测试
在算法课程中用三种算法编程计算两个数的最大公约数
c代码-求两数最大公约数
def gcd(a,b): #最大公约数函数,且最小公倍数 = 两个数相乘 / 最大公约数 if b == 0: return a else: return gcd(b,a%b) print("请输入两个数:") j,k = input().split() #消除空格,但不能直接int(input()....