题目

Problem

Figure 2 shows the flowchart for an algorithm.

The input for the algorithm is two positive integers.

The function INT(X) is the largest integer less than or equal to X.

(a) Complete the table in the answer book, with $a = 1980$ and $b = 462$ , showing the results at each step of the algorithm.

(4)

(b) Explain how the output, $h$ , relates to the inputs, $a$ and $b$ .

(1)

题目中文翻译

图 2 显示了算法的流程图。

算法的输入是两个正整数。

函数 INT(X) 是小于或等于 X 的最大整数。

(a) 在答案本中完成表格，取 $a = 1980$ 和 $b = 462$ ，显示算法每一步的结果。

(b) 说明输出 $h$ 与输入 $a$ 和 $b$ 的关系。

解答

展开

先只计算一次 $c=ab$ ，之后沿循环依次计算商 $d$ 、整数部分 $e$ 、乘积 $f$ 与余数 $g$ 。若 $g\ne0$ ，用旧的 $b$ 与余数 $g$ 更新 $a,b$ ；只有当 $g=0$ 时才计算 $h=c/b$ 并输出。

展开

Initially,

c=1980\times462=914760.

Following the flowchart gives

$a$	$b$	$c$	$d=a/b$	$e=\operatorname{INT}(d)$	$f=be$	$g=a-f$	$h$
1980	462	914760	$30/7$	4	1848	132	-
462	132	914760	$7/2$	3	396	66	-
132	66	914760	$2$	2	132	0	13860

At the final step,

h=\frac{914760}{66}=13860.

Therefore, the output is

\boxed{13860}.

展开

循环部分是欧几里得算法：当余数首次变为 0 时，此时的 $b$ 是两个输入的最大公因数。由于 $c$ 始终等于两个原输入的乘积，所以输出 $c/b$ 等于“乘积除以最大公因数”，即最小公倍数。

展开

The loop applies the Euclidean algorithm, so when $g=0$ , the current value of $b$ is the highest common factor of the two original inputs.

Since $c$ is their product,

h=\frac{ab}{\gcd(a,b)}=\operatorname{lcm}(a,b),

Hence $h$ is the

\boxed{\text{lowest common multiple of the two inputs}}.