1

講師がクラスでこの質問をしました：[質問]

n個の整数のシーケンスが配列A[1..n]に格納されます。Aの整数aは、Aにn / 2回以上出現する場合、多数派と呼ばれます。

O（n）アルゴリズムは、次の観察に基づいて過半数を見つけるために考案できます。元のシーケンスの2つの異なる要素が削除された場合、元のシーケンスの過半数は新しいシーケンスの過半数のままです。この観察結果を使用するか、そうでない場合は、プログラミングコードを記述して、O（n）時間で大部分が存在する場合はそれを見つけます。

この解決策が受け入れられた[解決策]

int findCandidate(int[] a)
{
    int maj_index = 0;
    int count = 1;
    for (int i=1;i<a.length;i++)
    {
        if (a[maj_index] == a[i])
            count++;
        else
            count--;

        if (count == 0)
        {
            maj_index =i;
            count++;
        }
    }
    return a[maj_index];
}

int findMajority(int[] a)
{
    int c = findCandidate(a);
    int count = 0;
    for (int i=0;i<a.length;i++)
        if (a[i] == c) count++;

    if (count > n/2) return c;
    return -1;//just a marker - no majority found
}

提供されているソリューションが動的ソリューションであることがわかりません。そして、その言葉遣いに基づいて、彼がそのコードをどのように引き出したかはわかりません。

4

3 に答える 3

3

動的計画法という用語の由来は、特定の種類のソリューションを最適化するための本当に素晴らしい方法を説明しようとしていることです（動的計画法は、よりパンチの効いたように聞こえたため、使用されました）。言い換えれば、「動的計画法」を見るとき、それを「素晴らしい最適化」に変換する必要があります。

于 2010-12-15T00:14:16.920 に答える
2

「動的計画法」は、メモリの動的割り当てなどとは何の関係もありません。これは単なる古い用語です。実際、それは「プログラミング」の現代的な測定ともほとんど関係がありません。

これは、特定のクラスの問題を解決する方法です。サブ問題の最適な解決策が、より大きな問題の最適な解決策の一部であることが保証されている場合です。たとえば、最小の請求額で567ドルを支払いたい場合、ソリューションには、1ドル..566ドルのソリューションの少なくとも1つと、もう1つの請求書が含まれます。

コードは、アルゴリズムの単なるアプリケーションです。

于 2010-12-14T23:19:39.790 に答える
0

findCandidate関数は、提供された配列をより小さく、より管理しやすい部分に分解するため、これは動的計画法です。この場合、彼は大多数の候補として最初の配列から始めます。遭遇したときにカウントを増やし、そうでないときにカウントを減らすことによって、彼はこれが正しいかどうかを判断します。カウントがゼロに等しい場合、最初のi文字に過半数がないことがわかります。ローカルマジョリティを継続的に計算することにより、候補の識別フェーズで配列を複数回繰り返す必要がありません。次に、配列を2回調べて、O（n）を取得することにより、その候補が実際に多数派であるかどうかを確認します。2回繰り返すため、実際には2n時間で実行されますが、定数は重要ではありません。

于 2010-12-14T23:29:38.530 に答える