Python で最大公約数を見つける方法

今回は、Python最大公約数を見つける方法と、Pythonが最大公約数を見つけるための注意事項についてお届けします。実際のケースを見てみましょう。

以前、Knuth TAOCPの最大公約数の解法をまとめましたが、実は放課後問題のアルゴリズム修正では、ユークリッド除算による最大公約数の解法を実現する必要があります。

この質問に対する私の最初の理解は間違っていたので、当然、標準的な答えはありませんでした。次に、標準的な答えに従って、対応するコード実装を作成します:

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(55,120))

プログラムの実行結果:

2 つの数値の位置を交換すると、コードは次のようになります:

# -*- coding:utf-8 -*-
#! python2
def MaxCommpisor(m,n):
  while m * n != 0:
    m = m % n
    if m == 0:
      return n
    else:
      n = n % m
      if n == 0:
        return m
print(MaxCommpisor(120,55))

プログラムの実行結果:

質問プロンプトでは、上記のコードから判断すると、効率の低下は除算と判断にあるはずです。ここで、前のアルゴリズムのコードを取得して比較します:

def CommDevisor(m,n):
  r = m % n
  while r != 0:
    m = n
    n = r
    r = m % n
  return n
print(CommDevisor(120,25))

実行結果:

新しいアルゴリズムには、ループ内に追加の除算と比較演算があります。実際、比較効率は依然として良好ですが、除算演算により効率が低下します。

この記事の事例を読んだ後、あなたはその方法をマスターしたと思います。さらに興味深い情報については、php 中国語 Web サイトの他の関連記事に注目してください。

推奨書籍:

Python Numpy が配列と行列を操作する方法

Python を操作して numpy 配列を走査する方法

以上がPython で最大公約数を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。