0

我遇到了一个我无法实现的伪代码，因为我无法理解它：

i, c := 0,0;
do i ≠ n →
    if v = b[i]           → c, i := c + 2, i + 1
       c = i               → c, i, v := c + 2, i + 1, b[i]
       c ≠ i ^ v ≠ b[i]    → i := i + 1
    fi
od

我认为 tis 伪代码是关于找到在 b[] 中出现超过n / 2 次的值 v。

4

2 回答 2

3

中的三个条件if是可选的，它们应该被翻译成一个if-else if-else链。类似赋值语句c,i,v := c+2, i+1, b[i]是多重赋值，据我所知就像 Python 多重赋值一样，所以iinb[i]指的是i. 这会产生

// n and v are initialised to something sensible, hopefully
i = 0;
c = 0;
while(i != n) {
    if (b[i] == v) {
        c = c + 2;
        i = i + 1;
    } else if (c == i) {
        c = c + 2;
        v = b[i];  // conjecture that the b[i] on the RHS refers to the old i
        i = i + 1;
    } else {
        i = i + 1;
    }
}

由于i在每个分支中都递增，我们可以将其取出，并得到

for(i = 0, c = 0; i != n; ++i) {
    if (b[i] == v) {
        c += 2;
    } else if (c == i) {
        c += 2;
        v = b[i];
    }
}
于 2012-06-19T08:29:31.800 回答
0

哇，这不是我期望看到的。它看起来像 Dijkstra 的 do-od 表示法（不确定什么是好的参考，也许是这个：http ://www.cs.grinnell.edu/~stone/courses/compilers/introduction-to-Dijkstra.pdf ）。

大致来说，这是一系列保护检查。如果某些条件成立，则执行暗示。至于以 do-od 表示法实现某些东西，我不太确定。类似于以下内容：

i = c = 0;
while (i != n) {
    if (v == b[i]) {
        c = c+2, i = i+1;
        if (c == i) c = c+2, i = i + 1, v = b[i];
        if (c != i || v != b[i]) i = i + 1
    }
}

不知道这些中间变量是什么，而且我一直将 do-od 程序概念化为更接近硬件的东西（所有东西都在并行运行和测试）。祝你好运

于 2012-06-19T07:02:27.537 回答