如何计算"kleinster gemeinsamer Nenner"最后一个公分母

Question

我找不到任何东西可能是因为我的英语。我想找出几个数的最小相除值。在德语中，它被称为http://de.wikipedia.org/wiki/Hauptnenner我想知道如何在。net中做到这一点，因为我无法相信这个问题是新的，除了像在纸上那样计算"2除数和3除数"之外，还没有找到解决方案。

如果能得到任何建议就太好了。

对

Answer 1

网站已经告诉你怎么做了:找到所有分母集合的最小公倍数。你可以利用最小公倍数和最大公约数之间的关系(参见维基百科)，并简单地使用欧几里得算法(也可以在维基百科上获得)。

Schau nach, wie du den ggT (groessten gemeinsamen Teiler berhnest -> Euklids Algorithmus)。

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:

• set result = 1
• 如果X和Y都是偶数，result *=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);
    }