Python-сообщество

Isem
Список - это не тип переменной на языке Питон (хотя бы потому, что понятие списка возникло задолго до того, как появился Питон).

Питон - это уже вторичное. Я же дал ссылку на определение односвязного списка, как структуры данных.
Так что такое список в вашем представлении? Можно ссылку на какое-нибудь формальное описание? Тем более если речь внезапно пошла о односвязном списке, а не списке вообще. Впрочем в исходном описании не то, что односвязный, а и просто список не фигурировал.

В этой статье (Cycle Detection) первые три предложения в переводе можно озвучить так:

Тут вы правы, признаю. Я это пропустил.

Жаль, что мы решали разные задачи. Ну да ладно, разобрались и хорошо.

Isem
Точная длина головы этого списка 2677

Точно. Я не совсем правильно запрограммировал. мое смещение считалось не до начала последовательности, а включало первый сегмент:
2705-28=2677

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

Для меня список - это граф. Вершины графа - это элементы списка. Дуги графа - это связи между елементами. Граф, конечно, не произвольный. Одно- и дувухсвязные списки - это, соответсвенно, одно- и двухнаправленные связи в графе. Еще надо добавить к этому то, что выходная связь у вершины должна быть единственная. Но в любом случае список - это прежде всего граф (по-моему это у меня осталось от Дональда Кнута из его трехтомника “искусство программирования”).

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

Кстати, а как определить смещение начала цикла пользуясь вашим алгоритмом?

Ed
Кстати, а как определить смещение начала цикла пользуясь вашим алгоритмом?

К сожалению, никак. Можно только дать оценку сверху, но она может существенно превышать реальное значение. Без второго указателя (или второго прохода) здесь не обойтись. Сначала мне казалось, что это возможно, но, подумав, пришел к выводу, что нет.

Отредактировано (Сен. 1, 2010 14:42:32)