平成24年度 秋期 基本情報技術者試験 午前 問2
テクノロジ／アルゴリズム与えられた正の整数x0，x1（x0＞x1）の最大公約数を，次の手順で求める。x0＝175，x1＝77の場合，手順(2)は何回実行するか。ここで，“A→B”は，AをBに代入することを表す。 〔手順〕 (1) 2→i (2) xi-2をxi-1で割った剰余→xi (3) xi＝0ならばxi-1を最大公約数として終了する。 (4) i＋1→iとして(2)に戻る。
出典：平成24年度 秋期 基本情報技術者試験 午前 問2
- ア3
- イ4
- ウ6
- エ7
正解：イ
解説
この手順はユークリッドの互除法です。x0＝175，x1＝77として順に剰余を計算すると，x2＝175 mod 77＝21，x3＝77 mod 21＝14，x4＝21 mod 14＝7，x5＝14 mod 7＝0となり，x5＝0が成立した時点で終了します。手順(2)はi＝2，3，4，5の4回実行されます。
選択肢ごとの解説
- ア誤り。剰余計算を1回省略するなど途中で終了と誤判定した場合の回数です。
- イ正しい。175→77→21→14→7→0と剰余を求める過程で，手順(2)は4回（i＝2,3,4,5）実行されます。
- ウ誤り。初期のiの値を数えに含めるなど，カウントの起点を誤った場合の回数です。
- エ誤り。手順(3)や(4)の実行回数と混同した場合などに生じる回数です。