修了試験 2016-12-11実施分 基本情報技術者試験 問7

解説

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