Programming Basics (Pseudocode Tracing)
The following program subtracts the two integers a and b from each other until they are equal. What is the value of k after it runs?
integer: 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
Show answer and explanation
Answer: B. 4
This is the subtraction form of Euclid's algorithm: subtract the smaller value from the larger until the two are equal. (a, b) changes as (48, 18) → (30, 18) → (12, 18) → (12, 6) → (6, 6), four subtractions, so k = 4. The final a = b = 6 is the greatest common divisor. Euclid's algorithm with the remainder (mod) needs only three steps: 48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0.
- A. This is the number of steps of Euclid's algorithm using mod. This program uses subtraction.
- B. Correct. Four steps from (48, 18) to (6, 6).
- C. This is the greatest common divisor a = b = 6, not the value of k.
Continue: 9 more Programming Basics (Pseudocode Tracing) questions