平成20年 春期 基本情報技術者 午前 問15

次の流れ図は、2数A、Bの最大公約数を求めるユークリッドの互除法を、引き算の繰返しによって計算するものである。
Aが876、Bが204のとき、何回の比較で処理は終了するか。

 ア  4
 イ  9
 ウ  10
 エ  11


答え エ


解説
A=876、B=204の時の処理を流れ図を追って、比較の回数を確認する。

  1. L = 876、S = 204なので、1回目の比較はL > Sで、LS = 672をLに代入する。
  2. L = 672、S = 204なので、2回目の比較はL > Sで、LS = 468をLに代入する。
  3. L = 468、S = 204なので、3回目の比較はL > Sで、LS = 264をLに代入する。
  4. L = 264、S = 204なので、4回目の比較はL > Sで、LS = 60をLに代入する。
  5. L = 60、S = 204なので、5回目の比較はL < Sで、SL = 144をSに代入する。
  6. L = 60、S = 144なので、6回目の比較はL < Sで、SL = 84をSに代入する。
  7. L = 60、S = 84なので、7回目の比較はL < Sで、SL = 24をSに代入する。
  8. L = 60、S = 24なので、8回目の比較はL > Sで、LS = 36をLに代入する。
  9. L = 36、S = 24なので、9回目の比較はL > Sで、LS = 12をLに代入する。
  10. L = 12、S = 24なので、10回目の比較はL < Sで、SL = 12をSに代入する。
  11. L = 12、S = 12なので、11回目の比較はL = Sで、A = 876、B = 204、L = 12を出力して終了する。
したがって、比較回数は11(ウ)である。


キーワード
・ユークリッドの互除法

キーワードの解説

戻る 一覧へ 次へ