基本情報技術者 2016年 秋期 午前（科目A） 問07

最大公約数を求める再帰関数 F(x,y) の値【午前2 解説】

要点まとめ

• 結論→ この再帰的定義はユークリッドの互除法で最大公約数を計算し、F(231,15)=3になります。計算は余りを繰り返すことで必ず停止します。
• 根拠→ 定義は y=0 のとき x を返し、y>0 のとき F(y, x mod y) を呼ぶため、gcd(x,y) を求める標準的な再帰式と同一です。
• 差がつくポイント→ 途中での余り計算ミスを防ぎ、231 mod 15 = 6、15 mod 6 = 3、6 mod 3 = 0 の一連を正確に追えるかが鍵です。

正解の理由

よくある誤解

• 「x mod y を逆に計算する」：$x\mathrm{mod}y$ と $y\mathrm{mod}x$ を取り違えると全く別の過程になりミスします。
• 「ベースケースの理解不足」：$y=0$ のときに $x$ を返す意味を誤解すると計算を止められません。
• 「単純な割り算ミス」：231 ÷ 15 の余りを誤って 3 や 5 にしてしまうことがよくあります。

解法ステップ

1. 定義を「再帰的に余りを取ることで最大公約数を求める」互除法と認識する。
2. 与えられた数で順に余りを計算する：まず $231\mathrm{mod}15$ を求める。
3. 得られた余りが 0 になるまでステップ 2 を繰り返す（各ステップで引数を入れ替える）。
4. 余りが 0 になったときのもう一方の数が答え（gcd）である。
5. 本問では $231\mathrm{mod}15=6$ → $15\mathrm{mod}6=3$ → $6\mathrm{mod}3=0$ で終了、答えは 3。

選択肢別の誤答解説

• ア: 2 — 231 と 15 の共通因子として 3 が存在するため 2 は誤り。231 は奇数なので 2 は共通因子になり得ません。
• イ: 3 — 正解。上の計算列に従うと最終的に 3 が最大公約数になります。
• ウ: 5 — 15 は 5 を因子に持ちますが 231 は 5 で割り切れないため共通因子ではありません。
• エ: 7 — 231 は 7 を因子に持ちますが 15 は 7 で割り切れないため最大公約数にはなりません。

補足コラム

FAQ