1

現在、このコードを使用してgcdとlcmを見つけています

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

def lcm(a, b):
    result = a*b/gcd(a,b)
    return result

しかし、[4,5,7,1,5,7,10,1,16,24] などの数値のリストに対してこれを実行したい場合はどうすればよいでしょうか。ループに制約されていますか?

4

3 に答える 3

0

再帰的な手法を使用できます。

def gcd(a, b):
   if b == 0:
      return a
   else:
      return gcd(b, a%b)

すべてのGCD値をハッシュマップに保存します。したがって、再帰ステップを実行するときは、最初にハッシュマップにアクセスして、小さい数値のGCDがすでに計算されているかどうかを確認します。これにより、広範囲の入力に対してこれを実行した場合に多くの時間を節約できます。

于 2012-01-10T17:08:02.237 に答える
0

Chris J が述べたように、このSO の質問はアルゴリズムを提供します。これは、バージョン 2.6 以降のreduceビルトインとモジュールを使用する答えの Python バージョンです。fractions

import fractions

def gcd(*values):
    return reduce(fractions.gcd, values)
于 2012-01-11T01:28:05.470 に答える