基本情報科目Bサンプル問題：問4　ユークリッドの互除法を解説｜最大公約数の求め方

次のプログラム中の 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) 片方の数が大きい場合、大きい数から小さい数を引いても最大公約数は変わりません。
• (3) 逆にもう片方が大きい場合でも同様です。

これらは、ユークリッドの互除法に基づいています。

プログラムの動作解析

1. 初期化
   x に num1 を、y に num2 を代入しています。
2. 繰り返し条件
   x と y が等しい場合に処理を終了する必要があります。
   • よって、while (x ≠ y) の形式が正しい。
3. 条件分岐
   x が y より大きい場合には x ← x - y、それ以外の場合には y ← y - x を実行します。
   • これは (2) と (3) の性質に対応。

選択肢の検討

ア: if (x ≠ y) x ＜ y endif

• 条件が単一の if 文で、x ≠ y を判定しています。
• しかし、この形式ではループ構造になっておらず、繰り返し計算を行いません。

イ: if (x ≠ y) x ＞ y endif

• 同様に単一の if 文で、ループ構造を欠いています。
• 最大公約数を求めるための継続的な計算が実現されません。

ウ: while (x ≠ y) x ＜ y endwhile

• ループ構造が適切ですが、条件が x < y と記述されており、逆の操作ができません。

エ: while (x ≠ y) x ＞ y endwhile

• ループ構造が適切で、x ≠ y が正しく設定されています。
• また、x > y の条件に応じて処理が切り替わり、期待する動作を満たします。

答え

正しい答えは エ: while (x ≠ y) x ＞ y endwhile です。