基本情報技術者 2012年 秋期 午前（科目A） 問02

要点まとめ

• 結論：与えられた初期値 $x_0=175$, $x_1=77$ に対する手順(2)の実行回数は合計で 4 回であり、よって正解は イ です。
• 根拠：ユークリッドの互除法で順に余りを計算すると $x_2=175\mathrm{mod}77=21$, $x_3=77\mathrm{mod}21=14$, $x_4=21\mathrm{mod}14=7$, $x_5=14\mathrm{mod}7=0$ となり、余り計算は 4 回で終了します。
• 差がつくポイント：i の初期値や「手順(2) を何回数えるか」の定義（余りを計算した回数＝手順(2) の回数）に注意し、最終的に 0 を得た回まで数えることが重要です。

正解の理由

よくある誤解

• 「最初の代入（i=2 の設定）を手順(2) の実行に含めない」：i の初期化は手順(1) であり、実際の余り計算が行われた回数を数えます。
• 「最後に最大公約数を出した時点（最後の非零余り）を数えない」：0 になった余りを作り出した手順(2) もカウントします。
• 「余りの計算順序や添字のずれ」：$x_{i-2}\mathrm{mod}{x}_{i-1}$ の添字関係を誤ると回数や値が変わるので注意が必要です。

解法ステップ

1. 初期設定：$x_0=175$, $x_1=77$, i=2。
2. 手順(2): $x_2=175\mathrm{mod}77=21$（手順(2) 回数 = 1）。$x_2\ne 0$ のため継続。
3. i=3：$x_3=77\mathrm{mod}21=14$（手順(2) 回数 = 2）。$x_3\ne 0$ のため継続。
4. i=4：$x_4=21\mathrm{mod}14=7$（手順(2) 回数 = 3）。$x_4\ne 0$ のため継続。
5. i=5：$x_5=14\mathrm{mod}7=0$（手順(2) 回数 = 4）。$x_5=0$ なので終了し、最大公約数は $x_4=7$。
6. 結果：手順(2) の実行回数は 4 回 → 選択肢 イ。

選択肢別の誤答解説

• ア: 3 — おそらく最後に 0 を出した余りの計算（$14\mathrm{mod}7=0$）を数えていない誤りです。
• イ: 正解 — 余りを求めた回数が $x_2,x_3,x_4,x_5$ の 4 回であり正しいカウントです。
• ウ: 6 — 不要に追加の計算を数えたり、i の更新や初期化を複数回誤カウントした結果の過大評価です。
• エ: 7 — 余り計算以外の代入操作（i の更新など）を手順(2) の回数に含める誤りで、過剰に数えています。

補足コラム

def count_remainders(a, b):
    count = 0
    while True:
        r = a % b
        count += 1
        if r == 0:
            return count, b  # (手順(2)の回数, gcd)
        a, b = b, r

print(count_remainders(175, 77))  # (4, 7)

FAQ