基本情報技術者 2017年 春期 午前（科目A） 問06

ユークリッドの互除法【午前解説】

正解の理由

解法ステップ

1. 関数定義を「互除法（gcd）」と認識する。条件分岐は $y=0$ で終了、そうでなければ再帰（交換して剰余）する。
2. 具体的に剰余計算を順に行う：$775\mathrm{mod}527=248$。
3. 次に $527\mathrm{mod}248=31$。
4. 次に $248\mathrm{mod}31=0$ となり、ここで $y=0$、関数は $x$（この時点での $x=31$）を返す。
5. したがって答えは 31。

選択肢別の誤答解説

• ア: 0 — 関数が常に 0 を返すと思った誤り。実際は $y=0$ のときにその時点の $x$ を返すため、両方が 0 でない限り 0 にはなりません。
• イ: 正解（31） — 正しく互除法を最後まで実行した結果です。
• ウ: 248 — $775\mathrm{mod}527$ の最初の余りであり途中経過に過ぎません。再帰はさらに続きます。
• エ: 527 — 初期の第二引数 y をそのまま返す誤解です。y が 0 でなければ再帰が行われ、最終結果は変わります。

よくある誤解

• 「最初の余りを答えにしてしまう」：$775\mathrm{mod}527=248$ をそのまま答えと誤認する受験者が多いですが、関数はさらに再帰を続けます。
• 「0 を答えにする誤解」：再帰で $y=0$ になった時に返すのは $x$ であり、決して常に 0 を返すわけではありません。0 は両方が 0 の特殊ケース以外では現れません。
• 「大きい方（527）をそのまま答える誤り」：初期の y の値をそのまま返すように読み違えるケースがありますが、定義は y が 0 でない限り再帰を行います。

補足コラム

# 再帰版（問題と同じ定義）
def f(x, y):
    if y == 0:
        return x
    return f(y, x % y)

# 反復版
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(f(775, 527))  # 31
print(gcd(775, 527))  # 31

FAQ