| 基本情報技術者試験 |
2016年度 ＝ 平成28年度・秋期 |
午前 |
問7 |
整数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のとき）
イ
関数F (x , y )は、ユークリッドの互除法によって、x とy の最大公約数を求める関数です。
二つの整数値が与えられたとき、大きい方の値を小さい方の値で割ってみて、割り切れて剰余が0となれば小さい方の値が最大公約数です。割り切れない場合は、小さい方の値と得られた剰余に対して、割り切れるまで、同じ手続きを再帰的に繰り返します。
231と15の最大公約数は3です（以下のように、商が0になるまで除算を繰り返して求めます）。
231 ÷ 15 ＝ 15 … 6
15 ÷ 6 ＝ 2 … 3
6 ÷ 3 ＝ 0
