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

この疑似コードは、b[] でn /2 回以上出現した値 v を見つけることだと思います。

4

2 に答える 2

3

の 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 に答える