平成31年度 春期 午前 問7

✓ これが正解エ11

解説

引き算を繰り返して、十一回目の比較で二つが等しくなります。

ユークリッドの互除法は、大きいほうから小さいほうを引くことを繰り返します。二つが等しくなった時点で、その値が最大公約数です。この流れ図では、比べるたびに一回と数えます。始まりは八百七十六と二百四です。大きいほうから引く操作を四回続けると、六十と二百四になります。ここで大小が入れ替わり、今度はもう一方から引く番です。三回引くと六十と二十四になり、また入れ替わります。さらに二回引いて十二と二十四になります。もう一回引くと十二と十二で並びます。ここまでの比較を数えると十回で、等しいと確かめる比較が十一回目です。引き算の回数と比較の回数がずれる点に注意します。最後の一回は引き算を伴わないからです。引いた回数は十回で、比較はそれより一つ多くなります。割り算で行えば回数はぐっと減ります。

ほかの選択肢はなぜ違うのか

• ア4：割り算による互除法の回数に近い値です。この流れ図は引き算の繰返しなので、回数はずっと多くなります。同じ結果でも、数え方が違えば回数は変わります。割り算なら少ない回数で済みます。引き算に直すと回数は増えます。
• イ9：最後に等しいと確かめる比較を含めていない数え方より、さらに少ない値です。入れ替わりの後の引き算を数え落とすと、この付近になります。大小が入れ替わる箇所は三か所あります。どれも数える必要があります。入れ替わりを見落とした形です。
• ウ10：引き算を行った回数にあたります。最後の一回は等しいと確かめるだけで、引き算をしません。その一回を足し忘れた形です。問われているのは比較の回数です。最後の比較は等号の確認です。引かずに終わります。一つ足りない形です。