平成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回(エ)になる。


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

キーワードの解説

戻る 一覧へ 次へ