Блог

Я пишу программу для школьного проекта на C, которая сравнивает значения двух массивов и выдает конкретные результаты в зависимости от того, какие данные были введены пользователем. В основном мои выходные значения — это два, correctPosition и correctValue.

correctValue — это значение, которое находится в массиве значений, но не в правильной позиции в inputArray, например; значение «4» находится в индексе 1 массива значений, но расположено в индексе 2 inputArray.

correctPosition — это значение с одинаковым индексом в обоих массивах valuesArray и inputArray. Например; значение «3» находится в индексе 1 valuesArray и inputArray

Если значение x между двумя массивами совпадает, то это может быть либо correctValue, либо correctPosition. Вот визуальное представление:

 valuesArray: 2 3 3
------------------
inputArray:  1 2 3
Answer: correctPosition = 1, correctValue = 1.

inputArray:  2 1 3
Answer: correctPosition = 2, correctValue = 0.

inputArray:  2 3 3
Answer: correctPosition = 3, correctValue = 0.
  

Вот код, который я написал для этого:

 #include <stdio.h>

int main() {

  int inputArray[3], valuesArray[3];
  int correctNumber = 0, positionMatch = 0;
  int x, y;
  int visitedMatch[3];

  valuesArray[0] = 2;
  valuesArray[1] = 3;
  valuesArray[2] = 3;
  inputArray[0] = 1;
  inputArray[1] = 2;
  inputArray[2] = 3;

  for( x = 0; x < 3; x  ) {
    visitedMatch[x] = 0;
  }

  for(x = 0; x < 3; x  ) {
    for(y = 0; y < 3; y  ) {
      if (inputArray[x] == valuesArray[y] amp;amp; visitedMatch[y] == 0) {
        if (x == y) { positionMatch  ; } else { correctNumber  ; }
        visitedMatch[y] = 1;
        break;
      }
    }
  }

  printf("correctPosition = %d, ", positionMatch);
  printf("correctValues = %dn", correctNumber);
  return 0;
}
  

Проблема в том, что для ввода 1 2 3 сначала принимается 1 и проверяется в valuesArray и ничего не может найти, поэтому результат остается 0. Затем на второй итерации, где x = 1, он принимает значение 2 и проверяет, что оно находится в массиве, но не с правильным индексом, поэтому счетчик correctValue становится 1. Теперь на последней итерации, где x = 2, он принимает значение 3 и проходит через цикл и находит ПЕРВОЕ значение «3» с индексом 2, потому что оно никогда не посещалось ранее, поэтому конечный результат становится correctPosition = 0, correctValue = 2. Если я записываю входные данные как 2 3 3, то все работает нормально, и на выходе получается correctPosition = 3, correctValue = 0. Как я могу это исправить, чего мне здесь не хватает?

Любая помощь будет действительно оценена.

Как я писал в комментариях, я предлагаю другой подход. Ваш алгоритм немного неаккуратен, потому что логически оценка positionMatch вкладчиков включает сравнение каждого входного значения ровно с одной соответствующей другой позицией, тогда как оценка valueMatch вкладчиков включает сравнение каждого входного значения со всей доской.

Они были бы чище, если бы были разделены. Если бы вам пришлось беспокоиться об обработке очень больших плат, то также было бы уместно, чтобы разделение двух этапов могло привести к решению, стоимость которого линейно зависит от размера платы, а не квадратично. В частности, подход, который я предлагаю, заключается в

1. Просканируйте два массива один раз, чтобы вычислить positionMatch количество и построить для каждого массива гистограмму количества появлений каждого символа.

2. Сканируйте две гистограммы, вычисляя сумму минимального для каждого символа количества отсчетов для этого символа в двух гистограммах. Это приводит к общему количеству правильных чисел, но не отличает те, которые находятся в правильном положении, от этих неправильных позиций.

3. Вычтите positionMatch вычисленное в (1) из суммы, вычисленной в (2), чтобы получить correctNumber .

С учетом сказанного, однако, вы должны быть в состоянии настроить свой текущий код для вычисления правильных результатов. Главное, чего не хватает, это избегать использования элемента the, valuesArray который должен предоставлять positionMatch вместо того, чтобы вместо этого предоставлять correctNumber . Но это ситуация, которую вы можете протестировать. Когда вы обнаруживаете совпадение ( inputArray[x] == valuesArray[y] amp;amp; visitedMatch[y] == 0 ), вы в настоящее время используете одну из двух альтернатив, в зависимости от того, x == y . Чтобы правильно вычислить количество, вместо этого у вас должно быть три:

• Если x == y , то увеличьте positionMatch и прервите внутренний цикл. (Вы также можете отметить посещенную позицию, но вам не нужно этого делать.)
• В противном случае, если inputArray[y] == valueArray[y] тогда ничего не делать. Этот элемент valueArray внес или будет вносить вклад в positionMatch , поэтому он не должен вносить вклад в correctNumber . Просто переходите к следующей итерации внутреннего цикла.
• Увеличьте значение Else correctNumber , отметьте посещенную позицию y и завершите внутренний цикл

В качестве альтернативы, вы могли бы адаптировать свой текущий подход для имитации предложенного мной без фактического построения физических гистограмм. Эти изменения были бы необходимы:

• Во внешнем цикле определите, следует ли увеличивать positionMatch . В любом случае переходите к внутреннему циклу.
• Во внутреннем цикле игнорируйте, является ли это x == y , и вместо этого увеличивайте correctNumber и отмечайте посещенную позицию всякий раз, когда вы находите совпадение. Это заменяет вычисление и оценку гистограмм.
• в конце вычтите positionMatch из correctNumber , прежде чем сообщать результаты.

Другое решение, немного более простое, чем алгоритм Джона Боллинджера :

• подсчитайте точное совпадение и укажите, что эти позиции следует забыть в обоих массивах

• для каждой не забываемой позиции из inputArray извлеките значение из не забываемой позиции valuesArray

  • если найдено в первый раз, увеличьте правильное число и укажите, что эту позицию в массиве значений следует забыть
  • если найдено, но не с первого раза, просто укажите эту позицию в valuesArray, чтобы забыть

Реализация может быть (поскольку я сейчас ленив, я даю значения для _inputArray через идентификатор препроцессора I, см. компиляции)

 #include <stdio.h>

#define SZ 3

int main() {
  int valuesArray[SZ] = { 2,3,3 };
  int inputArray[SZ] = { I };
  int correctNumber = 0, positionMatch = 0;
  int x, y;
  int forgetValues[SZ] = { 0 }; /* useless to give more value because want 0 for the others */
  int forgetInput[SZ] = { 0 }; /* useless to give more value because want 0 for the others */

  /* count the exact matches */
  for (x = 0; x < SZ; x  = 1) {
    if (inputArray[x] == valuesArray[x]) {
      positionMatch  = 1;
      printf("correct match %d index %dn", inputArray[x], x);
      forgetValues[x] = forgetInput[x] = 1; /* do not consider that position later */
    }
  }

  /* count correct values */
  for (x = 0; x < SZ; x  = 1) {
    if (!forgetInput[x]) {
      int v = inputArray[x];
      int found = 0;

      for(y = 0; y < SZ; y  = 1) {
        if (!forgetValues[y] amp;amp; (valuesArray[y] == v)) {
          if (!found) {
            /* first time, count it */
            correctNumber  = 1;
            found = 1;
            printf("correct value %d index %d / %dn", v, x, y);
          }
          forgetValues[y] = 1; /* do not consider it later */
        }
      }
    }
  }

  printf("correctPosition = %d, ", positionMatch);
  printf("correctValues = %dn", correctNumber);
  return 0;
}
  

Компиляции и выполнения ;

 pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall -DI=1,2,3 c.c
pi@raspberrypi:/tmp $ ./a.out
correct match 3 index 2
correct value 2 index 1 / 0
correctPosition = 1, correctValues = 1
pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall -DI=2,1,3 c.c
pi@raspberrypi:/tmp $ ./a.out
correct match 2 index 0
correct match 3 index 2
correctPosition = 2, correctValues = 0
pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall -DI=2,3,3 c.c
pi@raspberrypi:/tmp $ ./a.out
correct match 2 index 0
correct match 3 index 1
correct match 3 index 2
correctPosition = 3, correctValues = 0