ユークリッドの互除法で比較回数はどう数える？
基本情報技術者試験 平成31年度春期 午前 問7 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
次の流れ図は，2数 A，B の最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。
- ア
4
- イ
9
- ウ
10
- エ
11
会話形式の解説
講師この流れ図では、引き算の回数と「L：S」で比較する回数を分けて数えることが大切です。
受験者Lが876、Sが204から始まります。まずLから204を繰り返し引くのですね。
講師はい。4回引くとLは60、Sは204になります。4回目の比較は引き算の前なので、まだ終了しません。
受験者4回という答えでは、最初の引き算の区切りまでしか数えていませんね。その後はSの方が大きいです。
講師Sから60を3回引くとSは24です。続いてLから24を2回引くと、Lは12、Sは24になります。
受験者9回目の比較では、まだLが36、Sが24ですね。ここでも等しくありません。
講師そのとおりです。比較後にLから24を引き、10回目の比較ではLが12、Sが24です。
受験者10回目の比較でも終わらず、その後にSから12を引いて両方が12になります。
講師はい。ここまでの引き算は合計10回です。両方が12になったことを流れ図が確かめるには、比較にもう一度戻ります。
受験者つまり、10回という答えは引き算を数えたものです。最後に等しいと判定する比較を加えて、11回ですね。
講師正解です。「L：S」では大小に加えて等しいかも調べます。回数を問われたら、どの処理を数えるのか確認しましょう。
まとめ
L＝876、S＝204から始め、大きい方から小さい方を引いて比較に戻ります。Lから4回、Sから3回、Lから2回、Sから1回の計10回引くと、両方が12になります。その後、等しいことを確かめる比較がもう1回あるため、比較は計11回です。
解答・解説
正解はエです
この問題のテーマ
引き算で行うユークリッドの互除法について、流れ図の比較が終了までに何回行われるかを問う問題です。
解き方の考え方
初期値は L＝876、S＝204です。図では L と S を比較し、大きい方から小さい方を引いて比較に戻ります。L から4回、S から3回、L から2回、S から1回引くと、両方が12になります。引き算は計10回ですが、終了を決める等値判定も比較に含めます。
選択肢ごとの解説
- ×ア 44回目の比較では L＝264、S＝204なので、比較後に L から204を引きます。この時点では L＝60、S＝204で等しくなく、処理は続きます。
- ×イ 99回目の比較では L＝36、S＝24です。両者は異なるため、まだ終了しません。
- ×ウ 1010回目の比較では L＝12、S＝24です。この比較の後に S から L を引いて両方が12になりますが、その一致を確認するためにもう一度比較します。
- ○エ 1110回の引き算を終えた後、L＝S＝12を判定します。この最後の判定が11回目の比較なので、エの11回が正解です。
POINT
- 図の「L：S」は、大小だけでなく等しいかどうかも調べます。
- L と S が異なる比較の後には、どちらか一方から他方を1回引きます。
- 回数を数えるときは、引き算の回数と比較の回数を区別します。