Member
Статус: Не в сети Регистрация: 11.04.2004 Откуда: СПБ
Доброго. Есть такая задачка.
Дано: связанный список из N элементов, причем N неизвестно.
Требуется: проверить его на наличие зацикливаний, при этом алгоритм должен иметь линейную производительность ( O(N)).
Мне хватит собственно алгоритма или каких-нибудь наводок, реализацию я сам напишу...
Последний раз редактировалось Catar 16.12.2006 17:49, всего редактировалось 1 раз.
Member
Статус: Не в сети Регистрация: 14.01.2004 Откуда: Киев, Украина
Не ясно какой список, односвязный или двухсвязный? Плюс что понимается под словом зацикленность? Линейная производительность, я так понимаю значит то, что время выполнения алгоритма прямопорционально зависит от кол-ва элементов в списке?
Member
Статус: Не в сети Регистрация: 11.04.2004 Откуда: СПБ
Еще одна задачка.
Есть массив из N чисел.
Есть число (A), которое повторяется в массиве нечетное число раз, все другие числа встречаются четное число раз. Определить число A за линейное время...
Ну как же: два одинаковых числа по xor дают ноль --> xor чётного количества одинаковых чисел = 0, а нечётного - самому числу. Добавлено спустя 36 секунд
Member
Статус: Не в сети Регистрация: 11.04.2004 Откуда: СПБ
Билли Бонс писал(а):
int a = 0; :0)
дык это же не реальный кусок кода.... например никому не понятно, что такое array естественно в рабочем app оно было прописано Добавлено спустя 43 секунды а если мы возьмем много чисел, встречающихся нечетное число раз, и будем искать ДВА числа, встречающихся четное число?
Немного громоздко, но зато линейно и потребление памяти не зависит от N. Разве что тип элементов массива ограничен(для чисел типа int уже потребуются гигабайты памяти).
зы: алгоритм находит все числа, встречающиеся чётное число раз.
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения