编程之美_007最大公约数问题
[java]// 最大公约数问题
public class Test
{
public static void main(String[] args)
{
System.out.println(isEven(156465489));
System.out.println("1.辗转相除法:" + commonDivisor1(56, 36));
System.out.println("2.迭代相减法:" + commonDivisor2(56, 36));
System.out.println("3.迭代相减法和辗转相除法结合:" + commonDivisor3(56, 36));
} www.zzzyk.com
// 1.辗转相除法
// f(x,y)=f(y,y%x)(y>0)
// 性能瓶颈：取模运算开销较大
static int commonDivisor1(int x, int y)
{
return (y == 0) ? x : commonDivisor1(y, x % y);
}
// 2.迭代相减法
// f(x,y)=f(x-y,y)(x>y
// 性能瓶颈：迭代次数增多
static int commonDivisor2(int x, int y)
{
if (x < y)
{
return commonDivisor2(y, x);
}
if (y == 0)
{
return x;
}
else
{
return commonDivisor2(x - y, y);
}
}
// 3.迭代相减法和辗转相除法结合解最大公约数问题
static int commonDivisor3(int x, int y)
{
if (x < y)
{
return commonDivisor3(y, x);
}
if (y == 0)
{
return x;
}
else
{
// x为偶数
if (isEven(x))
{
if (isEven(y))
{
return commonDivisor3(x >> 1, y >> 1) << 1;// x偶数,y偶数
}
else
{
return commonDivisor3(x >> 1, y);// x偶数,y奇数
}
}
// x为奇数
else
{
if (isEven(y))
{
return commonDivisor3(x, y >> 1);// x奇数,y偶数
}
else
{
return commonDivisor3(x - y, y);// x奇数,y奇数
}
}
}
}
/**
* 判断一个数是否是偶数
* @param x 判断的数字
* @return true 偶数; false 奇数
*/
static boolean isEven(int x)
{
return (x & 1) == 0 ? true : false;
}
}
上一篇：http://www.zzzyk.com/kf/201301/183227.html
上一篇：http://www.zzzyk.com/kf/201301/183227.html
补充：软件开发 , Java ,
