アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20140727 実施分 問8
関数 f(x，y) が次のように定義されているとき，f(775，527) の値は幾らか。ここで，x mod y は x を y で割った余りを返す。
f(x，y)： if y = 0 then return x else return f(y，x mod y)
- ア 0
- イ 31
- ウ 248
- エ 527
出典：基本情報技術者試験 科目A免除 修了試験 20140727 実施分 問8
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、x mod yを繰り返して余りが0になったときのxを最大公約数とする。
この問題で必要なこと
f(775,527)→f(527,248)→f(248,31)→f(31,0)=31。最大公約数を求める互除法である。
ひっかけ
最後の余り0や最初の引数を答えにしてしまう。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）