平成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(n, m mod n)（n＞0のとき）
- ア 2
- イ 3
- ウ 4
- エ 5
解答・解説を見る
正解：ウ
AI解説
ユークリッドの互除法のトレース問題である。gcd(135,35) → 135 mod 35=30 なので gcd(35,30) → 35 mod 30=5 なので gcd(30,5) → 30 mod 5=0 なので gcd(5,0) となり、n=0 で終了する。呼出しは gcd(135,35), gcd(35,30), gcd(30,5), gcd(5,0) の4回である。 ア: 2回は途中の再帰呼出しを数え漏らした値である。 イ: 3回は最初の呼出しまたは最後の gcd(5,0) を数え忘れた値である。 ウ: 正解。引数の列 (135,35)→(35,30)→(30,5)→(5,0) で4回呼ばれる。 エ: 5回は余分に数えた誤りである。 💡 mod の列 135, 35, 30, 5, 0 を書き出せば呼出し回数が見える。「最初の呼出しを1回に数える」という条件の読み落としが定番のひっかけである。
出典：平成24年度 春期 応用情報技術者試験 午前 問8 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。著作権はIPAに帰属します。