Сравнение двух значений массива в C

Question

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

correctValue - это значение, которое находится, например, в valuesArray , но не в правильной позиции в inputArray ;значение "4" соответствует индексу 1 из valuesArray , но находится по индексу 2 из inputArray .

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

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

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] && visitedMatch[y] == 0) {
        if (x == y) { positionMatch++; } else { correctNumber++; }
        visitedMatch[y] = 1;
        break;
      }
    }
  }

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

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

Любая помощь будет очень признательна.

Answer 1

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

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

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

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

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

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

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

---

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

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

Answer 2

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

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

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

  • , если найдено при первом увеличении correctNumber и укажите эту позицию в 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 %d\n", 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] && (valuesArray[y] == v)) {
          if (!found) {
            /* first time, count it */
            correctNumber += 1;
            found = 1;
            printf("correct value %d index %d / %d\n", v, x, y);
          }
          forgetValues[y] = 1; /* do not consider it later */
        }
      }
    }
  }

  printf("correctPosition = %d, ", positionMatch);
  printf("correctValues = %d\n", 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