最大公約数を求めるプログラム

■ 解き方の方針 問題文の三つの性質を、そのまま繰返し条件、大小判定、繰返しの終端へ対応させます。処理の基本は、大きい方から小さい方を引き、二つの値を等しくすることです。 ■ 空欄aとc:いつまで繰り返すか 性質(1)より、xとyが等しくなったとき、その値が最大公約数です。したがって、等しくない間は処理を繰り返します。 a: while (x ≠ y) c: endwhile ■ 空欄b:どちらから引くか ifが真のときはx ← x - yを実行します。この計算を行うのはxの方が大きい場合なので、bは x > y です。そうでなければy > xなので、else側でy ← y - xを実行します。 ■ 処理が正しい理由 大きい方から小さい方を引いても、問題文の性質(2)、(3)により最大公約数は変わりません。値は正のまま小さくなり、最終的にx=yとなって、その共通値を返します。 ■ 正解と誤答の見分け方 したがって、正解は エ です。 ifでは1回しか引けないため不十分です。またx < yのときにx ← x - yを実行すると、正の値を保てません。

次のプログラム中の a ~ 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の最大公約数と等しい。

[プログラム]
 ○整数型:gcd(整数型: num1, 整数型: num2)
 整数型: x←num1
 整数型: y←num2
  a 
  if ( b )
  x←x-y
 else
  y←y-x
 endif
  c 
 return x

出典令和4年度 基本情報技術者試験 科目B サンプル問題 問4

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