うごく基本情報

平成28年度 秋期 問7

アルゴリズムとプログラミング

出典:平成28年度 秋期 基本情報技術者試験 午前 問7 の問題

出典:平成28年度 秋期 基本情報技術者試験 午前 問7

正解と解説を見る

正解:イ

覚えること:F(x, y) = F(y, x mod y) はユークリッドの互除法(最大公約数)。y が 0 になったときの x が答え。

F(231, 15) → 231 mod 15 = 6 で F(15, 6)、15 mod 6 = 3 で F(6, 3)、6 mod 3 = 0 で F(3, 0) となり、3 を返します(イ)。231 と 15 の最大公約数が 3 です。アの 2、ウの 5、エの 7 は、231 と 15 の両方を割り切る数ではありません(15 は 2 と 7 で割り切れず、231 は 5 で割り切れません)。

解説はこのサイトが作成したものです。