アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20220612 実施分 問5
与えられた正の整数 x₀，x₁（x₀＞x₁）の最大公約数を，次の手順で求める。x₀＝175，x₁＝77の場合，手順（2）は何回実行するか。ここで，“A ← B”は，BをAに代入することを表す。
〔手順〕
（1）i ← 2
（2）xᵢ ← “xᵢ₋₂をxᵢ₋₁で割った剰余”
（3）xᵢ＝0ならばxᵢ₋₁を最大公約数として終了する。
（4）“i ← i＋1”として（2）に戻る。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20220612 実施分 問5（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、割り算の余りで大きい方を置き換えて余りが0になるまで繰り返し最大公約数を求める。
この問題で必要なこと
175,77で剰余を繰り返す: 21,14,7,0の4回で余りが0になり、手順(2)は4回実行される。
ひっかけ
終了判定の回数の数え方(0になる回を含めるか)を誤らせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）。頻出知識ランキング46位（全1,254件中）。