平成31年 春期 基本情報技術者 午前 問7

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

 ア  4  イ  9  ウ  10  エ  11


答え エ


解説
この流れ図で比較処理はひし形の箇所になるので、比較の回数は
 1回目の比較は 876:204
 2回目の比較は 672:204
 3回目の比較は 468:204
 4回目の比較は 264:204
 5回目の比較は 60:204
 6回目の比較は 60:144
 7回目の比較は 60:84
 8回目の比較は 60:24
 9回目の比較は 36:24
 10回目の比較は 12:24
 11回目の比較は 12:12
11回(エ)になる。


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

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

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

戻る 一覧へ 次へ