問題プレビューID: 8be7f6d7基本情報技術者試験 午前免除試験 2021年6月13日

問 9
基本情報技術者試験 午前免除試験 2021年6月13日

関数 f(x,y)f(x, y) が次のとおり定義されているとき,f(775,527)f(775, 527) の値は幾らか。ここで,x mod yx \bmod y は xx を yy で割った余りを返す。

f(x,y): if y=0 then return x else return f(y, x mod y)f(x, y):\ \text{if } y = 0 \text{ then return } x \text{ else return } f(y,\ x \bmod y)

解説

正解は「イ」です。

この関数は,ユークリッドの互除法によって 2 数の最大公約数を求めるものです。f(775,527)f(775, 527) を順に展開します。

  1. f(775,527)f(775, 527):527≠0527 \neq 0 なので f(527, 775 mod 527)=f(527,248)f(527,\ 775 \bmod 527) = f(527, 248)
  2. f(527,248)f(527, 248):248≠0248 \neq 0 なので f(248, 527 mod 248)=f(248,31)f(248,\ 527 \bmod 248) = f(248, 31)
  3. f(248,31)f(248, 31):31≠031 \neq 0 なので f(31, 248 mod 31)=f(31,0)f(31,\ 248 \bmod 31) = f(31, 0)
  4. f(31,0)f(31, 0):y=0y = 0 なので 3131 を返す

したがって求める値は 31 であり,「イ」が正解です。これは gcd⁡(775,527)=31\gcd(775, 527) = 31 に一致します。

  • ア・ウ・エ: いずれも展開結果の 31 とは一致しません。

関連問題

本文が同じ・似ている問題を表示しています