KillDead
Junior Member | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Всем добрый день.
Препод по программированию задал задачку. Что-то никак не соображу, как решается.
Задача по Динамическим структурам данных, по паскалю в частности. Хотя жёстко к языку не привязана. Так что интересует алгоритм решения а не реализация . Вообще задача вроде как стандартная и видел много вопросов по ней. Но вот решения, которое подходит мне не нашёл.
Есть однонаправленный список, который может быть зациклен
Задание такое – определить зацикленный ли список?
Данные и условия:
Список может быть зациклен не только на предыдущий элемент. Т.е решение запустить 2 прохода по списку с разным шагом в 2 не подходит.
Перезаписывать, добавлять что-либо в самом списке нельзя. Т.е добавить флаг-" здесь мы были" нельзя.
Создавать переменные, которые зависят от количества элементов в цикле нельзя. Т.е создать ещё список с пройденными адресами нельзя.
Количество элементов списка (N) неизвестно. И максимальное количество проходов по списку, за которое точно можно будет сказать, что список не зациклен (или зациклен), не должно превышать N. Т.е тупой поиск в пройденных элементах использовать нельзя.
Вродь всё)
|
Всего записей: 140 | Зарегистр. 13-08-2006 | Отправлено: 13:52 03-12-2009 | Исправлено: KillDead, 23:36 06-12-2009 |
|
