次のプログラム中の a , b , c に入れる正しい答えの組合せを，解答群の中から選べ。

関数 gcd は，引数で与えられた二つの正の整数 num1 と num2 の最大公約数を，次の(1)～(3) の性質を利用して求める。

• (1) num1 と num2 が等しいとき，num1 と num2 の最大公約数は num1 である。
• (2) num1 が num2 より大きいとき，num1 と num2 の最大公約数は，(num1 － num2) と num2 の最大公約数と等しい。
• (3) num2 が num1 より大きいとき，num1 と num2 の最大公約数は，(num2 － num1) と num1 の最大公約数と等しい。

---

問題解説

この問題では、提示された3つの性質を用いて、2つの数値の最大公約数を求めるプログラムの空欄を埋めます。

1. アルゴリズムの核心：ユークリッドの互除法

この性質（大きい方から小さい方を引き続ける）は、ユークリッドの互除法（の減法バージョン）に基づいています。最終的に2つの数値が等しくなったとき、その値が最大公約数となります。

2. プログラムの動作解析

1. 初期化 x に num1 を、y に num2 を代入してスタートします。
2. 繰り返し条件（aの部分） 性質(1)より、x と y が等しくなれば終了です。つまり、等しくない間はずっと処理を繰り返す必要があります。
   • よって、while (x ≠ y) が入ります。
3. 条件分岐（bの部分） x と y を比較して、大きい方から小さい方を引く処理を分岐させます。
   • x > y であれば、x を更新 (x ← x - y)。
   • そうでなければ、y を更新 (y ← y - x)。

3. 選択肢の検討

• ア・イ: if 文（条件分岐）のみ。これでは1回しか計算が行われず、数値が等しくなるまで繰り返せません。
• ウ: ループ条件は良いですが、中の条件が x < y となっています。これでも論理的に組めますが、解答群の組み合わせとして最も自然な構造（xが大きい時にxを引く）は「エ」になります。
• エ: while (x ≠ y) で繰り返し、x > y の条件に応じて x または y を更新します。これが問題の性質 (2) と (3) を完璧に再現しています。

正解

正しい答えは エ: a=while (x ≠ y), b=x ＞ y, c=endwhile です。

まとめ

ユークリッドの互除法は、通常「余り（モジュロ演算）」を使って一気に計算しますが、この問題のように「引き算の繰り返し」で考えるのが基本形です。ループの終了条件が「等しくなったとき」であることを押さえておきましょう！