平成24年度 春期 応用情報技術者試験 午前 問8
関数 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 のとき）
キーボード：1〜4 で解答 → 次の問題 ← 前の問題
正解と解説を見る
解答する前に解説を開いたので、この問題は「見て解いた」として記録します（正解数には入りません）。
正解：ウ
定義に従って呼出しをたどります。
- gcd(135, 35): 135 mod 35 ＝ 30 → gcd(35, 30) を呼ぶ
- gcd(35, 30): 35 mod 30 ＝ 5 → gcd(30, 5) を呼ぶ
- gcd(30, 5): 30 mod 5 ＝ 0 → gcd(5, 0) を呼ぶ
- gcd(5, 0): n ＝ 0 なので 5 を返す
呼出し回数は 4回 です。
-
ア: 2
誤り。呼出しは gcd(135,35) から gcd(5,0) まで4回あるので誤りです。 -
イ: 3
誤り。n ＝ 0 となる最後の呼出し gcd(5, 0) も数えるので，4回になります。 -
ウ: 4
正しい。gcd(135,35) → gcd(35,30) → gcd(30,5) → gcd(5,0) の4回です。 -
エ: 5
誤り。呼出しは4回なので誤りです。
答え
ウ: 4
出典：平成24年度 春期 応用情報技術者試験 午前 問8
