51Nod－1011－最大公约数GCD

输入2个正整数A，B，求A与B的最大公约数。
Input
2个数A,B，中间用空格隔开。(1<= A,B <= 10^9)
Output
输出A与B的最大公约数。
Input示例
30 105
Output示例
15

对于这道题，要说的就是一个辗转相除法，也是欧几里得定理的应用，算法有些难于理解，需要数学很好才能理解，算法的实现上却是十分的简单，可以用递归来实现，当然，也可以用迭代来实现。代码如下（C）：

#include <stdio.h>

long gcd(long a, long b)
{
    if (!b)
    {
        return a;
    }
    else
    {
        return gcd(b, a % b);
    }
    return 0;
}

int main(int argc, const char * argv[])
{
    long A, B;
    scanf("%ld %ld", &A, &B);
    printf("%ld\n", gcd(A, B));
    return 0;
}

上面的是递归实现的过程，用迭代实现也很容易，如下（C）：

int gcd(int a, int b)
{
        int c = a % b;
        while(c)
        {
                a = b;
                b = c;
                c = a % b;
        }
        return b;
}

都是几行代码即可以实现的，其实不用强行理解，自己代入数据推算几遍即可，多实现几次，就可以记住了，挺好用的一个方法！