アルゴリズムとプログラミング
平成24年度 秋期 基本情報技術者試験 午前 問2
与えられた正の整数 x_0，x_1（x_0 > x_1）の最大公約数を，次の手順で求める。x_0=175，x_1=77 の場合，手順 (2) は何回実行するか。ここで，“A → B” は，A を B に代入することを表す。
〔手順〕
(1) 2 → i
(2) x_{i-2} を x_{i-1} で割った剰余 → x_i
(3) x_i=0 ならば x_{i-1} を最大公約数として終了する。
(4) i+1 → i として (2) に戻る。
- ア 3
- イ 4
- ウ 6
- エ 7
出典：平成24年度 秋期 基本情報技術者試験 午前 問2
答えと解説を見る
正解：イ
覚える知識
ユークリッドの互除法のトレースと初期値関係
ユークリッドの互除法は、割る数と余りを入れ替えながら剰余が0になるまで繰り返し、最後の割る数を最大公約数とする。
この問題で必要なこと
175,77から剰余を順に求めると21,14,7,0となり、手順(2)は4回実行される。
ひっかけ
余りが0になった回と、最大公約数を得た時点の数え方を取り違えさせる。
この知識の出題：本試験系 6 回・免除試験 19 回（公開問題での観測値）