3

私はこのアプローチを使用しました。

  1. n 個の数で可能なすべてのnC2 ペアを見つけました。
  2. 次に、GCD を計算し、2 つの数値の積を GCD で割ることによって、 LCMを個別に見つけました。
  3. また、それまでに計算された最小の LCM 値を含む変数を維持し、最終的にそれを出力しました。

しかし、GCD の時間の複雑さは数値の大きさに依存するため、数値が非常に大きい (~10^9) 場合、この素朴なアプローチは非効率的です。また、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

桁数が多い場合、GCD を見つけるためのユークリッド アルゴリズム ( https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency ) の効率的な実装が、私が考えることができる最良のルートです。素因数分解には高速で一般的なアルゴリズムがないため、それを使用して問題を軽減しても実行時間は短縮されません。これに役立つ迅速な削減については知りません。

大きなNに対処すると、これは他の人が得ているものだと思います：

  1. 配列をソートする
  2. 最小値から開始し、短絡を使用して LCM を計算します (たとえば、GCD 部分にユークリッド アルゴリズムを使用)。残りのペアの LCM がこれまでに見つかった最良の値より小さくならない場合は、処理を停止します。ソート済みセット内の 2 つの数値 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 に答える