次の流れ図は、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回(エ)になる。
【キーワード】
・ユークリッドの互除法