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

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

正解の理由

解法ステップ

1. 与えられた定義をユークリッドの互除法と同一であると認識する。
2. 実際に値を代入して再帰の流れを追う：
   • $f(775,527)$ → $f(527,775\mathrm{mod}527)$、まず $775\mathrm{mod}527=248$。
   • 次に $f(527,248)$ → $f(248,527\mathrm{mod}248)$、$527\mathrm{mod}248=31$。
   • 次に $f(248,31)$ → $f(31,248\mathrm{mod}31)$、$248\mathrm{mod}31=0$。
   • 最後に $f(31,0)$ となり定義より $31$ を返す。
3. よって $f(775,527)=31$ が導かれる。

選択肢別の誤答解説

• ア: 0 — 余りが0になった場面を「答えは0」と誤解した場合の落とし穴。定義では $y=0$ のとき $x$ を返すため誤り。
• イ: 31 — 正解。ユークリッド互除法の結果、最大公約数は31となる。
• ウ: 248 — 途中の余りをそのまま答えにしてしまったパターン。248は途中の余りだが最終結果ではない。
• エ: 527 — 片方の引数を単純に答えと見なした誤り。最終的に返る値は両数の最大公約数であり527ではない。

よくある誤解

• 「余りが0になったら0を返す」と考える誤り：実際は余りが0の直前の呼び出しでの第一引数 $x$ が返され、これが最大公約数です。
• 「再帰を途中で止めて現在の余りを答えにしてしまう」：途中の余り（例えば248）ではなく、最終的に $y=0$ になったときの $x$ を答える点を見落としやすい。
• 「関数は単純な mod を返すだけ」と混同：この関数は再帰呼び出しを通じて最大公約数を求めるアルゴリズムです。

補足コラム

def f(x, y):
    if y == 0:
        return x
    return f(y, x % y)

print(f(775, 527))  # 31

FAQ