ユークリッド除算に基づいて最大公約数を見つける方法の Python の例

この記事では主に、ユークリッド除算に基づいて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))

実行結果:

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

追記: さらなる参考として、いくつかの計算ツールをお勧めします:

オンライン 1 変数関数 (方程式) 解決計算ツール:
http://tools.jb51.net/jisuanqi/ equ_jisuanqi

関数電卓オンライン使用_高度な電卓オンライン計算:
http://tools.jb51.net/jisuanqi/jsqkexue

オンライン電卓_標準電卓:
http:// tools.jb51.net/ jisuanqi/jsq

関連おすすめ:

php 2つの整数の最大公約数を計算する一般的なアルゴリズムのまとめ_PHPチュートリアル

Pythonを使用して最大公約数を解く実装方法

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