IT Master

問題プレビューID: 2f665df8

問 7

整数 x,yx, y（x>y≧0x > y \geqq 0）に対して，次のように定義された関数 F(x,y)F(x, y) がある。F(231,15)F(231, 15) の値は幾らか。ここで，x mod yx \bmod y は xx を yy で割った余りである。

F(x,y)={x(y=0 のとき)F(y,x mod y)(y>0 のとき)F(x, y) = \begin{cases} x & (y = 0 \text{ のとき}) \\ F(y, x \bmod y) & (y > 0 \text{ のとき}) \end{cases}
解説

この定義は，2 数の最大公約数を求めるユークリッドの互除法と同じです。再帰的に計算します。

  1. F(231,15)F(231, 15)：231 mod 15=6231 \bmod 15 = 6 なので F(15,6)F(15, 6)
  2. F(15,6)F(15, 6)：15 mod 6=315 \bmod 6 = 3 なので F(6,3)F(6, 3)
  3. F(6,3)F(6, 3)：6 mod 3=06 \bmod 3 = 0 なので F(3,0)F(3, 0)
  4. F(3,0)F(3, 0)：y=0y = 0 なので定義より x=3x = 3

したがって，F(231,15)=3F(231, 15) = 3 となり，正解は「イ」です。