修了試験 2020-06-14実施分 基本情報技術者試験 問4

解説

正解は2です。 ユークリッドの互除法で最大公約数を求める手順をたどる問題です。 手順(2)で剰余を求め、剰余が0になったら1つ前の値が最大公約数です。 手順(2)を実行するたびに1回と数えます。 【計算】 x0＝175、x1＝77 から始めます。 1回目（i＝2）：175÷77＝2余り21なので、x2＝21です。 2回目（i＝3）：77÷21＝3余り14なので、x3＝14です。 3回目（i＝4）：21÷14＝1余り7なので、x4＝7です。 4回目（i＝5）：14÷7＝2余り0なので、x5＝0です。 x5＝0となったので、手順(3)で x4＝7 を最大公約数として終了します。 手順(2)の実行回数は4回です。 【選択肢別解説】 1：× 3回目の時点では剰余が7で、まだ0になっていません。 終了するには4回目の実行が必要です。 2：○ 剰余が0になるのは4回目なので、手順(2)の実行回数は4回です。 3：× 6回は実行回数を多く数えすぎています。 剰余は4回目で0になり、そこで終了します。 4：× 7回は最大公約数の値（7）と混同した数です。 実行回数は4回です。 【ポイント】 互除法は「大きい数を小さい数で割った余りで置き換える」操作を、余りが0になるまで繰り返します。 175＝5²×7、77＝7×11 なので最大公約数が7であることも確かめられます。