Pythonのユークリッド互除法
数の組を除数と余りへ繰り返し置き換えます。
Pythonのユークリッド互除法とは？
数の組を除数と余りへ繰り返し置き換えます。
2つの整数の最大公約数を求めます。
どのような場面で使う？
- アルゴリズムとデータ構造を理解する。
- 各ステップと境界ケースを確認する。
- 実行時間とメモリ使用量を比較する。
サンプルコード
main.py
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))期待される出力
6仕組み
余りが0になったときのもう一方が最大公約数です。計算量は対数的です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
練習問題
入力値と境界ケースを変更し、より大きなデータでも動作を確認してください。
- 空入力、1要素、重複値を試す。
- 各ステップの状態を表示する。
- 別の解法と性能を比較する。