平成28年度 秋期 基本情報技術者試験 午前 問7
テクノロジ／アルゴリズム整数x，y（x＞y≧0）に対して，次のように定義された関数F(x,y)がある。F(231,15)の値は幾らか。ここで，x mod yはxをyで割った余りである。 F(x,y) ＝ x （y＝0のとき） F(x,y) ＝ F(y，x mod y) （y＞0のとき）
出典：平成28年度 秋期 基本情報技術者試験 午前 問7
- ア2
- イ3
- ウ5
- エ7
正解：イ
解説
この関数はユークリッドの互除法と同じ考え方で，xをyで割った余りを使って再帰的に処理を進め，yが0になったときのxの値を返します。F(231,15)→F(15,231 mod 15)＝F(15,6)→F(6,15 mod 6)＝F(6,3)→F(3,6 mod 3)＝F(3,0)となり，y＝0なのでxの値である3が返されます。
選択肢ごとの解説
- ア誤り。2になるのは，計算の途中で剰余を求める順序を取り違え，誤った値のまま計算を進めた場合に生じる値です。
- イ正しい。F(231,15)→F(15,6)→F(6,3)→F(3,0)と再帰的に計算が進み，最後にy＝0となったときのxの値である3が返されます。
- ウ誤り。5になるのは，剰余の計算を1回誤り，途中の値を実際とは異なるものとして計算を進めた場合に生じる値です。
- エ誤り。7になるのは，最初のF(231,15)の剰余を231÷15の商である15と取り違えるなど，計算を誤った場合に生じる値です。