ITPEC FE Morning April 2021 Question 3

Topic: Algorithm and Programming

The GCD (Greatest Common Divisor) of two positive integers, x0 and x1 (x0 > x1), is computed by the procedure below. When x0 = 175 and x1 = 77, how many times should step (2) of this procedure be executed before it stops? Here, “A ← B” indicates that B is substituted for A.

[Procedure]

(1)i ← 2(2)xi ← remainder of xi−2 divided by xi−1(3)if xi = 0, stop with xi−1 as the GCD(4)i ← i + 1(5)return to step (2)

Explanation

4 times — step (2) runs once for every remainder, including the final 0 that stops the procedure.

Trace with x0 = 175, x1 = 77:

  • •i = 2: x2 = remainder of 175 ÷ 77 = 21 (175 = 2 × 77 + 21)
  • •i = 3: x3 = remainder of 77 ÷ 21 = 14 (77 = 3 × 21 + 14)
  • •i = 4: x4 = remainder of 21 ÷ 14 = 7
  • •i = 5: x5 = remainder of 14 ÷ 7 = 0, so step (3) stops with x4 = 7 as the GCD

Step (2) ran for i = 2, 3, 4 and 5.

Answer (b)

Why not others:

  • •(a) 3 — stops counting at the remainder 7, the GCD, but the procedure only learns that 7 is the GCD by running step (2) once more and getting 0
  • •(c) 6 — no reading of the trace gives six remainders: they fall 21, 14, 7, 0
  • •(d) 7 — the GCD itself, not the number of times step (2) ran

Key rule: In Euclid's algorithm count the division that leaves remainder 0 too, because that is the step that proves the previous remainder is the GCD.

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.