-1

2つの非反復シーケンス（配列）から最初のn個の要素を交換する必要があります。ここで、nはランダムな整数です。

Seq1：1 4 5 6 9 8 2 3 7

Seq2：3 9 1 2 8 7 4 5 6

n=4の場合

Seq1：3 9 1 2 | 9 8 2 3 7

Seq2：1 4 5 6 | 8 7 4 5 6

ここで、「|」の後に繰り返される番号を置き換えて、シーケンスを修復する必要があります。

これを行う方法？

これが私の努力です。

for(left1 = 0; left1<pivot; left1++)
  {
   for(right1 = pivot; right1 < no_jobs; right1++)
    {
     if(S1->sequence[left1] == S1->sequence[right1])
      {
        for(left2 = 0; left2<pivot; left2++)
        {
          for(right2 = pivot; right2<no_jobs; right2++)
          {
            if(S2->sequence[left2] == S2->sequence[right2])
            {
              swap_temp = S1->sequence[right1];
              S1->sequence[right1] = S2->sequence[right2];
              S2->sequence[right2] = swap_temp;
              break;
            }
          } 
        }
      }
    }
  }
4

2 に答える 2

1

単一の for ループを使用すると、最初の n 個の要素を簡単に交換できます。

for(int i = 0; i < n; i++){
   int tmp = array1[i];
   array1[i] = array2[i];
   array2[i] = tmp;
}

ここで、配列で何が変更されたかを見つける必要があります。これは、交換した部品を比較することで確認できます。

int m1 = 0, m2 = 0;
int missing_array1[n];
int missing_array2[n];

for(int i = 0; i < n; i++){
    bool found = false;
    for(int j = 0; j < n; j++){
        if(array1[i] == array2[j]){
            found = true;
            break;
        } 
    }
    if(!found){
        missing_array2[m2++] = array1[i];
    }
}

for(int i = 0; i < n; i++){
    bool found = false;
    for(int j = 0; j < n; j++){
        if(array2[i] == array1[j]){
            found = true;
            break;
        } 
    }
    if(!found){
        missing_array1[m1++] = array2[i];
    }
}

missing_array2 には、array2 から欠落している数値が含まれるようになりました。これらは、array1 で複製されるすべての数値です。同じことが missing_array1 にも当てはまります。次に、両方の配列をスキャンし、重複を不足している数字に置き換える必要があります。

while(m1 >= 0){
    int z = 0;
    while(missing_array1[m1] != array2[n + z]){
        z++;
    }
    array2[n + z] = missing_array2[m1--];
}

while(m2 >= 0){
    int z = 0;
    while(missing_array2[m2] != array1[n + z]){
        z++;
    }
    array1[n + z] = missing_array1[m2--];
}

要約すると、交換したパーツを比較して、各配列から失われる値を見つけます。これらの値は、反対側の配列で複製される値でもあります。次に、各配列をスキャンし、重複する値を欠損値の 1 つに置き換えます (すべての値が一意である限り、欠損値のどれを気にしないと仮定します。

于 2010-07-01T16:23:39.607 に答える
0

シーケンスのスワップされた部分に同じ値が含まれている場合、繰り返しはありません。スワップを実行すると、最初の n 要素がシャッフルされるだけです。したがって、修復する必要がある値は、スワップされたシーケンスのいずれかで発生する値です

まず、n 個のスワップされた要素のヒストグラムを作成します。シーケンス 1 の要素はビット 0 としてカウントされ、シーケンス 2 の要素はビット 1 としてカウントされます。ヒストグラムのいずれかのメンバーがゼロでない場合、それらは 1 つまたは他のシーケンスのみ。

修復が必要な値がある場合は、書き換えが必要な値のルックアップ テーブルを作成できます。これは、i がヒストグラムの非対称値の 1 つでない限り、i を i にマップする必要があります。その場合、別の非対称値にマップする必要があります。

Seq1: 1 4 5 6 9 8 2 3 7

Seq2: 3 9 1 2 8 7 4 5 6

n = 4 の場合

Seq1: 3 9 1 2 | 9 8 2 3 7

Seq2: 1 4 5 6 | 8 7 4 5 6

ヒストグラム

value    1 2 3 4 5 6 7 8 9 
count    3 1 1 2 2 2 0 0 1

シーケンス 1 のマッピング (一方、ヒストグラム [S1[i]] & 1、[S1[i]] を S2[i] に置き換えます)

value    1 2 3 4 5 6 7 8 9 
replace  1 6 5 4 5 6 7 8 4

i > n のシーケンス 1 にマッピングを適用する

Seq1:    3 9 1 2 | 9 8 2 3 7
replace  - - - - | 4 8 6 5 7
result   3 9 1 2 | 4 8 6 5 7

シーケンス 2 のマッピング (一方、ヒストグラム [S2[i]] & 2、[S2[i]] を S1[i] に置き換えます)

value    1  2  3  4  5  6  7  8  9 
replace  1  2  3  9  3  2  7  8  9

i > n のシーケンス 1 にマッピングを適用する

Seq2:    1 4 5 6 | 8 7 4 5 6
replace  - - - - | 8 7 9 3 2
result   1 4 5 6 | 8 7 9 3 2

または、次の値をヒストグラムに設定された別のビットに置き換えます (反復置換では、値をそれ自体に置き換えるかどうかもチェックする必要があります)。結果の値が一意である限り、置換としてどの値が使用されるかは問題ではないと思います。

于 2010-07-01T17:03:59.493 に答える