平成31年度 春期 基本情報技術者試験 午前 問7
テクノロジ／アルゴリズム次の流れ図は，2数A，Bの最大公約数を求めるユークリッドの互除法を，引き算の繰返しによって計算するものである。Aが876，Bが204のとき，何回の比較で処理は終了するか。
出典：平成31年度 春期 基本情報技術者試験 午前 問7
- ア4
- イ9
- ウ10
- エ11
正解：エ
解説
引き算による互除法では，LとSを比較し，大きい方から小さい方を引く操作をL＝Sになるまで繰り返します。A＝876，B＝204から実際にトレースすると，L：Sの比較を11回行った時点でL＝S＝12となり，処理が終了します。
選択肢ごとの解説
- ア誤り。4回では876と204から差を数回引いた段階に過ぎず，まだL＝Sになっていません。
- イ誤り。9回でもまだ差分計算の途中であり，L＝Sには達していません。
- ウ誤り。10回でもあと1回比較が不足しており，L＝Sの状態に至っていません。
- エ正しい。876と204から引き算を繰り返すと，11回目の比較でL＝S＝12となり処理が終了します。