問題プレビューID: 9ab47c60基本情報技術者試験 2017年(平成29年度)春期 午前

問 6
基本情報技術者試験 2017年(平成29年度)春期 午前

関数 f(x,y)f(x, y) が次のとおり定義されているとき,f(775,527)f(775, 527) の値は幾らか。ここで,x mod yx \text{ mod } 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 \text{ mod } y)

解説

ユークリッドの互除法を用いて、2 つの数の最大公約数(GCD)を求める再帰関数の問題です。

計算ステップ:

  1. f(775,527)f(775, 527)
    • x=775,y=527x = 775, y = 527
    • 775 mod 527=248775 \text{ mod } 527 = 248
    • 次は f(527,248)f(527, 248)
  2. f(527,248)f(527, 248)
    • 527 mod 248=31527 \text{ mod } 248 = 31 (248×2=496248 \times 2 = 496)
    • 次は f(248,31)f(248, 31)
  3. f(248,31)f(248, 31)
    • 248/31=8248 / 31 = 8 余り 0
    • 次は f(31,0)f(31, 0)
  4. f(31,0)f(31, 0)
    • y=0y = 0 なので xx の値である 31 を返す。

したがって、正解は イ です。

関連問題

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