给定两个正整数，求最大公约数。相信这是每个??写代码的同学都曾经遇到过的一个练习。当然，有很多解决方案。让我们给出一个没有任何算法处理的第一个程序：publicstaticintgetResult(inta,intb){intmax=(a>b)?a:b;结果=0；for(inti=1;i=y>0)，这样的递归操作，如f(42,30)=f(30,12)=f(12,6)=f(6,0)=6；这样直接减少了很多计算量。代码附在下面：intresult=((y==0)?x:gcd(y,x%y));返回结果；}方案二：虽然方案一很好的解决了求公约数的问题，但是算法中包含了除法，在计算机中除法的开销非常大。不能用除法吗？可以这样认为，如果一个数可以被x,y四舍五入，那么它也一定可以被x-y,y四舍五入，即一个数可以被x,y四舍五入是充分必要条件对于要由x-y、y四舍五入的数字。然后f(x,y)=f(x-y,y);这样计算的话，大整数之间的取模运算就可以转化为大整数之间的减法运算。由于f(x,y)=f(y,x)，为了避免求正数和负数的最大公约数，需要灵活使用f(x,y)=f(y,x),迭代进行，直到一侧为0；例如：f(42,30)=f(30,12)=f(18,12)=f(12,6)=f(6,6)=f(6,0)=6;与上面的方法，这个操作优化了大数据取模的问题，但是操作次数会增加，代码如下：privatestaticintgcd(intx,inty){if(y==0){returnx;}if(x>1,y>>1)<<1;}else{//x为偶数，y为奇数，f(x,y)=f(x/2,y)returngcd(x>>1,y);}}else{if(isEven(y)){//x为奇数，y为偶数，f(x,y)=2*f(x,y/2)returngcd(x,y>>1);}else{//x,y都是奇数，f(x,y)=f(x-y,y)returngcd(x-y,y);}}}publicstaticbooleanisEven(intx){返回(x%2==0)?true:false;}我以前从来没有想过这样的事情。第一次看到算法的时候，顿时觉得自己高大上了。但确实，看到以前常用的公约数问题如何用这种方式求解，确实是一个亮点。希望大家多提意见~原文链接：http://my.oschina.net/u/858241/blog/209774
