IPA FE Subject B sample Question 4

Topic: Math & Numbers

A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問4, translated into English. ITPEC is based on the same exams.

From the answer group below, select the correct combination of answers to be inserted into A through C in the program.

The function gcd finds the greatest common divisor of the two positive integers num1 and num2 given as arguments, by using the properties (1) through (3) below.

(1)When num1 and num2 are equal, the greatest common divisor of num1 and num2 is num1.(2)When num1 is greater than num2, the greatest common divisor of num1 and num2 is equal to the greatest common divisor of (num1 - num2) and num2.(3)When num2 is greater than num1, the greatest common divisor of num1 and num2 is equal to the greatest common divisor of (num2 - num1) and num1.
[Program]
○ integer: gcd(integer: num1, integer: num2)
integer: x ← num1
integer: y ← num2
A
if (B)
x ← x - y
else
y ← y - x
endif
C
return x

Answer group

OptionABC

Explanation

A: while (x ≠ y), B: x > y, C: endwhile — the subtraction must repeat until the two values meet, each time taking the smaller value from the larger.

Property (1) is where the work stops: once x and y are equal, x is the answer, so the block runs while x ≠ y and return x follows it. Properties (2) and (3) are one step each: when x is the larger, x is replaced by x - y (the if branch); otherwise y is replaced by y - x (the else branch). So the condition is x > y. Each step keeps the greatest common divisor unchanged and makes one value smaller, so the two values must meet, at the greatest common divisor.

Trace gcd(12, 18): 12 is not greater than 18, so y ← 6; 12 > 6, so x ← 6; now x = y = 6, the loop ends, and 6 is returned.

Answer (d)

Why not others:

  • •(a) and (c) — x < y subtracts the larger value from the smaller: in gcd(12, 18), x becomes −6; (a) returns −6, and in (c) the values never meet, so the loop does not end
  • •(b) — the right step, but done only once: gcd(12, 18) makes y 6 and returns 12

Key rule: Euclid's algorithm by subtraction repeats "larger minus smaller" while the two values differ; a single if does only one step, and the value reduced must be the larger one.

Math & Numbers · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.