Нужна помощь с логикой (С) - PullRequest
Новая
       6

Нужна помощь с логикой (С)

0 голосов
/ 01 июля 2010

Мне нужно поменять первые 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;
            }
          } 
        }
      }
    }
  }

Ответы [ 2 ]

1 голос
/ 01 июля 2010

Поменять местами первые n элементов просто с помощью цикла for. 

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--];
}

Таким образом, вы сравниваете части, которые вы поменяли местами, чтобы найти значения, которые будут отсутствовать в каждом массиве. Эти значения также являются значениями, которые будут продублированы в противоположном массиве. Затем вы сканируете каждый из массивов и заменяете дублирующиеся значения одним из пропущенных значений (я предполагаю, что вам не важно, какое из пропущенных значений является уникальным.

0 голосов
/ 01 июля 2010

Если переставленные части последовательностей содержат одинаковые значения, повторов не будет - выполнение перестановки просто перетасует первые n элементов. Таким образом, значения, которые вам нужно восстановить, являются значениями, которые встречаются в одной из последовательностей перестановки

Во-первых, я бы создал гистограмму из n замененных элементов, причем из последовательности 1 считаются как бит 0, а из последовательности 2 - как бит 1. Если какие-либо элементы гистограммы отличны от нуля, то они происходят только в одной или другой последовательности.

Если есть значения, требующие восстановления, вы можете создать справочную таблицу значений, которые требуют перезаписи. Это должно отобразить i в 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

применить отображение к последовательности 1 для i> n 

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

применить отображение к последовательности 1 для i> n 

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

В качестве альтернативы, замените следующее значение другим битом, установленным в гистограмме (итеративная замена также должна будет проверять замену значения на себя); Я предполагаю, что на самом деле не имеет значения, какое значение используется в качестве замены, если значения в результате уникальны.

...