伪代码/Java神秘算法

Question

我有一个算法，我想弄清楚它的作用。我相信你们中的一些人可以看看这个并告诉我它的作用，但我已经看了半个小时了，但我仍然不确定。当我尝试玩它时，它只是变得混乱。你有什么技巧来分解这样的算法？我如何分析这样的事情并知道发生了什么？

我的猜测是它按从小到大的顺序对数字进行排序，但我不太确定。

1. mystery(a1 , a2 , . . . an : array of real numbers)
    2. k = 1
    3. bk = a1
    4. for i = 2 to n
        5. c = 0
        6. for j = 1 to i − 1
            7. c = aj + c
        8. if (ai ≥ c)
            9. k = k + 1
           10. bk = ai
    11. return b1 , b2 , . . . , bk

这是我尝试用 Java 编写的等效内容，但我不确定我是否翻译正确：

public int[] foo(int[] a) {
        int k=1;
        int nSize=10;
        int[] b=new int[nSize];
        b[k]=a[1];
        for (int i=2;i<a.length;){
            int c=0;
            for (int j=1;j<i-1;)
                c=a[j]+c;
            if (a[i]>=c){
                k=k+1;
                b[k]=a[i];

Answer 1

Google 永远不会停止带来惊喜，因为29号我走吗？ ;)

Java 翻译是一个好主意，一旦运行，如果您在可视化算法时遇到问题，您将能够逐步浏览它以准确了解算法的作用。

一些提示：伪代码的数组索引为 1 到 n，Java 的数组索引为 0 到 length - 1 >。您的循环需要修改以适应这一点。此外，您还保留了循环中的增量 - i++、j++。

将 b 设为魔术常量大小也不是一个好主意 - 查看伪代码，我们可以看到它最多被写入 n - 1 次，因此这将是其大小的一个很好的起点。您可以调整它的大小以适合最后。

最后提示，该算法的时间复杂度为 O(n²)。这很容易确定 - 外部 for 循环运行 n 次，内部 for 循环运行 n / 2 次，总运行时间为 (n * (n / 2))。 n * n 占主导地位，这是 Big O 所关心的，使其成为 O(n²) 算法。

Answer 2

最简单的方法是抽取一小部分数字样本并在纸上进行计算。在您的例子中，我们采用数字a[] = {3,6,1,19,2}。现在我们需要逐步执行您的算法：

初始化：

i = 2
b[1] = 3

迭代后 1：

i = 3
b[2] = 6

迭代后 2：

i = 4
b[2] = 6

迭代后 3：

i = 5
b[3] = 19

迭代后 4：

i = 6
b[3] = 19

结果 b[] = {3,6,19}

您可能会猜到它在做什么。

Answer 3

您的代码非常接近伪代码，但存在一些错误：

• 您的 for 循环缺少增量规则：i++、j++
• Java 数组是基于 0 的，而不是基于 1 的，因此您应该初始化 k=0、a[0]、i=1 等

。 ，这不是排序，更多的是过滤 - 您会得到一些元素，但顺序相同。

Answer 4

我如何分析这样的事情并知道发生了什么？

此类操作的基本技术是用铅笔和纸手动执行。

更先进的技术是将代码分解为多个部分，弄清楚这些部分的作用，然后在心里重新组装它。 （技巧是选择分解的边界。这需要练习。）

一旦你变得更好，你将开始能够“阅读”伪代码......尽管这个例子对于大多数人来说可能有点太粗糙了编码员可以这样处理。

Answer 5

转换为 java 时，请小心数组索引，因为此伪代码似乎暗示从 1 开始的索引。

从静态分析来看：

• a 是输入，不会改变
• b 是输出
• k 似乎是指向 b 元素的指针，只会在某些情况下递增（因此我们可以认为 k = k+1 的意思是“下次我们写入 b 时，我们将写入下一个元素”）
• 第 6-7 行中的循环完成了什么？那么c的值是多少呢？
• 那么，使用之前的答案，第 8 行何时为真？
• 由于第 9-10 行仅在第 8 行为 true 时执行，这对输出中的元素有何说明？

然后你可以开始检查你的答案：

• 输出的所有元素都会被设置吗？
• 尝试使用类似 [1,2,3,4] 的输入运行伪代码——您期望输出是什么？

Answer 6

def funct(*a)
  sum = 0
  a.select {|el| (el >= sum).tap { sum += el }}
end

先生？谁发明了这些家庭作业问题？

顺便说一句：因为这是同时执行扫描和过滤器，并且过滤器取决于扫描，哪种语言具有必要的功能来简洁地表达这一点，使得序列只遍历一次？