基本情報技術者試験 2007年度 = 平成19年度・秋期 午前 問15

 整数x , y x y ≧0)に対して、次のように定義された関数F (x , y )がある。F (231, 15)の値は幾らか。ここで、x mod y x y で割った余りである。

         x  (y = 0のとき)   F (x,y) = {          F (y, x mod y)  (y >0のとき)


ア 2 イ 3 ウ 5 エ 7

解答



解説

 関数F (x , y )は、ユークリッドの互除法によって、x y 最大公約数を求める関数です。
 二つの整数値が与えられたとき、大きい方の値を小さい方の値で割ってみて、割り切れて剰余が0となれば小さい方の値が最大公約数です。割り切れない場合は、小さい方の値と得られた剰余に対して、割り切れるまで、同じ手続きを再帰的に繰り返します。
 231と15の最大公約数は3です(以下のように、商が0になるまで除算を繰り返して求めます)。
    231 ÷ 15 = 15 …  6
    15 ÷  6 =  2 …  3
     6 ÷  3 =  0

BohYoh.comトップページへ