问大家一个C语言问题，关于求最简分数

Question

#include <stdio.h>
int Gcd(int a, int b);
int main(void)
{
    int m, n, f;
    scanf("%d,%d", &m, &n);
    f = Gcd(m, n);
    if (f != -1)
    {
        printf("%d/%d", m / f, n / f);
    }
    else
    {
        printf("Input error!\n");
    }
    return 0;
}

int Gcd(int a, int b)
{
    int r;

    for(int i=1;i<=b;i++)
    {
        if(a%i==0 && b%i==0)
        r=i;
    }
    if(a>=1 && b<=10000)
    return r;
    else 
    return -1;
    
    
}

为什么会输出0/0啊？

Answer 1

引自免费微信小程序：皆我百晓生

从你提供的代码来看，问题出在Gcd函数的实现上。当前的Gcd函数使用了一个循环来寻找两个数的最大公约数，但是这个方法效率低下且存在逻辑错误。在循环结束后，并没有返回最大公约数r，而是在之后的条件判断中才返回值，这导致了当a和b不满足a>=1 && b<=10000条件时，函数会提前返回-1，即使之前已经找到了最大公约数。

此外，你的Gcd函数中的循环逻辑也有问题。它仅仅在每次i满足a%i==0 && b%i==0时更新r，但并没有保证r是最大的公约数。实际上，在循环结束时，r可能只等于其中一个较小的公约数。

为了解决这个问题，你可以使用更高效的算法来计算最大公约数，例如欧几里得算法。以下是修改后的代码：

#include <stdio.h>

int Gcd(int a, int b);

int main(void)
{
    int m, n, f;
    scanf("%d,%d", &m, &n);
    f = Gcd(m, n);
    if (f != -1)
    {
        printf("%d/%d", m / f, n / f);
    }
    else
    {
        printf("Input error!\n");
    }
    return 0;
}

// 使用欧几里得算法计算最大公约数
int Gcd(int a, int b)
{
    while(b != 0)
    {
        int temp = b;
        b = a % b;
        a = temp;
    }
    // 如果a或b小于1或者大于10000，则返回-1表示输入错误
    if(a < 1 || a > 10000 || b < 1 || b > 10000)
        return -1;
    return a;
}

在这个版本的Gcd函数中，我们使用了欧几里得算法，该算法基于这样一个事实：gcd(a, b) == gcd(b, a%b)。当b变为0时，a就是最大公约数。同时，我们在函数开始处添加了一个检查，确保a和b都在指定的范围内，否则返回-1表示输入错误。这样修改后，你的程序应该能正确地输出最简分数或输入错误提示。