c语言碾转相除法,从高中碾转相除法、更相减损术算法谈起

编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」

先问你们一个小学问题：「如何求两个整数的最大公约数?」

曾经见过不少的算法题，发现有的并不在数据结构和算法大纲中，而是来源于高中数学。

高中数学在必修三中，有一个非常重要的知识点，叫做「碾转相除法、更相减损术」。

辗转相除法，又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法，其可追溯至公元前300年前。

在古代，有一个比较出名的数学家，叫做「刘徽」。而更相减损术是我国数学家刘徽的专著《九章算术》中记载的.

碾转相除法

辗转相除是求最大公约数的一种算法。给两个数,我们可以把它组成数对(a,b)辗转相除法基于如下原理：「两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。」

求a和b的最大公约数，就用ab中较小的数去除另一个数，这个时候会有一个余数，当余数是0的时候，那个较小的数就是最大公约数。

若余数不是0，那么我们用这个余数来替换那个比较大的数，然后以此类推，直到算出最大公约数。

设两数为a,b（a>=b）求a,b两数的最大公约数的步骤为：

用a除以b，a%b=r(r>=0)

如果r=0，则（a,b）=b

如果r≠0，用b除以r，依此循环，直到r=0结束

算法的流程图（摘自百度百科）

代码如下：

#include<stdio.h>
int main()
{
    int a,b;
    printf("请输入两数：");
    scanf("%d%d",&a,&b);
    int t;
    if(a<b)
    {
        t=a;
        a=b;
        b=t;
    }
    int r;
    r=a%b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    printf("最大公约数是%d\n",b);
    return 0;
}

以上内容综合两篇文章编写，原文如下：

原文链接：https://blog.csdn.net/weixin_43405277/article/details/86631603

(16条消息) c语言碾转相除法,从高中碾转相除法、更相减损术算法谈起_weixin_39769627的博客-CSDN博客 https://blog.csdn.net/weixin_39769627/article/details/117054725?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-117054725-blog-86631603.pc_relevant_recovery_v2&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1-117054725-blog-86631603.pc_relevant_recovery_v2&utm_relevant_index=1