修了試験 2022-06-12実施分 基本情報技術者試験 問5
与えられた正の整数x_0，x_1（x_0＞x_1）の最大公約数を，次の手順で求める。 x_0＝175，x_1＝77の場合，手順(2)は何回実行するか。 ここで，"A←B"は，BをAに代入することを表す。 〔手順〕 (1) i←2 (2) x_i←"x_i-2をx_i-1で割った剰余" (3) x_i＝0ならばx_i-1を最大公約数として終了する。 (4) "i←i＋1"として(2)に戻る。
正答2
解説
正解はイ。 x_0=175，x_1=77としてx_i=x_(i-2) mod x_(i-1)を計算すると，x_2=175 mod 77=21，x_3=77 mod 21=14，x_4=21 mod 14=7，x_5=14 mod 7=0となり，最大公約数7を得る。 手順(2)はi=2から5まで計4回実行される。まとめて解く
修了試験 2022-06-12実施分を通しで解く（80問）→