【C语言】:输入两个正整数并找出它们的最大公约数减一比较法(当然这是我自己命名的hhh~)

66 阅读 0 评论 44 点赞

我是靠谱客的博主犹豫乐曲，最近开发中收集的这篇文章主要介绍【C语言】:输入两个正整数并找出它们的最大公约数减一比较法(当然这是我自己命名的hhh~)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

*********************************************************************************

导言：本人也是一位小白，有错误的地方请各位大佬指出，我便修改，这是我的第一篇博客写得不好请见谅。

下面介绍两种方法->

*********************************************************************************

- 减一比较法(当然这是我自己命名的hhh~)

代码如下：

#include <stdio.h>
#include <stdlib.h>//system("pause");的头文件

 int main ()
{
    int i = 0, j = 0;
    int temp = 0;
    printf("请输入两个正整数:> ");
    scanf("%d,%d",&i,&j);
        if(i > j)
    {
        temp = j;
    }
        else
    {
        temp = i;
    }

        for(temp; temp>0; temp--)
    {
        if(((i % temp) == 0) && ((j % temp) ==0))
        {
            printf("最大公约数是:%dn",temp);
            break;
        }
    }
    system("pause");//卡住生成的窗口方便观察结果
    return 0;
}

此方法的原理：将输入的两个数中较小的一个数给到一个中间变量用作for循环，以此来自减，在减的过程中会把这个数拿给输入时的两个数进行取余运算，若输入时的数均取余得到0就说明此时的中间变量的值就是输入的两个数的最大公约数。(因为较小的那个数自减的话比较大的那个数提高了效率，最大公约数顾名思义是输入两个正整数均所能整除的最大数)

当然这样的代码很是繁琐，看起来一大堆，所以为大家准备了第二种方法。

第二种方法也是大家上学时学过的“欧几里得算法”也就是辗转相除法，这属于算法的一种了。

先解释一下原理吧：

辗转相除法原理：先输入a和b进行取余(a%b,不管先后顺序)，若为0则说明a和b的最大公约数为b；若不为0则继续把b的值赋值给a，把前面取余得到的数赋值给b，然后继续取余判断a和b(a%b,不管先后顺序)是否等于0，若为0则说明最大公约数就是b的值，若不为0则继续把b的值赋值给a，把前面取余的数赋值给b，然后继续判断a和b取余(a%b,不管先后顺序)看是否等于0，如此循环。直到a%b==0了就说明b为a与b之间的最大公约数。

前面说到”减一法“的代码比较繁琐而这里却更繁琐，这里时为了大家更好的理解，下面会有优化的代码的，请各位看官稍安勿躁哦！

代码如下：

#include <stdio.h>
#include <stdlib.h>//system("pause");的头文件

 int main ()
{
    int i = 0, j = 0;
    int min = 0;
    int max =0;
    printf("请输入两个正整数:> ");
    scanf("%d,%d",&i,&j);
    if(i > j)
    {
        min = j;
        max = i;
    }
    else
    {
        min = i;
        max = j;
    }
    while(1)
    {
        if((max % min) == 0)
        {
            printf("最大公约数是:>%dn",min);
            break;
        }
        else
        {
            int num = min;
            min = max % min;
            max = num;
        }
    }
    system("pause");//卡住生成的窗口方便观察结果
    return 0;
}

注意：辗转相除法不需要把更大的数放前面，因为该方法具备“自动”把大的数换到前面去。

既然说到了可以不论顺序，所以我们吧这算法优化一下

#include <stdio.h>
#include <stdlib.h>//system("pause");的头文件

 int main ()
{
    int i = 0, j = 0;
    int num =0;
    printf("请输入两个正整数:> ");
    scanf("%d,%d",&i,&j);
    while(num=(i%j))
    {
        i = j;
        j = num;
    }
    printf("最大公约数是:%dn",j);
    system("pause");//卡住生成的窗口方便观察结果
    return 0;
}

这里就很简洁啦，相信大家也理解得差不多了吧！！！

我把代码运行输出一下吧！