BUKOVO.NET Forum

[MAK]

Ребзики, прораммеры, подскажите оптимальный алгоритм доказательства незамкнутости однонаправленного огромадного списка.
Возможно в формулировке допущенны ошибки. Можно ли замкнутый список назвать однонаправленным?

Спасибо. Олеся. Кривой Рог

[shem]

да можно. однонаправленный, это когда n-ый элемент ссылается на n+1, но n+1 не имеет ссылок на n-ого.
так что только замкнутый список из двух элементов не может быть однонаправленным:)))
а алгоритм.. ну вообще задача чисто переборная и решается в лоб, т.е. O(N*N) если требуется найти все циклы, если они вообще есть.
так что вопрос в эффективности реализации.

[MAK]

Шем, а разве циклов может быть больше одного если список замкнутый?
а реализация? как я могу себе представить: при пробеге по списку нам необходимо отдельно запоминать ВСЕ указатели, например в ключ массива - О(1). на каждом шаге проверять встречался ли нам такой указатель или нет(при достаточном объеме свободной памяти). так?
т.е. нет какго-нить хитрого математического доказательства?

[HuB]

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

[MAK]

а теперь представь что случится если список замкнут?
n неизвестно и сколь угодно большое.

[arygaetu]

напомню: программирование еще никому счастья не принесло!

[GHOST]

да ну вас)!

[HuB]

MAK
поясни тогда - у тебя связанный список или массивом заданный?

[MAK]

Имеем одонаправленный список неизвестной длинны. Он может быть очень длинным(>миллиарда например).
Нужен алгоритм, оптимально доказующий что этот список не замкнут.

У меня тока такой вариант:
пробегаемся по всему списку. все указатели заносим в ключ массива, проверяя нет ли уже такого ключа в этом массиве. ну типа хэш-таблица без данных. если дошли до конца списка - список не замкнут, если встретили указатель второй раз, фсе, хана, дальше лучше не продолжать - список замкнут.
поробег по списку - О(n), проверка указателя во вспомогательном массиве - О(1); т.е. вроде быстро, но обжористо.

[HuB]

MAK
ну, вариант 2 не обжористый, но долгий...
есть еще какие-то средние варианты - сейчас на вскидку не вспомню, но постараюсь нарыть.

[MAK]

возможно какая-нить сортировка или поиск хитрожопый...
ау, Шем, 2can, выж собаку съели(гыгы), разъясните неграмотному.

[shem]

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

[shem]

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

[arygaetu]

к слову я седне так поколдовал с хэш-функцией што до сих пор соображаю плохо

[MAK]

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

[HuB]

MAK
И я так понял ссылки могут быть любыми и не подчиняются никаким правилам?

[HuB]

[HuB]

arygaetu
захэшируй свой хэш!
и докажи что ты замкнут сам на себя.

[3y]

попробуй у Кнута поискать ? кажется в 3 томе
есть тут http://lib.ru/CTOTOR/KNUT/
могу в PDF-е перслать....

[MAK]

да, кнут еще тот мракобес... :)

[Ariny]

здесь Шем был - ещё программистом год назад)

[dinah]

они больны все.

[pag]

Динка, не правда! Люди обсуждают нормальную жизненную ситуацию! Первого января машинист московского метро в пять утра сел за свой штурвал в глубоком тоннеле.

....и никак он не поймет ведет он поезд по кольцевой или прямой линии: дежурные ему только сообщают о следующей станции.

А ему здесь и сейчас хочется знать куда же он все-таки пришел на работу в первый день Нового Года!

[pag]

Да, чуть не забыл! Поскольку список однонаправленный, то машинист уже не помнит как называлась предыдущая станция - ну первое января пять утра и все такое!

[arygaetu]

это вопрос профессионального опыта.
матерому машинисту абсолютно пофигу где он едет, по кольцу или прямо.
вкл/выкл/вкл/выкл