Consider the following C program C main() { int x, y, m, n; scanf ("%d %d",…
2004
Consider the following C program
C
main()
{
int x, y, m, n;
scanf ("%d %d", &x, &y);
/* Assume x > 0 and y > 0 */
m = x;
n = y;
while (m! = n)
{
if (m > n)
m = m - n;
else
n = n - m;
}
print f ("% d", n);
}
The program computes
- A.
x ÷ y using repeated subtraction
- B.
x mod y using repeated subtraction
- C.
the greatest common divisor of x and y
- D.
the least common multiple of x and y
Attempted by 88 students.
Show answer & explanation
Correct answer: C
Answer: computes the greatest common divisor (GCD) of x and y.
Start: the program sets m = x and n = y (assume x > 0 and y > 0).
Loop: while m != n, replace the larger of m and n by the difference between them (if m > n then m = m - n else n = n - m).
Invariant: each subtraction step preserves the greatest common divisor. That is, gcd(m, n) remains equal to gcd(x, y) after every assignment because gcd(a, b) = gcd(a - b, b) when a > b.
Termination: the loop stops when m == n. Call this common value g. Since gcd(m, n) = gcd(x, y) and m = n = g, g must be gcd(x, y).
Output: the program prints n (which equals m), so it prints the greatest common divisor of x and y.
Example: x = 12, y = 8 -> m=12,n=8 -> m>n so m=4 -> now m=4,n=8 -> n>m so n=4 -> now m=n=4, loop ends and 4 is printed; 4 = gcd(12,8).