0 / 0 / 0
Регистрация: 06.08.2012
Сообщений: 17
|
|
1 | |
Быки и коровы18.11.2015, 20:32. Показов 2361. Ответов 7
Метки нет (Все метки)
Доброго времени суток. Не могу реализовать человеческий поиск коров в Delphi. Имеется массив цифр загаданного 4-значного числа и массив цифр введенного пользователем числа. При проверке всех элементов (например, числа 1111) записывает лишнее кол-во коров при повторениях (если, например, цифра 1 присутствует в загаданном числе). Как можно реализовать поиск коров, чтобы он не реагировал на повторение цифр?
0
|
18.11.2015, 20:32 | |
Ответы с готовыми решениями:
7
Быки и коровы Быки и Коровы Быки и коровы Быки и Коровы. Переделать. |
438 / 367 / 132
Регистрация: 09.09.2011
Сообщений: 1,334
|
|
18.11.2015, 20:41 | 2 |
не понятен алгоритм поиска коров... как он должен быть реализован - приведите пример.
0
|
0 / 0 / 0
Регистрация: 06.08.2012
Сообщений: 17
|
|
18.11.2015, 20:45 [ТС] | 3 |
Kitayets, например, компом загаданно число 4852. мы пробуем 9704. тут 1 корова, т.к. цифра 4 есть в загаданном. но если я введу 4444, то будет 4 коровы, а должна быть все равно 1
0
|
438 / 367 / 132
Регистрация: 09.09.2011
Сообщений: 1,334
|
|
18.11.2015, 21:05 | 4 |
Сообщение было отмечено Ajzek как решение
Решение
ну можно по разному реализовать такой алгоритм. что вы проходили по теме? - это может подтолкнуть к выбору правильного с точки зрения преподавателя...
с точки - зрения логики - найденные соответствия нужно удалять из поиска, но из массивов ничего не удалить - только двигать, а это все лишнее... можно отсортировать оба массива и использовать маркер с указанием на стартовый индекс, и в случае нахождения пары сдвигать индекс - это даст нам эмуляцию удаления уже найденных соответствий. например: загаданное число 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
|
0 / 0 / 0
Регистрация: 06.08.2012
Сообщений: 17
|
|
18.11.2015, 21:05 [ТС] | 5 |
Kitayets, вот эта идея мне понравилась, спасибо!
0
|
438 / 367 / 132
Регистрация: 09.09.2011
Сообщений: 1,334
|
|
18.11.2015, 21:08 | 6 |
например дано: загаданное число 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
|
0 / 0 / 0
Регистрация: 06.08.2012
Сообщений: 17
|
|
18.11.2015, 21:12 [ТС] | 7 |
Kitayets, Да, этот вариант попроще... Еще раз огромное спасибо!
0
|
438 / 367 / 132
Регистрация: 09.09.2011
Сообщений: 1,334
|
|
18.11.2015, 21:52 | 8 |
этот вариант проще, но... не очень хорош с алгоритмической точки зрения. Если количество цифр 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
|
18.11.2015, 21:52 | |
18.11.2015, 21:52 | |
Помогаю со студенческими работами здесь
8
Игра быки и коровы Задача: Быки и коровы Быки и Коровы, код задачи Быки и коровы, кое что не понятно Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |