采用 4 个输入并打印三个数字的 largest/best 之和的伪算法

Question

我的伪代码作业需要一些帮助：输入 4 个数字并打印最大的 3 个数字的总和。

例如：输入：14、1、9、3 输出：14+9+3 => 26

如何用上述任务的伪代码编写算法？

到目前为止我已经做到了：

input a, b, c, d
declare h1, h2, h3
    if(a>=b && a>=c && a>=d)    h1 = a
    if(b>=a && b>=c && b>=d)    h2 = b
    if(c>=a && c>=b && c>=d)    h3 = c
    if(d>=a && d>=b && d>=c)    h4 = d
print h1+h2+h3

这样好吗？

Answer 1

假设输入在数组 t.
让sum = t[0].
让min = t[0].
对于 i 从 1 到 3 重复步骤 5 和 6:
sum += t[i].
if (min > t[i]) min = t[i].
Return sum - min.

您和 Brian 介绍的另一种方法归结为排序（对于 n=4，您可以像以前那样 "manually"，但对于更大的 n，这不是一个好主意）然后取和。

我更喜欢上面显示的方法，因为它保证了线性时间复杂度，可以很好地扩展并且易于实现。它只通过输入数据一次，如果输入是一个一个地流式传输并且我们不想将输入存储在内存中（我们想这样做 "on the fly"），则可以使用它。如果对输入数据没有任何假设，排序可能比线性排序（可以是 nlogn）更昂贵。

Answer 2

您的伪代码开了个好头。但是现在您只能找到四个数字中最大的一个。您需要再重复两次（忽略最大的）才能找到第二大和第三大的。

不过，另一个聪明的想法是，如果您需要 3 个最大的数字，则第 4 个数字必须是最小的。找到最小的数字，然后将其他数字相加。

input a, b, c, d
declare min

// find the smallest
min = a
if (b < min) min = b
if (c < min) min = c
if (d < min) min = d

// the sum of the largest 3 = the sum of all 4 minus the minimum
print a + b + c + d - min

Answer 3

使用递归。如果输入中的第一个数字最小，则对其他三个求和，否则旋转输入并递归调用。最终最小的数将是 a，所以其他三个是最大的，你可以将它们相加并得到答案 return。在伪代码中：

function sum3max(a, b, c, d)
    if a == min(a, b, c, d)
        return b + c + d
    return sum3max(b, c, d, a)

采用 4 个输入并打印三个数字的 largest/best 之和的伪算法

Pseudo Algorithm that takes 4 inputs and prints the sum of largest/best of three numbers

algorithm

pseudocode