ITPEC IP October 2023 Question 5
As shown in Figure 1, there is a processing unit which reads two positive integer input values A1 and A2, and then writes two integer output values B1 and B2. B1 is equal to A2, and B2 is the remainder of A1 divided by A2. In Figure 2, two processing units with the same function as the above are connected in series. When A1=15 and A2=6 are given to the left-hand unit in Figure 2, what is the output value of B1 for the right-hand unit?
Figure 1
Figure 2
Explanation
3 — the left unit outputs 6 and 3, which become the right unit's A1 and A2, and B1 copies A2.
Each unit sets B1 to A2 and B2 to the remainder of A1 ÷ A2. In Figure 2 the left unit's B1 and B2 feed the right unit's A1 and A2:
- •Left unit: A1 = 15, A2 = 6, so B1 = 6 and B2 = remainder of 15 ÷ 6 = 3
- •Right unit: A1 = 6, A2 = 3, so B1 = 3 and B2 = remainder of 6 ÷ 3 = 0
Answer (b)
Why not others:
- •(a) 0 — the right unit's B2, the remainder of 6 ÷ 3, not its B1
- •(c) 6 — the left unit's B1; it becomes the right unit's A1, which is not copied to B1
- •(d) 15 — the original A1; the left unit uses it only to compute the remainder and passes it on nowhere
Key rule: Each unit is one step of Euclid's algorithm, turning (A1, A2) into (A2, remainder of A1 ÷ A2); chained until the remainder is 0, the last B1 is the greatest common divisor, here 3 for 15 and 6.
Algorithm and Programming · AI-written, may contain errors
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 IP past-paper collection or Report an issue.