задачка для программистов (linked list)

sttranik · Post by **sttranik** » 07 Dec 2001 16:54

оживить раздел пара старых задачек:

1. есть linked list (N->N->N->...). нужно не используя вложенных циклов определить не является ли этот list циклическим.

2. (решается одинаковым с 1 принципом) есть не циклический linked list. используя только один цикл (не используя вложенных) найти середину списка.

как вариант 2 - найти 1/3 или 2/3 от начала списка

Vovka · Post by **Vovka** » 07 Dec 2001 17:04

<blockquote>quote:<hr>Originally posted by sttranik:
оживить раздел пара старых задачек:

1. есть linked list (N->N->N->...). нужно не используя вложенных циклов определить не является ли этот list циклическим.

2. (решается одинаковым с 1 принципом) есть не циклический linked list. используя только один цикл (не используя вложенных) найти середину списка.

как вариант 2 - найти 1/3 или 2/3 от начала списка<hr></blockquote>

Может я чего-то не понял - но при чём тут волженные циклы?

Определить, циклический список или нет можно, просто пройдясь его от головы до хвоста и сравнивая адреса элементов с головой.

Во второй задаче сначала подсчитать элементы, пройдясь по списку, а на втором проходе отсчитать нужное кол-во.

Не, наверное я всё-таки не так чего-то понял...

sttranik · Post by **sttranik** » 07 Dec 2001 18:02

<blockquote>quote:<hr>Originally posted by Vovka:
Определить, циклический список или нет можно, просто пройдясь его от головы до хвоста и сравнивая адреса элементов с головой.<hr></blockquote>
список может зацикливаться не на голову.
<blockquote>quote:<hr>
Во второй задаче сначала подсчитать элементы, пройдясь по списку, а на втором проходе отсчитать нужное кол-во.
<hr></blockquote>
да, немного недосказал условие. нужно сделать за [b:36fcf198d2]один[/b:36fcf198d2] проход, [b:36fcf198d2]без вложенных циклов[/b:36fcf198d2].

GShapiev · Post by **GShapiev** » 07 Dec 2001 18:30

Первая:
Пройтись двумя указателями. Одним идти попорядку, другим прыгать через элемент. Если станут равны - циклический.

Вторая - то же самое. Только когда второй остановится первый будет указывать на середину. (соответственно с 1/3 и 2/3).

Drom · Post by **Drom** » 07 Dec 2001 20:57

<blockquote>quote:<hr>Originally posted by GShapiev:
Первая:
Пройтись двумя указателями. Одним идти попорядку, другим прыгать через элемент. Если станут равны - циклический.

<hr></blockquote>

мое первое поползновение было добавлять к 1 указателю 2^N, а вторым пробегать до позиции +2^N, сравнивая:
p1=1, p2=2,
p1=2, p2=3..4
p1=4, p2=5..8 ...

кстати, кто может оценить какое отношениые скоростей оптимально: например список из 2^10 элементов и последний показывает на случайно выбранный (равномерно) элемент из середины.

<занудка1>
только не "перепрыгивать", а просто двигаться с разными скоростями (2:1, 3:1) - иначе нужно добавлять специальный код чтобы не проскочить медленный указатель.
</занудка1>

<занудка2>
для 1/3 и 2/3 списка лучше идти сразу тремя указателями со скоростью 3:2:1
</занудка2>

Andy77 · Post by **Andy77** » 07 Dec 2001 22:05

[b:10a51ace39]мое первое поползновение было добавлять к 1 указателю 2^N, а вторым пробегать до позиции +2^N, сравнивая:
p1=1, p2=2,
p1=2, p2=3..4
p1=4, p2=5..8 ...
[/b:10a51ace39]

Ваше первое поползновение [img:10a51ace39]images/smiles/icon_smile.gif[/img:10a51ace39] имеет сложность n*n, в то время как сложность решения GShapiev - линейна.

[b:10a51ace39]кстати, кто может оценить какое отношениые скоростей оптимально: например список из 2^10 элементов и последний показывает на случайно выбранный (равномерно) элемент из середины.[/b:10a51ace39]

см. выше. 2^10 - достаточно большое число...

[b:10a51ace39]
только не "перепрыгивать", а просто двигаться с разными скоростями (2:1, 3:1) - иначе нужно добавлять специальный код чтобы не проскочить медленный указатель.
[/b:10a51ace39]

GShapiev написал всё правильно, а вот Ваше решение, похоже, страдает - Вам не кажется, что при скоростях 2, 3 мы просто не будем попадать на определённые элементы?

[img:10a51ace39]images/smiles/icon_confused.gif[/img:10a51ace39] может, я просто задачу не понял?

Drom · Post by **Drom** » 08 Dec 2001 02:57

<blockquote>quote:<hr>

Ваше первое поползновение [img:772f838ff9]images/smiles/icon_smile.gif[/img:772f838ff9] имеет сложность n*n, в то время как сложность решения GShapiev - линейна.
<hr></blockquote>
не, оно тоже линейно. как только p1 залезет в петлю и одновременно будет больше длины этой петли - тут и наступит конец.

<blockquote>quote:<hr>Originally posted by Andy77:

GShapiev написал всё правильно, а вот Ваше решение, похоже, страдает - Вам не кажется, что при скоростях 2, 3 мы просто не будем попадать на определённые элементы?
<hr></blockquote>
кажется.
у нас просто термины разные. для меня:
"прыгать" - сравнивать на шаге N элементы N c 2N,
"разные скорости" - сравнивать (N c 2N) и (N c 2N+1)

причем я теперь уже совсем не уверен, что в случае 2:1 прыгать не стоит [img:772f838ff9]images/smiles/icon_sad.gif[/img:772f838ff9] sorry

people, кто-нибудь теорчел помнит? можно определить для каких N при любых p, L существует q: (p+q) mod L = (Nq) mod L (?) N, p, q, L - натуральные бло... хм то есть числа натуральные.