2

我正在为 Coursera 课程做作业，要求我计算两个数字的最小公倍数，其中任何一个都不大于 2 * 10 ^ 9。我正在用 C 语言编写它，并且正在运行我的代码编号为 226553150 和 1023473145 的测试用例。答案是 46374212988031350，但我得到的是 46374212988031344，相差 6！

我已经用 Python 编写了一个正确的解决方案，它使用的方法与我在下面发布的方法基本相同，但数值精度的细节显然已经为我处理好了。我将此发布到 SO 以了解 C 中的浮点精度，因为我在互联网上看到的大多数问题以及关于 LCM 的 SO 仅涉及整数。

这是我正在编译的代码gcc -pipe -O2 -std=c11 lcm.c：

#include <stdio.h>
#include <math.h>

double gcd(double a, double b) {
    if (b == 0) {
        return a;
    }

    return gcd(b, fmod(a,b));
}

double lcm(double a, double b) {
    return (a * b) / gcd(a,b);
}

int main() {

    double a;
    double b;

    scanf("%lf %lf", &a, &b);

    printf("%.0lf\n", lcm(a,b));

    return 0;
}
4

2 回答 2

3

46374212988031350可以用 a 表示的最接近的数字double是46374212988031352(off by 2)。您可以使用最直接的计算来测试它。

#include <stdio.h>

int main() {

   // The gcd of 226553150 and 1023473145 is 5
   double a = 226553150;
   double b = 1023473145;
   double c = b/5;

   double lcm = a*c;

   printf("lcm: %.0lf\n", lcm);

   return 0;
}

输出：

lcm: 46374212988031352

您通过计算使事情变得更糟(a * b)/gcd(a, b)。可以用浮点数表示的最接近231871064940156750,的数字是. 换句话说，你会因为先计算而失去更多的准确性。(a*b)231871064940156736(a*b)

您尚未发布用于执行相同计算的 Python 代码。我猜 Python 正在对数字使用整数类型。如果我使用：

a = 226553150;
b = 1023473145;
c = b/5;

lcm = a*c

print("lcm:", lcm)

我得到输出：

('lcm:', 46374212988031350)

a但是，如果我对and使用浮点文字b，我会得到不同的输出：

a = 226553150.0;
b = 1023473145.0;
c = b/5;

lcm = a*c

print("lcm:", "%18.0lf" % lcm)

输出：

('lcm:', ' 46374212988031352')

总之，您在 C 程序和 Python 程序之间看到的差异是由于使用了浮点类型和整数类型。如果你使用longorlong long代替double，你应该得到与 Python 程序相同的输出，如邓海军的回答所示。

于 2016-04-11T05:41:18.103 回答
1

我怀疑你为什么使用浮点数不长。我将 float 更改为 long ，然后它工作正常。

#include <stdio.h>
#include <math.h>

long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }

    return gcd(b, a%b);
}

long lcm(long a, long b) {
    return (a * b) / gcd(a,b);
}

int main() {

    long a;
    long b;

    scanf("%ld %ld", &a, &b);
    printf("%ld\n", lcm(a,b));

    return 0;
}
于 2016-04-11T05:24:48.247 回答