修了試験 2015-07-26実施分 基本情報技術者試験 問7

解説

正解は4です。 引き算を繰り返すユークリッドの互除法の流れ図をたどり、比較の回数を数える問題です。 流れ図では、最初にAをLに、BをSに代入します。 LとSを比較し、L＞SならL－SをLに、L＜SならS－LをSに代入して比較に戻ります。 L＝Sになったら終了し、そのLが最大公約数です。 【計算】 1回目：L＝876、S＝204でL＞Sなので、L＝672になります。 2回目：L＝672＞S＝204なので、L＝468になります。 3回目：L＝468＞S＝204なので、L＝264になります。 4回目：L＝264＞S＝204なので、L＝60になります。 5回目：L＝60＜S＝204なので、S＝144になります。 6回目：L＝60＜S＝144なので、S＝84になります。 7回目：L＝60＜S＝84なので、S＝24になります。 8回目：L＝60＞S＝24なので、L＝36になります。 9回目：L＝36＞S＝24なので、L＝12になります。 10回目：L＝12＜S＝24なので、S＝12になります。 11回目：L＝12＝S＝12なので、処理は終了します。 比較の回数は11回で、最大公約数は12です。 【選択肢別解説】 1：× 4回目の比較の時点ではL＝264、S＝204で、まだ等しくありません。 2：× 9回目の比較の後もL＝12、S＝24で、処理は続きます。 3：× 10回目の比較の後にL＝S＝12となりますが、等しいことを確認する比較がもう1回必要です。 4：○ 11回目の比較でL＝Sが確認されて終了するので、11回が正しい回数です。 【ポイント】 終了判定の「＝」も1回の比較として数えることを忘れないようにします。 876と204の最大公約数が12であることは、876＝12×73、204＝12×17から確かめられます。