29 / 29 / 18
Регистрация: 13.02.2010
Сообщений: 145
|
||||||
1 | ||||||
Быки и коровы10.08.2011, 16:05. Показов 14223. Ответов 12
Метки нет (Все метки)
Есть такая задача быки о коровы. Условие: http://acmp.ru/?main=task&id_task=13. Код моего решения:
0
|
10.08.2011, 16:05 | |
Ответы с готовыми решениями:
12
Быки и коровы Быки и коровы Быки и коровы Быки и коровы |
2 / 2 / 0
Регистрация: 02.08.2011
Сообщений: 22
|
||||||
10.08.2011, 16:23 | 2 | |||||
Количество быков тоже неправильно выдает. все потому что во время выполнения цикла
как вариант - убрать удаление и в поиске коров добавить условие t[i]!=f[i]
1
|
Каратель
|
||||||
10.08.2011, 16:56 | 3 | |||||
строки сдесь не нужны
решение
1
|
29 / 29 / 18
Регистрация: 13.02.2010
Сообщений: 145
|
|
10.08.2011, 16:58 [ТС] | 4 |
0
|
Каратель
|
|
10.08.2011, 17:05 | 5 |
тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи
Добавлено через 1 минуту так как нумерация массивов с нуля, то правильным условием завершения цикла должно быть i < 4
0
|
29 / 29 / 18
Регистрация: 13.02.2010
Сообщений: 145
|
|
10.08.2011, 17:08 [ТС] | 6 |
Решение я расписал, быков переделаю но можете сказать как правильно сделать поиск коров со строками (не обращая внимания на быков). Как я уже говорил, Си++ я изучаю несколько недель и просто несколько сомневаюсь в коде а не псевдокоде на бумаге.
0
|
10.08.2011, 17:42 | 7 | ||||||||||
Даня98, можно в двух циклах. В первом проходите первую группу символов, во втором вторую. Во втором цикле поверяете: если символы равны и стоят на одинаковой позиции, инкрементируете счётчик быков, если же символы равны, но стоят на разных позициях, то инкрементируете счётчик коров.
Посмотреть код
Таким образом за один раз находите и всех быков, и всех коров. Добавлено через 2 минуты Можно ещё больше сэкономить, если сделать на C Добавлено через 6 минут На C
1
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||||||
10.08.2011, 19:02 | 8 | |||||
Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):
2
|
Higher
|
|
10.08.2011, 19:20 | 9 |
Сообщение было отмечено как решение
Решение
Позвольте с вами не согласится =)
В настолько детской задаче не имеет значения сложность алгоритма, даже при O(n^2), получается O(16)... Гораздо важнее случайно не допустить где-нибудь ошибку(я про условия настоящей олимпиады, ну или если не стоит цель попасть в лучшие попытки, как у меня =) ). А с использованием контейнеров и алгоритмов STL ошибку допустить очень сложно. Но есть специальные задачи, в которых важна именно оптимальность алгоритма. Порешайте задачи из темы "Динамическое программирование" на acmp, вам понравится =)
3
|
10.08.2011, 19:25 | 10 | |||||
Olga_, действительно, ваш алгоритм лучше. Если уж идти в сторону оптимизации, то можно отказаться от хранения чисел 0-9 в четырёх байтах int и хранить их в char, и выставлять 10 флагов не как 10 int по 4 байта каждый, а как 10 бит (в пределах двух байт). Уйму памяти сэкономим...
Оптимизируем дальше
Так же для ликвидации накладных расходов на вызов функции, можно и от неё отказаться :-)
2
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
|
10.08.2011, 19:28 | 11 |
Да вы правы, правы, Diagon, 100 раз правы, глупо было залезть в детскую тему. Пусть это будет как вариант, кто-то подумает, проанализирует, может понравится
Добавлено через 2 минуты И вы правы С битами очень удобно
1
|
29 / 29 / 18
Регистрация: 13.02.2010
Сообщений: 145
|
|
10.08.2011, 22:42 [ТС] | 12 |
У Вас не правильный алгоритм: введите 1234 1234 должно вывести 4 0, а у вас выводит 1 3.
Алгоритм O(N^2) работает правильнее чем O(N)
1
|
848 / 190 / 18
Регистрация: 01.08.2011
Сообщений: 505
|
||||||
11.08.2011, 08:05 | 13 | |||||
Даня98, вы как проверяли? Проверьте еще раз
0
|
11.08.2011, 08:05 | |
11.08.2011, 08:05 | |
Помогаю со студенческими работами здесь
13
Игра быки и коровы Игра: Быки и Коровы Быки и коровы, не правильно считает их Быки и коровы. Комментарии к коду. Написать игру «Быки и коровы» Нужен исходник программы "Быки и коровы" с минимальной итерацией Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |