修了試験 2012-12-16実施分 基本情報技術者試験 問6

解説

正解は4です。 流れ図では、最初にAをL、BをSに入れ、LとSを比較します。 L>SならL-SをLに、L<SならS-LをSに入れて比較に戻ります。 L=Sになったら終了し、そのLが最大公約数です。 比較の回数を、比較ごとに1回として数えます。 【計算】 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となり、処理を終了します。 最大公約数は12で、比較は11回です。 【選択肢別解説】 1：× 4回は、Lから204を引く処理を4回繰り返した時点です。 まだL=60、S=204で終了していません。 2：× 9回目の比較の後はL=12、S=24で、まだ等しくありません。 処理は続きます。 3：× 10回目の比較の後にL=S=12となりますが、それを判定する比較がもう1回必要です。 4：○ 等しいことを確認する最後の比較を含め、比較は11回行われます。 【ポイント】 終了判定の「=」になる比較も1回に数えることを忘れないようにします。 引き算の互除法は、割り算の互除法で商の回数だけ引き算を繰り返すことに相当します。