[基本情報技術者試験]ユークリッドの互除法のアルゴリズムをPythonで書いてみた。

概要

• 基本情報技術者試験の午後の試験でアルゴリズムがあります。過去問を解いても理解ができません…。実際にアルゴリズムをPythonで書いて、理解を深めていきたいと思います。

• まず最初はユークリッドの互除法のアルゴリズムから書いてみます。

ユークリッドの互除法

アルゴリズム

• 二つの整数の大きい方から小さい方を引くことを、両者が等しくなるまで繰り返す。等しくなった値が最大公約数である。
• GCMはGreatest Common Measure（最大公約数）

コード

# ユークリッドの互除法で最大公約数を求めるGCM関数
def GCM(A,B):
    # 繰り返し処理
    while A != B: # AとBが等しくなるまで繰り返す
        print("A=",A,"B=",B) # 途中の結果
        # 分岐処理
        if A > B: # AがBより大きいなら
            A = A - B # AにA-Bを格納する
        else:
            B = B - A # BにB-Aを格納する
    return A

print("実行結果：",GCM(84,60))

実行結果

A= 84 B= 60
A= 24 B= 60
A= 24 B= 36
A= 24 B= 12
実行結果： 12

まとめ

• 頭で考えるだけよりも、実際にプログラムを書いたほうが理解が深まった。
• 次回はうるう年のアルゴリズムを書こうかな

参考

• こちらの本のCHAPTER3 01ユークリッドの互除法を引用または参考にしました。
  情報処理教科書 基本情報技術者試験のアルゴリズム問題がちゃんと解ける本 第2版