修了試験 2018-01-28実施分 基本情報技術者試験 問3

解説

正解は2です。 ユークリッドの互除法で最大公約数を求める手順を、実際にたどる問題です。 手順(2)で剰余を計算し、剰余が0になった時点で終了します。 【計算】 手順(1)で、iに2を代入します。 1回目の手順(2)では、175を77で割った剰余21をx_2に代入します。 x_2は0ではないので、手順(4)でiを3にします。 2回目の手順(2)では、77を21で割った剰余14をx_3に代入し、iを4にします。 3回目の手順(2)では、21を14で割った剰余7をx_4に代入し、iを5にします。 4回目の手順(2)では、14を7で割った剰余0をx_5に代入します。 手順(3)でx_5＝0となるので、x_4＝7を最大公約数として終了します。 手順(2)は4回実行されています。 【選択肢別解説】 1：× 3回目の時点ではx_4＝7で、まだ剰余は0になっていません。 終了するには4回目の剰余計算が必要です。 2：○ 剰余は21、14、7、0と変化し、4回目で0になって終了します。 3：× 6回は実行回数を数え過ぎています。 4回目で剰余が0になり、手順は終了します。 4：× 7は求めた最大公約数の値であり、手順(2)の実行回数ではありません。 【ポイント】 互除法は、割られる数を割る数で割り、割る数と剰余で同じ計算を繰り返す方法です。 剰余が0になったときの割る数が最大公約数になります。