伪代码/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

最简单的方法是取一个样本，但只是一小部分数字，并将其写在纸上。在你的例子中，我们取数字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 2

您的代码与伪代码非常接近，但以下是一些错误：

• 你的for循环缺少增量规则：i++，k=0数组是从0开始的，而不是从1开始的，所以你应该初始化a[0]，i=1，e.t.c.

而且，这不是排序，更像是一种过滤--你会得到一些元素，但顺序是一样的。

Answer 3

我如何分析这样的东西，并知道发生了什么？

这类事情的基本技巧是用纸和笔手动执行。

一种更高级的技术是将代码分解成几个部分，找出这些部分的作用，然后在心理上重新组装它。(诀窍是选择分解的边界。这需要练习。)

一旦你做得更好了，你就可以开始“阅读”伪代码了……尽管对于大多数程序员来说，这个例子可能有点太粗糙，无法像那样处理。