アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20201213 実施分 問9
整数 x，y（x＞y≧0）に対して，次のように定義された関数 F(x,y) がある。F(231,15) の値は幾らか。ここで，x mod y は x を y で割った余りである。
F(x, y) = { x （y＝0 のとき）
{ F(y, x mod y) （y＞0 のとき）
- ア 2
- イ 3
- ウ 5
- エ 7
出典：基本情報技術者試験 科目A免除 修了試験 20201213 実施分 問9
答えと解説を見る
正解：イ
覚える知識
再帰関数のトレース計算
F(x,y)=F(y,x mod y) はユークリッドの互除法で、y=0 のときの x が最大公約数。
この問題で必要なこと
F(231,15)→F(15,6)→F(6,3)→F(3,0)=3となり、最大公約数を求める再帰である。
ひっかけ
最後の余りや途中の商を答えにしてしまう。
この知識の出題：本試験系 8 回・免除試験 11 回（公開問題での観測値）