如何计算最小公分母

Question

我找不到任何东西，也许是因为我的英语。我想找到几个数字的最小除法值。 在德语中，它被称为：http://de.wikipedia.org/wiki/Hauptnenner 我想知道如何在 .Net 中执行此操作，因为我不敢相信这个问题是新问题，除了像在纸上那样计算“2 个分隔符和 3 个分隔符”之外还没有找到解决方案。

如果能得到任何建议，我会很高兴。

问候

Answer 1

该网站已经告诉您如何做到这一点：找到所有分母集合的最小公倍数。您可以利用最小公倍数和最大公约数之间的关系（请参阅维基百科）并简单地使用欧几里得算法（也可在维基百科上找到）。

Schau nach，wie du den ggT（groessten gemeinsamen Teiler berechnest -> Euklids Algorithmus）。 Danach kannst du den Hauptnenner aus dem kgV der Nenner berechnen.

Answer 2

最小公分母通常称为最小公乘数 LCM。两个数字 a 和 b 的 LCM（表示为 L(a, b)）与这些数字的最大公约数 GCD(a, b) 之间存在关系：

LCM(a, b) = a * b / GCD(a, b)

使用欧几里得算法可以非常有效地计算 GCD(a, b)。

此外，三个数的 LCM 计算可以简化为两个数的 LCM：

LCM(a, b, c) = LCM(LCM(a, b), c),

因此再次计算两个数字的 GCD。现在，计算 N 个数字的 LCM 的过程应该很明显了。

Answer 3

Jiri 展示了 LCM 和 GCD 如何简化为计算两个数字的 GCD。杰夫的算法对于大量数据来说太慢了。这是一个算法的草图，该算法是输入数字长度的多项式，将它们称为 X 和 Y：

• 设置结果 = 1
• 如果X和Y都是偶数，则结果*=2； X/=2； Y/=2；
• 如果一个是偶数，另一个是奇数，偶数的一半（没有其他更新）
• 如果两者都是奇数，则从较大的值中减去较小的值并迭代（注意，这给了我们一个奇偶组合

多项式复杂性的证明来自这样一个事实：在每两次迭代中，我们至少将其中一个数字减少至少一半

Answer 4

我一直在寻找与此类似的东西并提出了这个解决方案。 我发现的大多数解决方案都是针对两个数字的，而我的解决方案需要处理未知数量的数字。不管怎样，这就是我想出来的。 它对我有用，也许对你也有用。

    public static int GetLCM(int[] values) {
        var retval = values[0];
        for (var i = 1; i < values.Length; i++) {
            retval = GCD(retval, values[i]);
        }
        return retval;
    }
    private static int GCD(int val1, int val2) {
        while (val1 != 0 && val2 != 0) {
            if (val1 > val2) 
                val1 %= val2;
            else 
                val2 %= val1;
        }
        return System.Math.Max(val1,val2);
    }