問題
与えられた正の整数 x₀，x₁（x₀＞x₁）の最大公約数を、次の手順で求める。x₀＝175，x₁＝77 の場合、手順 (2) は何回実行するか。ここで、"A→B" は、A を B に代入することを表す。 〔手順〕 (1) 2→i (2) xᵢ₋₂ を xᵢ₋₁ で割った剰余→xᵢ (3) xᵢ＝0 ならば、xᵢ₋₁ を最大公約数として終了する。 (4) i＋1→i として (2) に戻る。
選択肢
- 13
- 24
- 36
- 47
正解
2. 4
詳しい解説を見る解説を閉じる
解説
ユークリッドの互除法である。175÷77 余り 21（1 回目）、77÷21 余り 14（2 回目）、21÷14 余り 7（3 回目）、14÷7 余り 0（4 回目）で剰余が 0 となり終了する。手順 (2) は 4 回実行されるため、イが正しい。（出典: 平成24年度 秋期 基本情報技術者試験 午前 問2）
一問一答
科目A 180問+科目B 60問