ITPEC IP October 2023 Question 9

14 — the loop keeps subtracting the smaller value from the larger until x = y: Euclid's algorithm by subtraction.

The end condition x = y is checked at the top of the loop. Trace (x, y):

• •(98, 42): x > y, so x = 98 − 42 = 56
• •(56, 42): x > y, so x = 56 − 42 = 14
• •(14, 42): x ≤ y, so y = 42 − 14 = 28
• •(14, 28): x ≤ y, so y = 28 − 14 = 14
• •(14, 14): x = y, the loop ends with x = 14

14 is the greatest common divisor of 98 and 42: 98 = 14 × 7, 42 = 14 × 3.

Answer (b)

Why not others:

• •(a) 0 — only a subtraction after x and y became equal gives 0, and it would change y, not x; the end condition stops the loop before that
• •(c) 28 — the value of y after the third pass, not a final value
• •(d) 56 — x after the first pass; the loop runs on because 56 ≠ 42

Key rule: A pre-test loop checks its end condition before each pass; repeatedly subtracting the smaller number from the larger ends with both equal to the greatest common divisor.

Algorithm and Programming · AI-written, may contain errors