平成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のとき）
出典：平成24年度 春期 応用情報技術者試験 午前 問8
- ア2
- イ3
- ウ4
- エ5
正解：ウ
解説
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の基底部となり値を返します。呼出し回数は，gcd(135,35)，gcd(35,30)，gcd(30,5)，gcd(5,0)の合計4回です。
選択肢ごとの解説
- ア誤り。再帰呼出しの回数を1回少なく数えています。
- イ誤り。基底部の呼出しを数え忘れると3回になりますが，問題文の指示に従うと4回です。
- ウ正しい。最初の呼出しを含めて，gcdは合計4回呼ばれます。
- エ誤り。計算過程を1ステップ多く見積もった場合の値です。