Предыдущая тема :: Следующая тема |
Автор |
Сообщение |
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Окт 31, 2005 8:52 Заголовок сообщения: вопрос программистам |
|
|
Ребзики, прораммеры, подскажите оптимальный алгоритм доказательства незамкнутости однонаправленного огромадного списка.
Возможно в формулировке допущенны ошибки. Можно ли замкнутый список назвать однонаправленным?
Спасибо. Олеся. Кривой Рог |
|
Вернуться к началу |
|
|
shem СОЛНЦЕПОДОБНЫЙ
Зарегистрирован: 21.10.2004 Сообщения: 1301 Откуда: ага, именно оттуда
|
Добавлено: Пн Окт 31, 2005 10:04 Заголовок сообщения: Re: вопрос программистам |
|
|
да можно. однонаправленный, это когда n-ый элемент ссылается на n+1, но n+1 не имеет ссылок на n-ого.
так что только замкнутый список из двух элементов не может быть однонаправленным:)))
а алгоритм.. ну вообще задача чисто переборная и решается в лоб, т.е. O(N*N) если требуется найти все циклы, если они вообще есть.
так что вопрос в эффективности реализации. |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Окт 31, 2005 10:52 Заголовок сообщения: Re: вопрос программистам |
|
|
Шем, а разве циклов может быть больше одного если список замкнутый?
а реализация? как я могу себе представить: при пробеге по списку нам необходимо отдельно запоминать ВСЕ указатели, например в ключ массива - О(1). на каждом шаге проверять встречался ли нам такой указатель или нет(при достаточном объеме свободной памяти). так?
т.е. нет какго-нить хитрого математического доказательства? |
|
Вернуться к началу |
|
|
HuB Hito
Возраст: 44 Зарегистрирован: 15.10.2004 Сообщения: 1427 Откуда: Бамбуково / мАсква
|
Добавлено: Пн Окт 31, 2005 13:04 Заголовок сообщения: Re: вопрос программистам |
|
|
зачем все запоминать?
просто будет n! проходов..
берешь первый элемент - пробегаешь 2...n, по ходу смотришь нет ли ссылок на первый.
берешь второй - пробегаешь 3..n, по ходу смотришь нет ли ссылок на второй.
и.т.д.
тупо и просто... или тебе надо какой-нибудь хитрожопый алгоритм? _________________ все что было написано до этого - наглая и беспардонная ложь |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Окт 31, 2005 13:44 Заголовок сообщения: Re: вопрос программистам |
|
|
а теперь представь что случится если список замкнут?
n неизвестно и сколь угодно большое. |
|
Вернуться к началу |
|
|
arygaetu [cut]
Зарегистрирован: 06.10.2004 Сообщения: 4105 Откуда: da hab ich noch nicht gelebt
|
Добавлено: Пн Окт 31, 2005 14:07 Заголовок сообщения: Re: вопрос программистам |
|
|
напомню: программирование еще никому счастья не принесло! |
|
Вернуться к началу |
|
|
GHOST СОСТОЯНИЕ-НОРМАЛЬНО
Возраст: 35 Зарегистрирован: 16.05.2005 Сообщения: 488 Откуда: ПИТЕР-Flava
|
Добавлено: Пн Окт 31, 2005 15:20 Заголовок сообщения: Re: вопрос программистам |
|
|
да ну вас)! _________________ ПРЕДЕЛ СВОБОДЫ.....СПУТНИК ЖИзни) |
|
Вернуться к началу |
|
|
HuB Hito
Возраст: 44 Зарегистрирован: 15.10.2004 Сообщения: 1427 Откуда: Бамбуково / мАсква
|
Добавлено: Пн Окт 31, 2005 15:38 Заголовок сообщения: Re: вопрос программистам |
|
|
MAK
поясни тогда - у тебя связанный список или массивом заданный? _________________ все что было написано до этого - наглая и беспардонная ложь |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Окт 31, 2005 16:21 Заголовок сообщения: Re: вопрос программистам |
|
|
Имеем одонаправленный список неизвестной длинны. Он может быть очень длинным(>миллиарда например).
Нужен алгоритм, оптимально доказующий что этот список не замкнут.
У меня тока такой вариант:
пробегаемся по всему списку. все указатели заносим в ключ массива, проверяя нет ли уже такого ключа в этом массиве. ну типа хэш-таблица без данных. если дошли до конца списка - список не замкнут, если встретили указатель второй раз, фсе, хана, дальше лучше не продолжать - список замкнут.
поробег по списку - О(n), проверка указателя во вспомогательном массиве - О(1); т.е. вроде быстро, но обжористо. |
|
Вернуться к началу |
|
|
HuB Hito
Возраст: 44 Зарегистрирован: 15.10.2004 Сообщения: 1427 Откуда: Бамбуково / мАсква
|
Добавлено: Пн Окт 31, 2005 16:28 Заголовок сообщения: Re: вопрос программистам |
|
|
MAK
ну, вариант 2 не обжористый, но долгий...
есть еще какие-то средние варианты - сейчас на вскидку не вспомню, но постараюсь нарыть. _________________ все что было написано до этого - наглая и беспардонная ложь |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Окт 31, 2005 16:33 Заголовок сообщения: Re: вопрос программистам |
|
|
возможно какая-нить сортировка или поиск хитрожопый...
ау, Шем, 2can, выж собаку съели(гыгы), разъясните неграмотному. |
|
Вернуться к началу |
|
|
shem СОЛНЦЕПОДОБНЫЙ
Зарегистрирован: 21.10.2004 Сообщения: 1301 Откуда: ага, именно оттуда
|
Добавлено: Пн Окт 31, 2005 16:40 Заголовок сообщения: Re: вопрос программистам |
|
|
ммм...
вопрос - список неизвестной длины?
какой длины хэш таблица тогда, если неизвестна длина списка?
или она динамическая?
ну тогда _очень_ долго будет вставляться новый элемент. |
|
Вернуться к началу |
|
|
shem СОЛНЦЕПОДОБНЫЙ
Зарегистрирован: 21.10.2004 Сообщения: 1301 Откуда: ага, именно оттуда
|
Добавлено: Пн Окт 31, 2005 16:43 Заголовок сообщения: Re: вопрос программистам |
|
|
не может быть поиска... надо все элементы просмотреть, по любому.
разве что поколдовать с хэш-функцией.
выбрать что нибудь такое, что учитывает размер элементов списка, границы выделенной памяти под этот список и т.д.
т.е. колдовать с реализацией. а чисто математически - абсолютно поисковая задачу, никакого алгоритма. |
|
Вернуться к началу |
|
|
arygaetu [cut]
Зарегистрирован: 06.10.2004 Сообщения: 4105 Откуда: da hab ich noch nicht gelebt
|
Добавлено: Пн Окт 31, 2005 17:00 Заголовок сообщения: Re: вопрос программистам |
|
|
к слову я седне так поколдовал с хэш-функцией што до сих пор соображаю плохо |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Окт 31, 2005 17:00 Заголовок сообщения: Re: вопрос программистам |
|
|
shem,
список неизвестной длины. и сразу вопрос: если список замкнут, как определяется его длина? бесконечная? или по количеству уникальных элементов? |
|
Вернуться к началу |
|
|
HuB Hito
Возраст: 44 Зарегистрирован: 15.10.2004 Сообщения: 1427 Откуда: Бамбуково / мАсква
|
Добавлено: Пн Окт 31, 2005 17:03 Заголовок сообщения: Re: вопрос программистам |
|
|
MAK
И я так понял ссылки могут быть любыми и не подчиняются никаким правилам? _________________ все что было написано до этого - наглая и беспардонная ложь |
|
Вернуться к началу |
|
|
HuB Hito
Возраст: 44 Зарегистрирован: 15.10.2004 Сообщения: 1427 Откуда: Бамбуково / мАсква
|
Добавлено: Пн Окт 31, 2005 17:04 Заголовок сообщения: Re: вопрос программистам |
|
|
MAK писал(а): | shem,
список неизвестной длины. и сразу вопрос: если список замкнут, как определяется его длина? бесконечная? или по количеству уникальных элементов? |
1) по количеству элементов до замыкания, либо
2) бесконечность
зависит от задач. |
|
Вернуться к началу |
|
|
HuB Hito
Возраст: 44 Зарегистрирован: 15.10.2004 Сообщения: 1427 Откуда: Бамбуково / мАсква
|
Добавлено: Пн Окт 31, 2005 17:06 Заголовок сообщения: Re: вопрос программистам |
|
|
arygaetu
захэшируй свой хэш!
и докажи что ты замкнут сам на себя. |
|
Вернуться к началу |
|
|
3y _____________________________
Зарегистрирован: 02.10.2004 Сообщения: 649 Откуда: Спб
|
Добавлено: Пн Окт 31, 2005 20:58 Заголовок сообщения: Re: вопрос программистам |
|
|
попробуй у Кнута поискать ? кажется в 3 томе
есть тут http://lib.ru/CTOTOR/KNUT/
могу в PDF-е перслать.... |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Чт Ноя 30, 2006 19:42 Заголовок сообщения: Re: вопрос программистам |
|
|
да, кнут еще тот мракобес... :) |
|
Вернуться к началу |
|
|
Ariny Арина
Возраст: 37 Зарегистрирован: 07.10.2004 Сообщения: 85 Откуда: Казань+Буково
|
Добавлено: Чт Ноя 30, 2006 23:35 Заголовок сообщения: Re: вопрос программистам |
|
|
здесь Шем был - ещё программистом год назад) _________________ Встреча Нового года у меня прошла неудачно: я попробовал подключиться к Интернету, но не сумел.
"Лансапоте". М.Уэльбек |
|
Вернуться к началу |
|
|
dinah Сюзанна
Возраст: 39 Зарегистрирован: 03.12.2004 Сообщения: 3556
|
Добавлено: Пт Dec 01, 2006 0:12 Заголовок сообщения: Re: вопрос программистам |
|
|
они больны все. _________________ Я чуть не плакала и так разволновалась, что заговорила по-немецки.
А. Франк |
|
Вернуться к началу |
|
|
pag Житель
Зарегистрирован: 13.10.2004 Сообщения: 85
|
Добавлено: Сб Апр 21, 2007 0:51 Заголовок сообщения: Re: вопрос программистам |
|
|
Динка, не правда! Люди обсуждают нормальную жизненную ситуацию! Первого января машинист московского метро в пять утра сел за свой штурвал в глубоком тоннеле.
....и никак он не поймет ведет он поезд по кольцевой или прямой линии: дежурные ему только сообщают о следующей станции.
А ему здесь и сейчас хочется знать куда же он все-таки пришел на работу в первый день Нового Года! |
|
Вернуться к началу |
|
|
pag Житель
Зарегистрирован: 13.10.2004 Сообщения: 85
|
Добавлено: Сб Апр 21, 2007 1:07 Заголовок сообщения: Re: вопрос программистам |
|
|
Да, чуть не забыл! Поскольку список однонаправленный, то машинист уже не помнит как называлась предыдущая станция - ну первое января пять утра и все такое! |
|
Вернуться к началу |
|
|
arygaetu [cut]
Зарегистрирован: 06.10.2004 Сообщения: 4105 Откуда: da hab ich noch nicht gelebt
|
Добавлено: Сб Апр 21, 2007 15:14 Заголовок сообщения: Re: вопрос программистам |
|
|
это вопрос профессионального опыта.
матерому машинисту абсолютно пофигу где он едет, по кольцу или прямо.
вкл/выкл/вкл/выкл |
|
Вернуться к началу |
|
|
MAK Атэц
Зарегистрирован: 30.09.2004 Сообщения: 2690 Откуда: Карачаево-Балбесия
|
Добавлено: Пн Апр 23, 2007 12:34 Заголовок сообщения: Re: вопрос программистам |
|
|
arygaetu писал(а): | вкл/выкл/вкл/выкл |
это далеко не все обязанности машиниска электоропоезда. давайте вместе загляем в устаф. пункт 13 гласит что, "при виде горящей избы, он обязан туда зайти". тут возникает внештатная ситуация - как он будет в нее заходить, если "осторожно, двери давно были закрыты"? |
|
Вернуться к началу |
|
|
|