アルゴリズムとプログラミング
平成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(y, x mod y) （y>0 のとき）
答えを選ぶ
出典：平成28年度 秋期 基本情報技術者試験 午前 問7（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
F(x,y)=F(y, x mod y) を y=0 まで繰り返すとx、y の最大公約数が得られる。
この問題で必要なこと
F(231,15)→F(15,6)→F(6,3)→F(3,0)=3 と再帰をたどり、最大公約数3を得る。
ひっかけ
途中の剰余(6や15)を答えにしたり、最大公約数と最小公倍数を混同させる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）