the greatest common dividor(两个数的最大公约数)

综述：

    今天看了计算机编程艺术，第一张是关于最大公约数的，基本的算法思想是求m，n的最大公约数，我们假设m = tn + x；我们证明m，n的最大公约数，就是n与x的最大公约数。因为m能被k整除，n能被k整除，所以m/k = （tn + k）/k = tn/k + x/k, x必须也能被k整除。算法如下：

unsigned int greatest_common_dividor(unsigned int m,unsigned int n)
{
    unsigned int r;
    while(true)
    {
        r = m % n;
        if(r == 0)
            return n;
        m = n;
        n = r;
    }
}

       我们可以看到从第一次开始不管m 〉n或者n〉m，从第二次开始总是m〉n。但是有两次赋值。所以能不能去掉这两次赋值呢。所以算法的魅力就在这里，我们看能不能把r去掉，只留m,n呢，我们知道m，n肯定最后只需要一个，其中较大的会被删掉。
        我们假设m〉n，此时我们可以让m=m%n，赋值之后此时m为较小的了，在下此迭代的时候，就会出现死循环，因为我们只能让m〉n才能使其能够正确运行。
        所以我们接下来令n=n%m就可以保证，n始终是较小的。又不会浪费循环次数。所以算法是

unsigned int greatest_common_dividor(unsigned int m,unsigned int n)
{
    while(true)
    {
        m = m % n;
        if(0 == m)
            return n;
        n = n % m
        if(0 == n)
            return m;
    }
}

不禁感叹，没有想不到，只有做不到。算法真的太神秘了。