| ソフトウェア開発技術者試験 |
2004年度 ＝ 平成16年度 |
午前 |
問14 |
整数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となれば小さい方の値が最大公約数です。割り切れない場合は、小さい方の値と得られた剰余に対して、割り切れるまで、同じ手続きを再帰的に繰り返します。
1170と231の最大公約数は3です（以下のように、商が0になるまで除算を繰り返して求めます）。
1170 ÷ 231 ＝ 5 … 15
231 ÷ 15 ＝ 15 … 6
15 ÷ 6 ＝ 2 … 3
6 ÷ 3 ＝ 0
