平成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(ウ)である。

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

【キーワードの解説】
  • ユークリッドの互除法
    2つの自然数(整数)の最大公約数を求める手法。
    2つの数(自然数、整数)aとb(a ≥ b)について、aのbによる剰余をrとすると、aとbの最大公約数はbとrの最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。

もっと、「ユークリッドの互除法」について調べてみよう。

戻る 一覧へ 次へ