修了試験 2022-06-12実施分 基本情報技術者試験 問5

解説

正解は2です。 この手順はユークリッドの互除法で、前の2つの値の剰余を次々に求め、剰余が0になったときの直前の値を最大公約数とします。 手順(2)で剰余を求めるたびに回数を数えます。 【計算】 x_0＝175、x_1＝77から始めます。 1回目（i＝2）は175÷77の剰余で、x_2＝21です。 x_2は0ではないので続けます。 2回目（i＝3）は77÷21の剰余で、x_3＝14です。 3回目（i＝4）は21÷14の剰余で、x_4＝7です。 4回目（i＝5）は14÷7の剰余で、x_5＝0です。 x_5＝0になったので、x_4＝7を最大公約数として終了します。 手順(2)は合計4回実行されます。 【選択肢別解説】 1：× 3回の時点ではx_4＝7で、まだ剰余は0になっていません。 剰余が0になることを確かめる4回目が必要です。 2：○ i＝2、3、4、5の4回で剰余が0になり、終了します。 175と77の最大公約数は7です。 3：× 6回は実際の実行回数より多い値です。 4回目で剰余が0になった時点で手順(3)により終了します。 4：× 7回は最大公約数の値7と回数を取り違えた値と考えられます。 問われているのは手順(2)の実行回数です。 【ポイント】 互除法では、最後に0になる剰余を求める回も手順(2)の実行回数に含めます。 数え漏れを防ぐには、iの値と剰余を1行ずつ書き出すのが確実です。