Cool Folders ® :: Форум Игротека

О linked-listе

Автор: Большой Грызь
Дата : 09-12-04, Чтв, 17:11:25

Есть односвязный linked-list.
Т.е.:

X -> X -> X -> X -> X -> NULL

В котором может быть петля в виде:

X -> X -> X -> X -> X --
^ |
|________________|

Петля может быть, а может и не быть.
Требуется определить, есть ли петля или её нет за o(n) времени и за o(1) места.
Значения ячеек Х - абсолютно неважны (могут отличаться, могут быть одинаковыми).
Менять значения ячеек запрещено.
Всё, что можно проверять - это сами поинтеры.

Небольшая подсказка - если элементов N, то петлю можно определить максимум за N проверок, используя при этом не более 5 переменных.

Жизнь человека немного стоит по сравнению с его делом.
Но чтобы делать дело, надо жить.
(Э. Хемингуэй)
[ 10-12-04, Fri, 0:14:54 Отредактировано: Большой Грызь ]

О linked-listе

№ 2

Автор: a-dagger
Дата : 09-12-04, Чтв, 18:45:18

Что значит "o(n) времени" и "o(1) места"?

Фсе граматичиские ашипки в маих пастах зделаны мной намерино, в здравам уме и тфёрдой памети.

О linked-listе

№ 3

Автор: Большой Грызь
Дата : 10-12-04, Птн, 01:50:21

a-dagger,
Простыми словами это означает следующее:
1) "o(n) времени" означает, что для любого N (кол-во элементов в петле) твой алгоритм должен сделать максимум a*N проверок, где а - константа, не зависящая от N.

2) "o(1) места" означает, что для любого N (кол-во элементов в петле) твой алгоритм должен использовать не более Х памяти, где Х - константа, не зависящая от N.

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

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

О linked-listе

№ 4

Автор: Tarlog
Дата : 10-12-04, Птн, 14:07:31

Решение 1:
2 индекса: i, j.
i-один шаг
j-два шага
Если в какой-то точке (кроме первой) i==j, то есть петля.

Решение 2:
Проходишь по списку переворачивая его наоборот. Если вместо того, что-бы прийти к концу, приходишь к началу - есть петля.
Проходишь по списку еще раз, переворачивая его обратно.

Наверно надо добавить, что я это задачу решал в домашнем задании по Data structures года 3 назад и решил (решение 1), а решение 2 мне рассказали потом

[ 10-12-04, Fri, 21:13:24 Отредактировано: Tarlog ]
[ 10-12-04, Fri, 21:13:36 Отредактировано: Tarlog ]
[ 10-12-04, Fri, 21:15:19 Отредактировано: Tarlog ]

О linked-listе

№ 5

Автор: a-dagger
Дата : 10-12-04, Птн, 14:50:57

Автор: Tarlog

Решение 2:
Проходишь по списку переворачивая его наоборот. Если вместо того, что-бы прийти к концу, приходишь к началу - есть петля.
Проходишь по списку еще раз, переворачивая его обратно.

По-моему, это не сработает.
Ведь если петля такая:
X -> X -> X -> X -> X --
^ |
|________________|
то к началу ты не попадешь никогда, да и к концу тоже не придешь. Так как ты знаешь, что нужно начинать повторное прохождение?

Фсе граматичиские ашипки в маих пастах зделаны мной намерино, в здравам уме и тфёрдой памети.

О linked-listе

№ 6

Автор: Tarlog
Дата : 10-12-04, Птн, 14:57:22

a-dagger
Ты переворачиваешь список.
В твоем примере, после первой итерации список будет выглядеть так:
X <- X -> X -> X -> X --
      ^                |
      |________________|
А в конце так:
X -> X <- X <- X <- X --
      |                ^
      |________________|

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

О linked-listе

№ 7

Автор: Большой Грызь
Дата : 10-12-04, Птн, 15:03:46

Да, первое решение таки верное

А второе не принимается

В виду того, что было дано, что сам список менять нельзя

Это равносильно тому, что ты используешь o(n) памяти

Но первое решение абсолютно верное

П.С. А как с задачей о ряде чисел?

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

О linked-listе

№ 8

Автор: a-dagger
Дата : 10-12-04, Птн, 15:10:32

Честно говоря, не понял ни первого, ни второго решения

Не бывать мне программером...

Фсе граматичиские ашипки в маих пастах зделаны мной намерино, в здравам уме и тфёрдой памети.

О linked-listе

№ 9

Автор: Большой Грызь
Дата : 10-12-04, Птн, 15:37:43

a-dagger, объясняю первое

Рисуем две стрелочки: вначале обе указывают на первую клетку. Затем двигаем первую стрелочку по одной клетке (т.е., чтобы она указывала на 1-ю, затем 2-ю, затем 3-ю и те де), а вторую - через одну клетку (т.е., чтобы она указывала на 1-ю, затем 3-ю, затем 5-ю и те де).

Если есть петля, то вторая стрелка в какой-то момент "догонит" первую сзади. Если петли нет - то вторая стрелка просто дойдёт до конца списка.
При этом, если "догонит", то максимум через N итераций (вторая стрелка догонит первую до того, как первая пройдёт все N клеток). А если петли нет, то это уже за N/2 итераций станет ясно (вторая стрелка прыгая через клетку дойдет до конца).

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

О linked-listе

№ 10

Автор: a-dagger
Дата : 10-12-04, Птн, 15:54:27

Понятно

Сам бы ни в жисть до такого не допер

Фсе граматичиские ашипки в маих пастах зделаны мной намерино, в здравам уме и тфёрдой памети.

О linked-listе

№ 11

Автор: Tarlog
Дата : 11-12-04, Сбт, 01:47:32

равносильно тому, что ты используешь o(n) памяти

Я использую О(1) дополнительной памяти

А впрочем не принимается, так не принимается. Но решение красивое

О linked-listе

№ 12

Автор: Большой Грызь
Дата : 11-12-04, Сбт, 04:27:37

Автор: Tarlog
Дата : 11-12-04, Sat, 8:47:32

Я использую О(1) дополнительной памяти
А впрочем не принимается, так не принимается. Но решение красивое

Это, если ты меняешь лист "по месту"

а если это не разрешено - придется во втором варианте использовать о(n)

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