@Ajzek

Доброго времени суток. Не могу реализовать человеческий поиск коров в Delphi. Имеется массив цифр загаданного 4-значного числа и массив цифр введенного пользователем числа. При проверке всех элементов (например, числа 1111) записывает лишнее кол-во коров при повторениях (если, например, цифра 1 присутствует в загаданном числе). Как можно реализовать поиск коров, чтобы он не реагировал на повторение цифр?

0

@Kitayets

не понятен алгоритм поиска коров... как он должен быть реализован - приведите пример.

0

@Ajzek

Kitayets, например, компом загаданно число 4852. мы пробуем 9704. тут 1 корова, т.к. цифра 4 есть в загаданном. но если я введу 4444, то будет 4 коровы, а должна быть все равно 1

0

@Kitayets

ну можно по разному реализовать такой алгоритм. что вы проходили по теме? - это может подтолкнуть к выбору правильного с точки зрения преподавателя...

с точки - зрения логики - найденные соответствия нужно удалять из поиска, но из массивов ничего не удалить - только двигать, а это все лишнее...

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

например:

загаданное число 3524, введенное 5444

1. сортируем -> 2345 и 4445
2. маркер на первом элементе *2344
3. ищем 4 с маркера до конца, или до первого совпадения
4. нашли на позиции 3, смещаем маркер на на позицию 4 -> 234*4, увеличиваем счетчик найденных коров
5. ищем 4 по шагу 3 -> нет
6. -//-
7. ищем 5 по шагу 3 - > есть, увеличиваем счетчик найденных коров
8. выводим счетчик. все


можешь такой алгоритм запрограммировать?

Добавлено через 3 минуты
или можно удалять найденные элементы - записывая в массив заведомо не корректные данные, например -1, если по условию вводятся только положительные числа, или 10 - двузначных цифр для поиска у нас точно не будет.

тогда логика поиска проще, чем сортировка и указатель на индекс

1

@Ajzek

Kitayets, вот эта идея мне понравилась, спасибо!

0

@Kitayets

например дано: загаданное число 3524, введенное 5444

1. ищем 5 в массиве линейным поиском, находим на позиции 2, увеличиваем счетчик найденных коров, заменяем 5 на -1 -> 3-124
2. ищем 4 в 3-124 - находим на позиции 4, увеличиваем счетчик найденных коров, заменяем 4 на -1 -> 3-12-1
3. ищем 4 в 3-12-1 -> нет
4. ищем 4 в 3-12-1 -> нет
5. выводим счетчик. все

1

@Ajzek

Kitayets, Да, этот вариант попроще... Еще раз огромное спасибо!

0

@Kitayets

этот вариант проще, но... не очень хорош с алгоритмической точки зрения. Если количество цифр 4 - то это ОК, но если вдруг размер массивов будет больше... значительно больше -> время решения задачи будет возрастать квадратично О(n^2).

первый вариант будет лучше, ведь он сокращает размер поиска при каждом нахождении соответствия, но есть еще лучший вариант - с линейной сложностью O(n):

1. создадим дополнительный массив из 10 элементов с индексами [0..9] и инициализируем его нулями
2. пройдем по массиву коров 1 раз и увеличим значения в спомогательном массиве на количество раз встреченных соответствующих цифр. например для исходного массива 5444 - вспомогательный будет выглядеть так (0 0 0 0 3 1 0 0 0 0).
3. теперь 1 раз пройдемся по массиву введенных цифр и если значение по соответствующему цифре индексу вспомогательного массива - 0, то корова не найдена иначе уменьшаем значение на 1 и увеличиваем счетчик найденных коров.
4. выводим счетчик. все

при размере массивов в 1000000 элементов - 2 алгоритм потребует ~1000000000000 сравнений, а последний приведенный всего ~2000000.

но если размер всего 4 элемента, то без разницы.

1