1

アルゴリズムは、私が送信した入力の一部に対して 1 つのエラーでオフを返しています。最初に配列で merge_sort と inversion_count を書きました。これにより、適切な数の反転が返されました。ベクトルに移行すると、次の入力に対して 1 ずつ受け取ります: 2 4 1 3 5

新鮮な目をいただければ幸いです。

vector<int> a;
object o;

length = a.size();
inv = o.count_inversion(a, 0, length-1);



int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
{
    int inversion = 0;
    int mid = (alpha + omega) / 2;
    int i = alpha;
    int j = mid + 1;
    int lastITR = 0;
    vector<int> final(omega - alpha + 1);


while (i <= mid && j <= omega) {
    if (vector1[i] <= vector1[j])
    {
            final[lastITR++] = vector1[i++];
    }
    else
    {
            final[lastITR++] = vector1[j++];
            inversion += mid - i + 1;
    }
}

while (i <= mid)
    {
    {
    final[lastITR++] = vector1[i++];
    }

    while (j <= omega)
    {
    final[lastITR++] = vector1[j++];
    }

    for (int k=0 ; k < omega-alpha+1; k++)
    {
    vector1[k+alpha] = final[k];
    }

return inversion;
}


int inversion::count_inversion(vector<int> vector1, int a, int b)
{
int x, y, z, mid;

if (a >= b)
    {
            return 0;
    }

mid = (a+b)/2;

x = count_inversion(vector1, a, mid);
y = count_inversion(vector1, mid+1, b);
z = merge_and_count(vector1, a, b);

return x + y + z;
}
4

1 に答える 1

2

あなたの問題を引き起こしている可能性が高いものは以下のとおりです（注：あなたが何をしようとしているのかわかりませんが、正直なところ重要ではないと思います）：

int inversion::merge_and_count(vector<int> vector1, int alpha, int omega)
// note: pass by *value*, not reference ------^

ルーチンの最後に次のような理由で、呼び出し元のためにこのベクトルを実際に変更するつもりであることは明らかです。

for (int k=0 ; k < omega-alpha+1; k++)
{
    vector1[k+alpha] = final[k];
}

基本的に、マージされた を構築しfinal、それを破棄しようとしているベクターにコピーします。これが行われると、呼び出し側vector<int>は変更されず、以前と同じままです。

参照を使用してこれを修正します。

int inversion::merge_and_count(vector<int>& vector1, int alpha, int omega)
// note: reference -----------------------^

潜在的な問題がいくつかありますが、それがあなたを悲しませている可能性があります。そこで呼び出し元ベクトルを変更したいことが明確ではないため、値渡しcount_inversionは問題ありません。これが反転のみをカウントしている場合は、変更したくない可能性があります。ただしmerge_and_count、参照を使用する必要があります。

注: イテレータを習得したら、このようなモデル化に喜んで使用できます。コードがきれいになるだけでなく、適切なイテレータ型をサポートする任意のシーケンス コンテナでの使用が自動的に許可されます。

于 2013-10-11T05:27:34.550 に答える