2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Односвязный список. Замкнулся или нет?
Сообщение12.12.2016, 21:19 


11/12/16
315
По легенде, эту задачу давали на собеседованиях в Майкрософте в середине 90-х.

Есть односвязный список любой длины. Список может закончиться (последний элемент указывает на null), либо замкнуться на себя в любое место (последний элемент указывает на какой-то элемент списка, может быть на самого себя).
Предложить алгоритм, который за время не хуже чем O(n) даст ответ на вопрос: список закончился или замкнулся?
Нельзя создавать никакие динамические структуры данных: в распоряжении есть только некоторое количество переменных, количество которых не зависит от длины списка.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение12.12.2016, 22:04 
Модератор
Аватара пользователя


09/05/12
9402
Кронштадт
Неоптимальное, кажется, решение, но в $O(n)$ вписывается. Берем два взаимно простых числа $p$ и $q$ и, стартовав с одного элемента, смещаемся по списку двумя указателями: одним на $p$ элементов, вторым - на $q$. Если в один прекрасный момент мы любым из них наткнемся на null - ответ очевиден; если в какой-то момент два указателя будут указывать на одно и то же - список имеет цикл. По идее, в среднем наилучший результат обеспечит пара $(1,2)$, но для конкретных циклов быстрее может оказаться и какая-то другая.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение12.12.2016, 22:33 


11/12/16
315
Решение, понятно, верное. И единственное мне известное. В O(n) укладывается.
А меньше, чем за O(n) проверить невозможно, так как нужно проверить каждый элемент, куда ссылается.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение12.12.2016, 23:17 
Модератор
Аватара пользователя


09/05/12
9402
Кронштадт
EUgeneUS в сообщении #1176407 писал(а):
А меньше, чем за O(n) проверить невозможно, так как нужно проверить каждый элемент, куда ссылается.
Асимптотику сделать меньше, естественно, нельзя, но, возможно, получится уменьшить константу, хотя, кажется, менее чем двумя обходами списка не обойтись, если память лимитирована.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение13.12.2016, 17:22 


11/12/16
315
Можно прикинуть.

Пусть сдвиг указателя на следующий элемент стоит столько же сколько сравнение, для простоты.
Сравнивать надо только положение "быстрого" указателя, но в каждом узле два раза - с null и со значением "медленного" указателя.
"Быстрый" указатель должен пройти весь список, меньше 3n не получается (на каждом шаге два сравнения и один сдвиг указателя), и уперлись в null. Общие затраты будут строго больше - добавятся затраты на смещение "медленного" указателя.

Рассмотрим два случая:

1. Список замыкается на начало.
а) Отношение скоростей 1:2. Затраты: 6n + n = 7n.
б) Отношение скоростей большое. Затраты: 3n (быстрый успевает обойти список и упереться в медленный)

2. Список замыкается на последний элемент.
а) Отношение скоростей 1:2. Затраты: 6n + n = 7n.
б) Отношение скоростей большое, обозначим его как V. Затраты: 3Vn + n

То есть при отношении 1:2 получаем результат за время зависящее от длины списка, как O(n), но слабо зависящее от его конфигурации.
При другом отношении время начинает сильно зависеть от конфигурации списка, впрочем продолжая оставаться O(n).

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение13.12.2016, 17:40 
Заслуженный участник
Аватара пользователя


20/07/09
3877
МФТИ ФУПМ
Если список не нужно сохранять, то можно сделать его реверс. Если придём к начальному элементу, то есть цикл.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение13.12.2016, 18:39 


11/12/16
315
Nemiroff
Забавное решение.
В приведенной формулировке - подходящее. В более жесткой ("нельзя метить элементы списка, в том числе с помощью новых структур данных") - нет.

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

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение13.12.2016, 23:09 


05/09/12
2263
Простите, не могли бы вы объяснить решение? Вот, к примеру, есть список
Используется синтаксис Haskell
l = (1+) : l
Как написать тестирующую функцию, проверяющую условие задачи?

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение13.12.2016, 23:49 


11/12/16
315
Цитата:
Используется синтаксис Haskell


К сожалению ничем не могу помочь :-(
И не ясно, какое решение из двух нужно объяснить.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение13.12.2016, 23:55 


05/09/12
2263
Тогда может объясните, какое отношение к абстракции односвязного списка имеют понятия "указатель", "указывать на одно и то же" и т.п.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение14.12.2016, 00:31 


11/12/16
315
_Ivana

Наверное никакое. Если честно, тонкая разница между указателем и ссылкой регулярно ускользает от меня.
Если Вам это режет глаз. Ну что ж. Есть вариант: возможно, Вам имеет смысл обратиться к модератору для перенесения темы в карантин по четвертому пункту:
Цитата:
4. Недостаточно внятная информация о предмете обсуждения
. Так сказать для приведения в порядок.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение14.12.2016, 00:42 
Заслуженный участник
Аватара пользователя


27/04/09
18500
Уфа
Насколько я помню, не любой список — односвязный. Вот хаскелевский [a] хотя и реализуется cons-ячейками (когда не оптимизируется в ноль), но, конечно, сравнить две такие ячейки не по значению не получится (если только у GHC нет какой-то тайной магии на этот счёт).

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение14.12.2016, 00:44 


05/09/12
2263
EUgeneUS судя по реакции в теме, никому это больше глаз не режет, или все делают необходимые выводы из контекста. Карантин - это лишнее, пусть остается как в ПДД - сначала дается определение понятия "велосипед" без упоминания руля (под которое подходят и роликовые коньки и тележка из супермаркета), а потом идет правило, запрещающее управлять велосипедом не держась за руль...

-- 14.12.2016, 00:46 --

arseniiv в сообщении #1176789 писал(а):
не любой список — односвязный

Хаскелевский, Схемный и многие другие - односвязные.
arseniiv в сообщении #1176789 писал(а):
сравнить две такие ячейки не по значению не получится

Я пытался намекнуть об этом ТС, но безуспешно.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение14.12.2016, 00:49 
Аватара пользователя


16/07/14
677
Москва
Тут конфликт обозначений.
Под односвязным список можно понимать функциональное "пустой список ИЛИ пара (элемент, список)". А можно - императивное "Node*, где Node - это пара (элемент, Node*)".
При использовании первого определения проблема не с решением, а уже с постановкой задачи - непонятно, что такое "список замкнулся". Если "для некоторых $n \neq m$ хвосты, начинающиеся с $n$-го и $m$-го элементов совпадают" - то эта задача неразрешима:
Используется синтаксис Python
def get_list(turing_machine, configuration=start_configuration):
  if configuration == end_configuration:
    yield from get_list(turing_machine, start_configuration)
  yield configuration
  yield from get_list(turing_machine, next_configuration(turing_machine, configuration))
get_list(MT) зациклен (по определению про совпадающие хвосты) тогда и только тогда, когда МТ останавливается.

 Профиль  
                  
 
 Re: Односвязный список. Замкнулся или нет?
Сообщение14.12.2016, 00:53 
Заслуженный участник
Аватара пользователя


27/04/09
18500
Уфа
_Ivana в сообщении #1176791 писал(а):
Хаскелевский, Схемный и многие другие - односвязные.
Хм, да, передумал, получается, что всё-таки единственная разница в том, есть ли способ узнавать, «где находится» объект (в данном случае cons-ячейка).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 17 ]  На страницу 1, 2  След.

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group