呵呵，出道题大家做，看谁的方法好。

tarkey

有两个整数，a，b。
写一个函数来计算a和b的最大公因数。

lobo

呵呵，这个以前在某论坛和人讨论过，先看看大家的答案再说：）
虽然是很简单的题目，但写法也是多样的。

nicememory

没考虑负数
int gcd(int a,int b)
{
     while(a!=b)
     {
        if(a==1||b==1)
            return 1;
        if(a>b)
            a-=b;
        else
            b-=a;   
        
                  
     }  
     return a;
         
}

tarkey

这个吊。。。-。-， 有数学证明吗？

lobo

用减法看上去效率高，其实不然，举个例子，求A除以B的余数，你会用：
return A%B 还是
while (A>B) A -= B; return A;
少数情况下，下面一种方法快，但多数情况下，下面一种方法就慢了，平均起来，肯定是%比减法快，不然%也没有存在的必要了，毕竟编译器不是吃素的。
所以3楼的：
        if(a>b)
            a-=b;
        else
            b-=a;
不如改成：
        if(a>b)
            a %= b;
        else
            b %= a;
试想，当a和b相差很大时，由减法改成%会减少很多循环次数，当a、b很接近时也是一样，例如a = 100，b = 99，先是a = 100-99 == 1,然后99-1，98－1...自己想象吧。

tarkey

有没有相关的数学模型呢？

Deen

这个问题好久了 ...

#define UINT unsigned int

UINT Get_Value(UINT a, UINT b)
{
    if (a < b)
    {
         swap(a, b); // c = a; a = b; b = c;
     }

    if (a % b)
   {
        return b;
    }
    else
    {
           UINT Mod = a % b;

           a = b; b = Mod;
               
           Mod = a % b;
                                
           if (Mod == 0) { return b; }
           else
           {
                 return Mod;
           }
     }
}

Deen

tarkey 你研究这个干什么 ？

不是在启发自己吧 ？

nicememory

另外一种写法:
int gcd(int a,int b)
{
       while(b)
       {
                   a%=b;
                   a^=b;
                   b^=a;
                   a^=b;
        }
        return a;
}

lobo

其实关键就是a、b的互换，这一次是a%b那下一次一定是b%a，那有什么办法可以减去这个互换的开销呢？其实3楼的if(a>b)就是一个方法，略去他那句
        if(a==1||b==1)
            return 1;
效率要比7楼的和9楼的高。
其实这个if判断也可以省去的，因为if的结果我们都是已知的，但直接去掉也不行，下面给出一种高效的：
int gcd(int a,int b)
{
       while(a%b && b%a) ;
        return a | b;
}
呵呵，简洁吧。