欢迎大家来到IT世界,在知识的湖畔探索吧!

利用欧拉的辗转相除法来求最大公约数可以很好地理解变量的迭代关系。而对照一下递归算法，可以更好地理解两个递归函数之间参数的迭代关系：

int gcd(int a,int b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
    //return b?gcd(b,a%b):a;
}
int gcd2(int a, int b)
{
    while(b != 0)
    {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

相对于非递归函数的写法，为什么递归函数不需要使用一个临时变量？是因为递归函数的参数值位于各自的栈帧。参数传值时没有彼此的耦合关系。

《九章算术》中的辗转相减法：

欢迎大家来到IT世界,在知识的湖畔探索吧!int gcd3(int a, int b) // 《九章》中的辗转相减法
{
    int t = a;
    a = a>b?a:b;
    b = t<b?t:b;
    while(b != 0)
    {
        t = a - b;
        a = t>b?t:b;
        b = t<b?t:b;
    }
    return a;
}

对照一下：

最大公约数也可以返回b，但要在b=0前提示返回，终止条件就是a%b!=0。

ibt gcd(int a, int b)
{
    int r;
    if (a<b){r=a;a=b;b=r;}
    while(r=a%b)  // 求a，b的最大公约数
    {
        a=b;
        b=r;
    }
    return b;
}

形象化解释

下面我们对上面的过程进行一个表形象地讲解，实际上这也是教材里面的讲解方式，我只是照搬过来，增加一下自己的理解罢了。我们来通过一个例子来讲解：

假如我们有一块 1680 米 * 640 米 的土地，我们希望将其分成若干正方形的土地，且我们想让正方形土地的边长尽可能大，我们应该如何设计算法呢？

实际上这正是一个最大公约数的应用场景，我们的目标就是求解 1680 和 640 的最大公约数。

将 1680 米 * 640 米 的土地分割，相当于对将 400 米 * 640 米 的土地进行分割。 为什么呢？ 假如 400 米 * 640 米分割的正方形边长为 x，那么有 640 % x == 0，那么肯定也满足剩下的两块 640 米 * 640 米的。

我们不断进行上面的分割：

直到边长为 80，没有必要进行下去了。

－End－