サンプル問題セット(2022年12月公開) 科目B 問4
次のプログラム中の[ ]~[ ]に入れる正しい答えの組合せを,解答群の中から選べ。
関数 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 の最大公約数と等しい。
○整数型: gcd(整数型: num1, 整数型: num2)
整数型: x ← num1
整数型: y ← num2
[ a ]
if ([ b ])
x ← x - y
else
y ← y - x
endif
[ c ]
return x
| a | b | c | |
|---|---|---|---|
| ア | if (x ≠ y) | x < y | endif |
| イ | if (x ≠ y) | x > y | endif |
| ウ | while (x ≠ y) | x < y | endwhile |
| エ | while (x ≠ y) | x > y | endwhile |
出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問4
正解と解説を見る
正解:エ
ポイント:引き算のユークリッドの互除法:x と y が等しくなるまで、大きい方から小さい方を引き続ける。
最大公約数は、「大きい方から小さい方を引いても変わらない」という性質を使って求められます。x と y が等しくなるまで引き算を繰り返し、等しくなったらその値が最大公約数です。
何回繰り返すか分からないので、空欄aと空欄cは while (x ≠ y) と endwhile。if にすると引き算が1回しか行われません。
空欄bは、x から y を引く条件なので x > y(x が大きいとき)です。
よって(エ)。例:gcd(12, 8) は (12, 8) → (4, 8) → (4, 4) となり 4 です。
ウ(x < y のとき x ← x - y):小さい方から大きい方を引くので、値が負になり、いつまでも等しくなりません。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。
正解のプログラムを動かしてみる
gcd(1, 12) を呼び出したときに、1行ずつ何が起きるかの表です(全部で 38 手)。「真・偽」は、その行の条件の判定です。
| 手 | 実行した行 | 変わった値 |
|---|---|---|
| 1 | 1行目○整数型: gcd(整数型: num1, 整数型: num2) | num1 = 1 num2 = 12 |
| 2 | 2行目整数型: x ← num1 | x = 1 |
| 3 | 3行目整数型: y ← num2 | y = 12 |
| 4 | 4行目while (x ≠ y) | 真 |
| 5 | 5行目if (x > y) | 偽 |
| 6 | 8行目y ← y - x | y = 11 |
| 7 | 4行目while (x ≠ y) | 真 |
| 8 | 5行目if (x > y) | 偽 |
| 9 | 8行目y ← y - x | y = 10 |
| 10 | 4行目while (x ≠ y) | 真 |
| 11 | 5行目if (x > y) | 偽 |
| 12 | 8行目y ← y - x | y = 9 |
| 13 | 4行目while (x ≠ y) | 真 |
| 14 | 5行目if (x > y) | 偽 |
| 15 | 8行目y ← y - x | y = 8 |
| 16 | 4行目while (x ≠ y) | 真 |
| 17 | 5行目if (x > y) | 偽 |
| 18 | 8行目y ← y - x | y = 7 |
| 19 | 4行目while (x ≠ y) | 真 |
| 20 | 5行目if (x > y) | 偽 |
| 21 | 8行目y ← y - x | y = 6 |
| 22 | 4行目while (x ≠ y) | 真 |
| 23 | 5行目if (x > y) | 偽 |
| 24 | 8行目y ← y - x | y = 5 |
| 25 | 4行目while (x ≠ y) | 真 |
| 26 | 5行目if (x > y) | 偽 |
| 27 | 8行目y ← y - x | y = 4 |
| 28 | 4行目while (x ≠ y) | 真 |
| 29 | 5行目if (x > y) | 偽 |
| 30 | 8行目y ← y - x | y = 3 |
| 31 | 4行目while (x ≠ y) | 真 |
| 32 | 5行目if (x > y) | 偽 |
| 33 | 8行目y ← y - x | y = 2 |
| 34 | 4行目while (x ≠ y) | 真 |
| 35 | 5行目if (x > y) | 偽 |
| 36 | 8行目y ← y - x | y = 1 |
| 37 | 4行目while (x ≠ y) | 偽 |
| 38 | 11行目return x |
戻り値:1