CSP-J 2020 第一轮 第 6 题：递归算法XYZ的输出含义

题目

设 $A$ 是 $n$ 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])
1.  if n=1 then return A[1]
2.  else temp ← XYZ (A[1..n-1])
3.  if temp < A[n]
4.  then return temp
5.  else return A[n]

 请问算法 XYZ 的输出是什么？（）。

选项

• A. A 数组的平均
• B. A 数组的最小值
• C. A 数组的中值
• D. A 数组的最大值

答案

B

题解

答案是 B. A 数组的最小值。

算法每次都返回较小的数：

• 当数组只有一个元素时，返回 A[1]，它就是最小值。
• 当数组有多个元素时，先递归求出前 n-1 个元素的最小值 temp，再与最后一个元素 A[n] 比较，返回两者中较小的那个。

因此，它相当于计算： \[ XYZ(A[1..n])=\min\bigl(XYZ(A[1..n-1]),\,A[n]\bigr) \] 最终得到整个数组的最小值。