問題
関数 gcd(m,n) が次のように定義されている。m＝135、n＝35 のとき、gcd(m,n) は何回呼び出されるか。ここで、最初の呼出し gcd(135,35) の呼出しも、1 回に数えるものとする。また、m、n は m＞n≧0 を満たす整数とし、m mod n は m を n で割った余りを返すものとする。
〔関数の定義〕
gcd(m,n)＝ m （n＝0 のとき）
gcd(m,n)＝ gcd(n, m mod n) （n＞0 のとき）
選択肢
- 12
- 23
- 34
- 45
正解
3. 4
詳しい解説を見る解説を閉じる
解説
ユークリッドの互除法を再帰で実装したものである。順に計算すると、gcd(135,35)→gcd(35,30)→gcd(30,5)→gcd(5,0) となり、最後に n＝0 となって 5 を返す。呼び出しは gcd(135,35)、gcd(35,30)、gcd(30,5)、gcd(5,0) の 4 回なので、ウが正解である。（出典: 平成24年度 春期 応用情報技術者試験 午前 問8）
一問一答
全400問を繰り返し学習