ITPEC FE Morning October 2020 Question 8

Topic: Algorithm and Programming

The flowchart below calculates the greatest common divisor of two (2) numbers, A and B, using the Euclidean algorithm with repeated subtraction. When A is 876 and B is 204, how many comparisons are required to obtain the result?

StartLASBL(L − S)S(S − L)L : SoutputA, B, LEnd

Explanation

11 comparisons — the diamond L : S runs once before every subtraction and once more for the final L = S that ends the loop.

Start with L = 876, S = 204:

ComparisonsResultAction
1–4L > SL: 876 → 672 → 468 → 264 → 60
5–7L < SS: 204 → 144 → 84 → 24
8–9L > SL: 60 → 36 → 12
10L < SS: 24 → 12
11L = Soutput L = 12, end

That is 10 subtractions plus the final equality test: 11 comparisons.

Answer (d)

Why not others:

  • •(a) 4 — the number of steps in the division form of Euclid's algorithm (876 mod 204 = 60, 204 mod 60 = 24, 60 mod 24 = 12, 24 mod 12 = 0), not this subtraction flowchart
  • •(b) 9 — matches no consistent count of the trace; even the subtractions alone number 10
  • •(c) 10 — counts only the comparisons that lead to a subtraction and misses the last one, where L = S ends the loop

Key rule: When counting loop tests, include the final test that exits the loop: k passes through the body need k + 1 tests.

Algorithm and Programming · AI-written, may contain errors

Practice this exam

This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.