Дан однонаправленный список (упорядоченная структура данных, каждый элемент которой содержит указатель на следующий элемент) из n элементов. Известен указатель на первый элемент.
Необходимо определить, есть ли в этом списке циклы, то есть существует ли такой k-й элемент, у которого указатель содержит ссылку на один из предыдущих элементов - на r-й элемент, где r<k.
Алгоритм решения этой задачи должен выполняться за время t=O(n) (порядка n) и использовать постоянное, не зависящее от n, количество ячеек памяти - M=O(1).
Необходимо определить, есть ли в этом списке циклы, то есть существует ли такой k-й элемент, у которого указатель содержит ссылку на один из предыдущих элементов - на r-й элемент, где r<k.
Алгоритм решения этой задачи должен выполняться за время t=O(n) (порядка n) и использовать постоянное, не зависящее от n, количество ячеек памяти - M=O(1).
-
-
22.11.2007 в 23:42Чего-то я не понял, как это может указывать на предыдущий элемент, если он по любому указывает на следующий? Задача ошибочная. Список-то однонаправленный.
-
-
22.11.2007 в 23:51А вообще если какой-то указатель указывает назад, то проверить это проще простого - сравнить адрес проверяемой ячейки и адрес, на который указывает указатель. Если первое больше, то мы нашли решение.
-
-
22.11.2007 в 23:53a1->a2->a3->...->ar->...->ak->ar->...->ak ->ar->...
то есть зацикленный список.
Здесь n - максимальное количество элементов в нем.
-
-
22.11.2007 в 23:56Ты программированием занимаешься?
-
-
22.11.2007 в 23:59Ответ с адресной логикой не принимается. Предполагается, что адреса элементов списка могут идти вразнобой.
Это же список, а не массив
-
-
22.01.2008 в 18:00-
-
23.01.2008 в 17:09Предположим, что мы не можем проверить корректность данных (в данном случае корректность n+1 элемента); например, мы имеем абстрактный список, содержащий только указатели, и значение указателя последнего элемента не определено, а в оперативной памяти хранится мегахаотичный мусор
Короче, эту задачу нужно решить, строго сравнивая между собой указатели.
-
-
23.01.2008 в 19:33Тогда отсортировать указатели и просмотреть полученный список на предмет одинаковых адресов. Только помоему время будет не порядка n, а больше, и для сортированного массива нужно будет еще n ячеек
-
-
23.01.2008 в 19:47По идее можно сравнивать n и n+k указатель, где k изменяется от 1 до длинны списка. Если при каком-то k указатели равны, то можно еще раз проверить для произвольного n и если пару раз будет работать, значит список зациклен.
-
-
25.01.2008 в 12:31DUST. По памяти алгоритм подходит, а вот время работы будет порядка n^2. Кстати, по-моему, в данном алгоритме достаточно первого равенства указателей n и n+k.
Загадка-подсказка: Сколько раз за один оборот часовой стрелки ее догоняет минутная?
-
-
25.01.2008 в 12:48-
-
25.01.2008 в 13:07Смысл n (как я уже писал выше) - максимальное количество элементов в незацикленном списке. Естественно, если список зациклен, то он бесконечен.
-
-
25.01.2008 в 13:19Ну хз. Первого совпадения конечно достаточно, однако мы не знаем, в каком месте список начинает зацикливаться.
-
-
12.06.2009 в 21:54Задача и вправду бессмыслена. Если в однонаправленном списке есть цикл, то он однозначно в конце, так как невозможно, имея в распоряжении один указатель выйти из цикла, если только на этот случай не припрятан ещё один указатель, о чём в условии задачи не сказано. Если нам нужно всего навсего определить, имеется ли цикл, то запустим бесконечный цикл, в котором будем прибавлять счётчик. Так как n известно, то можно сделать простой и логичный вывод, что если счётчик станет больше n, то непорядок и в списке элементов больше, чем должно быть, но такого быть не может, поэтому это цикл. Если я не прав, то переформулируйте условие.
-
-
16.06.2009 в 15:42А какое Вы предлагаете условие для бесконечного цикла? Если while(true), то в любом случае цикл пройдет более n итераций, так как n конечно.
Это собственно и есть главный вопрос задачи. Как я уже писал выше, значение указателя последнего элемента не определено, и невозможно определить, является ли n-й элемент последним, сравнивая значение указателя с некоторой константой.
Еще раз уточню, что ячеек памяти (указателей) по условию задачи может быть больше одной (любое число, главное, чтобы оно не зависело от n).
-
-
11.12.2009 в 23:40данно: 1,2,3,4
1-лжец поскольку если бы он был рыцарем несмог про себя сказать что он лжец
остаёться 2,3,4
тут есть два варианта:
а)допустем что второй рыцарь тогда есть всего один лжец и он 1 значит 4 тоже следовательно рыцарь
б)допустем что второй лжец (тоесть 1,2 лжецы)
тогда остаеться 3 и 4
тут якобы тоже есть два варианта но нет:
3-рыцарь тогда наши лжецы 1,2 и посколку он нам не мог соврать 4 тоже следовательно рыцарь
а если 3- лжец то 4 всё равно рычарь (поскольку 1 солгал что все лжецы ) и из етого следует что 4 неможет быть лжецом
так что по любому 4 рыцарь
-
-
30.12.2010 в 16:10Двигаемся по циклу с шагом 1 и шагом 2 одновременно и каждый раз сравниваем указатели.
На i-том шаге му будем на расстоянии i и 2*i от начала, если есть период d рано или поздно
для какого-то i=k*d мы получим одинаковые указатели.
Псевдокод, надеюсь доступно)
p = head;
q=head;
i=0;
while(i < n) {
p = p->next;
q=q->next->next;
i++;
if (p == q)
return true;
}
return false;
По ходу длина цикла будет делителем i при котором вернется true.