BohYoh.com《ソフトウェア開発技術者試験》 2002年度＝平成14年度午前問14

ソフトウェア開発技術者試験

2002年度＝平成14年度

午前

問14

　整数x，y （x ＞ y ≧ 0）に対して、次のように定義された関数F (x, y )がある。F (1170, 231)の値は幾らか。ここで、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 の最大公約数を求めるアルゴリズムに基づく定義であることは明らかです。
　1170と231の最大公約数は3です（以下のように、商が0になるまで除算を繰り返して求めます）。

　　　1170 ÷ 231 ＝  5　…　15
　　　 231 ÷　15 ＝ 15　…　 6
　　　　15 ÷　 6 ＝  2　…　 3
　　　　 6 ÷　 3 ＝  0