ITPEC FE Morning October 2020 Question 8
ITPEC FE Morning October 2020 — Question 8 of 80
Euclidean Algorithm (Subtraction) — count comparisons in a GCD flowchart.
Trace with A = 876, B = 204:
- •Initialize:
L = 876,S = 204 - •Each diamond
L : Sis one comparison - •If
L > S:L ← L - S - •If
L < S:S ← S - L - •If
L = S: output result and stop
Trace:
- Comparisons 1–4: L shrinks: 876 → 672 → 468 → 264 → 60
- Comparisons 5–7: S shrinks: 204 → 144 → 84 → 24
- Comparisons 8–9: L shrinks: 60 → 36 → 12
- Comparison 10: S shrinks: 24 → 12
- Comparison 11: L = S = 12 → output
Answer: 11 comparisons → (d)
Why not others:
- (a) 4 — only counts the first phase of subtractions
- (b) 9 — misses last two comparisons
- (c) 10 — forgets to count the final equality check
Key rule: The final L = S check is also a comparison — every pass through the decision diamond counts.
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
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.