Consider the following pseudo-code fragment in which an invariant for the loopβ¦
2019
Consider the following pseudo-code fragment in which an invariant for the loop is βΒ \(m ^*x^k=p^n\) andΒ \(πβ₯0\)Β β (here,Β \(π\)Β andΒ \(π\)Β are integer variable that have been initialized):
/* Pre-conditions :Β \(p \geq 1 \wedge n \geq 0\) */
/* Assume that overflow never occurs */
intΒ \(π₯=π;\) intΒ \(π=π\); intΒ \(π=1\);
whileΒ \((π<>0\))Β {
if (k is odd) thenΒ \(π=πβπ₯\);
\(π₯=π₯βπ₯\);
\(k=\lfloor k/2 \rfloor\);Β Β Β Β /* floor(\(π/2\))Β */
}
Which of the following must be true ar the end of the while loop?
π₯=ππ
π=ππ
π=π₯π
π=ππ
Answer: B. \(m=p^n\) β Answer: m = p^n Reasoning using the loop invariant: Invariant: m * x^k = p^n and k β₯ 0. Initially x = p, k = n, m = 1, so the invariant holds: 1 * p^n = p^n.β¦
- A.
\(x=p^n\) - B.
\(m=p^n\) - C.
\(p=x^n\) - D.
\(p=m^n\)
Attempted by 380 students.
Show answer & explanation
Correct answer: B
Answer: m = p^n
Reasoning using the loop invariant:
Invariant: m * x^k = p^n and k β₯ 0. Initially x = p, k = n, m = 1, so the invariant holds: 1 * p^n = p^n.
Maintenance when k is odd: write k = 2q + 1. After the updates m' = m * x, x' = x^2, k' = q. Then m' * x'^{k'} = (m * x) * (x^2)^q = m * x^{2q+1} = m * x^k, so the invariant is preserved.
Maintenance when k is even: write k = 2q. Then m remains the same, x' = x^2, k' = q, and m * x'^{k'} = m * (x^2)^q = m * x^{2q} = m * x^k, so the invariant is preserved.
Termination: the loop stops when k = 0. Plugging into the invariant gives m * x^0 = p^n, so m = p^n. Thus m holds the value p^n at loop end.
Notes on the other statements:
x = p^n is not generally true at termination; x is repeatedly squared and may end up as a higher power of p. For example, p = 2, n = 3 yields final x = 16 while p^n = 8.
p = x^n and p = m^n are not implied by the invariant or the updates and are false in general (see small numeric counterexamples above).
A video solution is available for this question β log in and enroll to watch it.