如何证明这种欧几里得(最大公约数)算法的正确性?

#include<stdio.h>
unsigned int gcd(unsigned int M, unsigned int N)
{
    int rem;
    if(M < N)/*exchange value to=>M>N*/
    {
        int temp = M;
        M = N;
        N = temp;
    }
    
    while(N > 0)
    {
        rem = M % N;
        M = N;
        N = rem;
    }
    return M;
}
int main()
{
    printf("%d\n", gcd(25, 45));
    return 0;
}

这种算法通过不断的求余数,直到最后结果为0,倒数第二个数就是最大公因数。这个算法很高效,但是自己怎么能证明最后非0的那个余数就一定是正确答案昵,作为数学渣有点困扰。

阅读 8.7k
3 个回答

手打公式太繁,改用拍照。

Image

GreatestCommonDivisor1.png

借张图)两个数都是由最大公约数堆出来的,所以相减、取模最大公约数肯定是不变的。(直观解释)

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题
宣传栏