3

我使用了这种方法。

  1. 找到所有可能的nC2 对n 个数。
  2. 然后通过计算他们的GCD 并将两个数字的乘积除以他们的 GCD 来单独找到他们的LCM 。
  3. 还维护了一个变量，其中包含到目前为止计算的最小 LCM 值并最终输出它。

但是当数值非常大（~10^9）时，这种幼稚的方法似乎效率低下，因为 GCD 的时间复杂度将取决于数字的大小。对于非常大的 N 值也是不可行的。还有其他更好的方法来解决这个问题吗？

4

2 回答 2

0

我不认为有一个有效的算法。

你总是可以使用启发式和简单的，这肯定会解决这个问题。

平均而言，对于大多数数组，这对数字将类似于 a,b(a<b)，其中 LCM(a,b) ~ O(b)，即 a 的大部分因子都包含在 b 中，因此 LCM 大约为的 O(b)。

因此，平均而言，LCM 不会很大并且与数组的元素相似。

所以，想法是对数组进行排序，然后按升序先尝试较小的 a,b。当b> lcm_so_far。

谢谢

于 2016-11-14T10:23:39.553 回答
0

对于大量数字，欧几里得算法 ( https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency ) 的有效实现是我能想到的最佳途径。没有快速、通用的素数分解算法，因此使用它来减少问题无助于运行时间。我不知道有任何快速减少会对此有所帮助。

针对大 N，我认为这是其他人一直在做的：

  1. 对数组进行排序
  2. 从最低值开始并计算 LCM（例如，对于 GCD 部分使用欧几里德算法）：一旦剩余对的 LCM 不能小于迄今为止找到的最佳值，则停止处理。请注意，对于排序集中的两个数字，b < c，LCM 的下限是 (b * c) / b = c（这发生在 b 除以 c 时）。请参阅下面的工作代码（short_lcm 版本）。

可以对此进行其他优化（例如不在python中编写它:)）但这证明了算法的改进：

import fractions

def lcm(a, b):
    return abs(a * b) / fractions.gcd(a, b)

def short_lcm(a):
    a = sorted(a)

    iterations = 0
    cur_lcm = lcm(a[0], a[1])
    first = a[0]
    second = a[1]
    for i in range(0, len(a)):
        #Best case for remaining pairs
        if i < len(a) - 1 and a[i + 1] >= cur_lcm: break

        for j in range(i + 1, len(a)): #Starting at i + 1 avoids duplicates
            if a[j] >= cur_lcm: break  #Best case for remaining pairs

            iterations += 1

            test = lcm(a[i], a[j])
            if test < cur_lcm:
                cur_lcm = test
                first = a[i]
                second = a[j]

    if iterations < 1: iterations = 1

    print("Lowest LCM pair is (%d, %d): %d. Found in %d iterations" % (
                first, second, cur_lcm, iterations))

def long_lcm(a):
    iterations = 0
    cur_lcm = lcm(a[0], a[1])
    first = a[0]
    second = a[1]
    for i in range(0, len(a)):
        for j in range(i + 1, len(a)):     #Starting at i + 1 avoids duplicates
            iterations += 1

             test = lcm(a[i], a[j])
            if test < cur_lcm:
                cur_lcm = test
                first = a[i]
                second = a[j]

    print("Lowest LCM pair is (%d, %d): %d. Found in %d iterations" % (
                first, second, cur_lcm, iterations))

if __name__ == '__main__':
    from random import randint
    import time

    a = [randint(1, 1000) for r in xrange(100)]

    #Only print the list if it's relatively short
    if len(a) < 20: print a

    #Try all pairs
    start = time.clock()
    long_lcm(a)
    print "Slow version time: %f\n" % (time.clock() - start)

    start = time.clock()
    short_lcm(a)
    print "Fast version time: %f" % (time.clock() - start)
于 2016-11-14T17:08:47.730 回答