プログラミングの基礎(擬似言語のトレース)
2つの整数 a、b を引き算で等しくしていく次のプログラムを実行した後の k の値はどれか。
整数型: a ← 48, b ← 18, k ← 0
while (a ≠ b)
if (a > b)
a ← a − b
else
b ← b − a
endif
k ← k + 1
endwhile- A3
- B4
- C6
答えと解説を見る
正解：B. 4
大きい方から小さい方を引くことを、2つが等しくなるまで繰り返す、引き算によるユークリッドの互除法です。(a, b) は (48, 18) → (30, 18) → (12, 18) → (12, 6) → (6, 6) と変わり、引き算は4回なので k = 4 です。最後の a = b = 6 が最大公約数です。剰余(mod)を使う互除法なら、48 mod 18 = 12、18 mod 12 = 6、12 mod 6 = 0 の3回で済みます。
- A. mod を使う互除法の繰返しの回数です。このプログラムは引き算を使います。
- B. 正しい。(48, 18) から (6, 6) になるまでの4回です。
- C. 最大公約数 a = b = 6 の値で、k の値ではありません。