問題プレビューID: eabc9566基本情報技術者試験 午前免除試験 2019年7月28日

問 8
基本情報技術者試験 午前免除試験 2019年7月28日

関数 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)

解説

正解は「イ」です。

この関数はユークリッドの互除法によって xx と yy の最大公約数を求めるものです。

  • f(775,527)f(775, 527): 775 mod 527=248775 \bmod 527 = 248 なので f(527,248)f(527, 248) を呼ぶ。
  • f(527,248)f(527, 248): 527 mod 248=31527 \bmod 248 = 31 なので f(248,31)f(248, 31) を呼ぶ。
  • f(248,31)f(248, 31): 248 mod 31=0248 \bmod 31 = 0 なので f(31,0)f(31, 0) を呼ぶ。
  • f(31,0)f(31, 0): y=0y = 0 なので 3131 を返す。

よって値は 31 です。

関連問題

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