基本情報技術者試験のサンプル問題を解こう！（8）（科目B）「最大公約数を求める」

基本情報技術者試験のサンプル問題（科目B）を解いてみよう。

今回のテーマは、「最大公約数を求める」である。

ユークリッドの互除法（二つの正の整数の最大公約数を繰り返し引き算する古典的アルゴリズム）を疑似コードで実装する問題である。

問題文を確認しよう

• 関数 gcd(num1, num2) は、x ← num1、y ← num2 とする。
• その後、(a)〜(c) の穴埋めを含む処理があり、最終的に return x となっている。
• 問題文で示された最大公約数の性質は以下の通りである。

1. num1 == num2 のとき、最大公約数はその値。
2. num1 > num2 のとき、gcd(num1-num2, num2) と同じ。
3. num2 > num1 のとき、gcd(num1, num2-num1) と同じ。

(a) はループ条件

• 性質(1) より、「x と y が等しくなるまで繰り返す」必要がある。
• したがって (a) には 繰り返し処理が必須となる。 → while (x ≠ y)が選ばれるべき。

(b) は比較条件

• 性質(2) と (3) に従い、
  • x > y のとき x ← x - y （num1 > num2）
  • x < y のとき y ← y - x （num1 < num2）
• よって (b) は x > y が正しい。

(c) はループ終了のための文

• while を選んだ以上、終わりを示す必要があるので (c) には endwhileが入る。

正しい組み合わせ

(a) while (x ≠ y)
(b) x > y
(c) endwhile

この組み合わせで、x == y となるまで差を取り続け、その値が最大公約数として return x される。

動作例（36 と 60 で確認しよう）

1. x = 36, y = 60 → x < y → y = 60 − 36 = 24
2. x = 36, y = 24 → x > y → x = 36 − 24 = 12
3. x = 12, y = 24 → x < y → y = 24 − 12 = 12
4. x = 12, y = 12 → ループ終了 → return 12 が最大公約数

補足

• これは最も基本的な「引き算版」ユークリッド互除法である。
• 「剰余（%）」を使う形式もあるが、本問は繰り返し引き算型での出題である。