応用情報技術者 2012年 春期 午前2 問08
問題文
関数が次のように定義されている。、のとき、は何回呼ばれるか。ここで、最初のの呼出しも、1回に数えるものとする。また、は整数とし、はをで割った余りを返すものとする。
〔関数の定義〕
選択肢
ア：2
イ：3
ウ：4（正解）
エ：5
関数gcd(m, n)の呼び出し回数【午前2 解説】
要点まとめ
- 結論：の呼び出し回数は4回です。
- 根拠：ユークリッドの互除法により、再帰呼び出しは余りが0になるまで続きます。
- 差がつくポイント：呼び出し回数は最初の呼び出しも含めて数えることを忘れないことです。
正解の理由
関数はになるまで再帰的に呼ばれます。
135と35の余り計算は以下の通りです。
1回目：gcd(135, 35) → 35 ≠ 0 → 次は gcd(35, 135 mod 35)
135 mod 35 = 30 → 2回目：gcd(35, 30)
30 ≠ 0 → 次は gcd(30, 35 mod 30)
35 mod 30 = 5 → 3回目：gcd(30, 5)
5 ≠ 0 → 次は gcd(5, 30 mod 5)
30 mod 5 = 0 → 4回目：gcd(5, 0)
ここでなので終了。呼び出しは合計4回です。
したがって、正解はウの4回です。
135と35の余り計算は以下の通りです。
1回目：gcd(135, 35) → 35 ≠ 0 → 次は gcd(35, 135 mod 35)
135 mod 35 = 30 → 2回目：gcd(35, 30)
30 ≠ 0 → 次は gcd(30, 35 mod 30)
35 mod 30 = 5 → 3回目：gcd(30, 5)
5 ≠ 0 → 次は gcd(5, 30 mod 5)
30 mod 5 = 0 → 4回目：gcd(5, 0)
ここでなので終了。呼び出しは合計4回です。
したがって、正解はウの4回です。
よくある誤解
呼び出し回数を余りが0になるまでの再帰回数と勘違いし、最初の呼び出しを数えないことがあります。
また、余りの計算ミスで呼び出し回数を誤ることも多いです。
また、余りの計算ミスで呼び出し回数を誤ることも多いです。
解法ステップ
- 最初の呼び出しgcd(135, 35)を1回目と数える。
- を計算し、余りが0でなければ再帰呼び出しを続ける。
- 余りが0になるまで繰り返し、呼び出し回数をカウントする。
- 最終的な呼び出し回数を答える。
選択肢別の誤答解説
- ア: 2回は余り計算を途中で止めすぎている。
- イ: 3回は最終呼び出しののケースを数えていない。
- ウ: 4回は正しい呼び出し回数。
- エ: 5回は余り計算の段階数を誤って多く数えている。
補足コラム
ユークリッドの互除法は最大公約数を求める最も効率的な方法で、再帰的に余りを計算し続けます。
呼び出し回数は余りの大きさに依存し、最悪の場合はフィボナッチ数列に近い回数となることもあります。
呼び出し回数は余りの大きさに依存し、最悪の場合はフィボナッチ数列に近い回数となることもあります。
FAQ
Q: なぜのときに呼び出しを終了するのですか？
A: のとき、が最大公約数であるため、再帰を終了します。
A: のとき、が最大公約数であるため、再帰を終了します。
Q: 呼び出し回数に最初の呼び出しは含めますか？
A: はい。問題文で最初の呼び出しも1回に数えると明記されています。
A: はい。問題文で最初の呼び出しも1回に数えると明記されています。
関連キーワード: ユークリッドの互除法、最大公約数、再帰呼び出し、余り計算、gcd関数
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！