問題プレビューID: 4064e693基本情報技術者試験 午前免除試験 2018年12月9日

問 5
基本情報技術者試験 午前免除試験 2018年12月9日

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

  • y=0y = 0 のとき:F(x,y)=xF(x, y) = x
  • y>0y > 0 のとき:F(x,y)=F(y,x mod y)F(x, y) = F(y, x \bmod y)
解説

正解は「イ」です。

この関数はユークリッドの互除法を表しており,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 なので 33

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

  • ア・ウ・エ: いずれも計算の途中で誤った値です。

関連問題

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