アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20141221 実施分 問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のとき）
F(x,y)＝{ x （y＝0のとき） / F(y, x mod y) （y＞0のとき） }
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20141221 実施分 問7（問題文は IPA の公開問題。解説は当サイト作成）
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は x を y で割った余りで繰り返し置換し、余りが0になったときの除数が最大公約数となる。
この問題で必要なこと
F(x,y)=F(y,x mod y) はユークリッドの互除法で最大公約数を返す。gcd(231,15)=3。
ひっかけ
最小公倍数や途中の余りの値を答えさせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）