平成31年度 春期 問7

出典:平成31年度 春期 基本情報技術者試験 午前 問7
正解と解説を見る
正解:エ
覚えること:引き算による互除法:大きい方から小さい方を引き続け、等しくなったら終わり。比較の回数を数える。
(L, S) は (876, 204) から、比較のたびに 672, 468, 264, 60(L から S を引く)と変わり、ここで L < S になって S が 144, 84, 24 と減ります。次に L > S で L が 36, 12、最後に L < S で S が 12 になり、L = S = 12 で終了します。比較は 4 + 3 + 2 + 1 + 最後の1回 = 11回です(エ)。最大公約数は 12 です。アの 4 は、L から S を引く最初の4回だけを数えた値です。イの 9 とウの 10 は、比較の回数に数え漏れがあります。
解説はこのサイトが作成したものです。