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

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

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

解説

正解は「イ」です。

この関数はユークリッドの互除法により,二数の最大公約数を求めるものです。再帰的に計算すると次のようになります。

f(775,527)=f(527,248)=f(248,31)=f(31,0)=31f(775, 527) = f(527, 248) = f(248, 31) = f(31, 0) = 31

  • 775 mod 527=248775 \bmod 527 = 248
  • 527 mod 248=31527 \bmod 248 = 31
  • 248 mod 31=0248 \bmod 31 = 0

y=0y = 0 となったときの x=31x = 31 が最大公約数であり,求める値は 31 です。したがって「イ」が正解です。

関連問題

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