アルゴリズムとプログラミング
平成23年度 特別試験 基本情報技術者試験 午前 問6
関数 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
出典：平成23年度 特別試験 基本情報技術者試験 午前 問6
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、x mod y を繰り返して余りが0になったときの除数を最大公約数とするアルゴリズムである。
この問題で必要なこと
f(x,y)=f(y, x mod y)を繰り返し、y=0になったときのxが最大公約数。775,527→527,248→248,31→31,0 で31。
ひっかけ
途中の値(248や527)や0を答えとさせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）