うごく基本情報

サンプル問題セット(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
abc
アif (x ≠ y)x < yendif
イif (x ≠ y)x > yendif
ウwhile (x ≠ y)x < yendwhile
エwhile (x ≠ y)x > yendwhile

出典:基本情報技術者試験 科目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 手)。「真・偽」は、その行の条件の判定です。

手実行した行変わった値
11行目○整数型: gcd(整数型: num1, 整数型: num2)num1 = 1
num2 = 12
22行目整数型: x ← num1x = 1
33行目整数型: y ← num2y = 12
44行目while (x ≠ y)真
55行目if (x > y)偽
68行目y ← y - xy = 11
74行目while (x ≠ y)真
85行目if (x > y)偽
98行目y ← y - xy = 10
104行目while (x ≠ y)真
115行目if (x > y)偽
128行目y ← y - xy = 9
134行目while (x ≠ y)真
145行目if (x > y)偽
158行目y ← y - xy = 8
164行目while (x ≠ y)真
175行目if (x > y)偽
188行目y ← y - xy = 7
194行目while (x ≠ y)真
205行目if (x > y)偽
218行目y ← y - xy = 6
224行目while (x ≠ y)真
235行目if (x > y)偽
248行目y ← y - xy = 5
254行目while (x ≠ y)真
265行目if (x > y)偽
278行目y ← y - xy = 4
284行目while (x ≠ y)真
295行目if (x > y)偽
308行目y ← y - xy = 3
314行目while (x ≠ y)真
325行目if (x > y)偽
338行目y ← y - xy = 2
344行目while (x ≠ y)真
355行目if (x > y)偽
368行目y ← y - xy = 1
374行目while (x ≠ y)偽
3811行目return x

戻り値:1

サイトで、1行ずつ予想しながら動かす →