Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Экзаменационная задача / 19 сообщений из 19, страница 1 из 1
26.10.2010, 01:34
    #36919293
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
ЗадачаЕсть связный список неизвестной размерности. В этом списке возможно есть цикл. Требуется сочинить алгоритм проверяющий есть цикл или нет.
Изменять реализацию списка и его нод нельзя.
Можно создать дополнительную внешнюю структуру с количеством элементов не больше чем размер списка.

Вопрос: существует ли реалистичный алгоритм с быстродействием O(N)?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 02:07
    #36919311
clihlt
clihlt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
White Owl,

Эммм
Не понятно
White Owl
Есть связный список неизвестной размерности

В смысле не извесно сколько элементов в списке ?

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

Пусть доп внешняя структура - это список - имеет следующие поля:
1) Адрес следующего элемента в оригинальном списке - next_orig
2) Адрес след элемента. - next ( как и в обычном списке для связности )
3) Индекс текущего элемента - i

Алгоритм:
Для каждого элемента из оригинального списка
- Если поле адреса след элемента == NULL
то нет в этом списке циклов. Выход из цыкла.
- Иначе Если поле адреса след элемента < Колличество элементов в доп структурке
то цикл есть. Выход из цикла
- Иначе в доп структуру добавляем новый элемент, такой что
next_orig = Адрес след элемента из оригинально списка
i = Колличество элементов в доп структурке
В оригинальный список в поле адреса след элемента проставляем Колличество элементов в доп структурке
Колличество элементов в доп структурке инкрементируем на 1.
Конец цикла

Выполняем востановление адресов в оригинальном списке.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 06:44
    #36919407
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Ой, прошу прощения, там конечно должно быть "неизвестного размера".
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 07:22
    #36919421
Barlone
Barlone
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Для односвязного списка можно без дополнительных структур, примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
bool HasLoop(Node top) {
  Node a,b;
  a=top;
  if (a==NULL) return false;
  b = a.next;
  while (b!=a && b!=NULL) {
    a=a.next;
    b=b.next;
    if(b==NULL) break;
    b=b.next;
  }
  return b==a;
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 09:51
    #36919609
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
ЗадачаИзменять реализацию списка и его нод нельзя.
clihltВ оригинальный список в поле адреса след элемента проставляем Колличество элементов в доп структурке...
Выполняем востановление адресов в оригинальном списке.Тут надо уточнить у ТС, можно ли менять исходный список на время выполнения алгоритма.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 10:56
    #36919807
Берлuнгер
Берлuнгер
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
я так понимаю, что список -- Н-мерный, количество элементов которого неизвестны?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 10:59
    #36919814
Берлuнгер
Берлuнгер
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Яростный МечЗадачаИзменять реализацию списка и его нод нельзя.
clihltВ оригинальный список в поле адреса след элемента проставляем Колличество элементов в доп структурке...
Выполняем востановление адресов в оригинальном списке.Тут надо уточнить у ТС, можно ли менять исходный список на время выполнения алгоритма.
подозреваю, что нет...

либо искать цикл всякими графами, либо рекурсиями пытатся зациклится... в любом случае задача не есть легкая... в случае рекурсий. в любом случае нужна дополнительная память...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 11:06
    #36919839
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Берлuнгеря так понимаю, что список -- Н-мерный, количество элементов которого неизвестны?Скорее всего, обычный линейный список (односвязный), у которого next последнего узла может быть null или указывать на любой узел (будет цикл).
К тому же неизвестно, задача для С++ или нет (к примеру в С# нет доступа к числовому представлению адреса - доп. ограничение).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 11:10
    #36919852
Берлuнгер
Берлuнгер
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Яростный МечБерлuнгеря так понимаю, что список -- Н-мерный, количество элементов которого неизвестны?Скорее всего, обычный линейный список (односвязный), у которого next последнего узла может быть null или указывать на любой узел (будет цикл).
К тому же неизвестно, задача для С++ или нет (к примеру в С# нет доступа к числовому представлению адреса - доп. ограничение).
если линейный, то решается обычным проходом (быстрее все равно не получится)
но судя по "список неизвестной размерности" -- возможно речь идет именно о неизвестном количестве ветвей в узле...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 11:24
    #36919892
Mozok
Mozok
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
White OwlЗадачаЕсть связный список неизвестной размерности. В этом списке возможно есть цикл. Требуется сочинить алгоритм проверяющий есть цикл или нет.
Изменять реализацию списка и его нод нельзя.
Можно создать дополнительную внешнюю структуру с количеством элементов не больше чем размер списка.

Вопрос: существует ли реалистичный алгоритм с быстродействием O(N)?
Задача древняя, как мир, где-то уже постилась на этом форуме.
Одно из решений:
1. Создаются два итератора (назовем их быстрый и медленный).
2. Медленный выставляется на начало списка, быстрый - на элемент, следующий зан им.
3. Порверяем, равны ли друг другу элементы, на которые указывают итераторы.
Если да, то цикл существует.
Если нет, продвигаем быстрый итератор на 2 элемента вперед, медленный - на 1 элемент вперед.
4. Вернуться к п. 3.
Пример реализации:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
(defun getCycleIt (src)
    (declare (list src))
    (loop for slowP = src then (cdr slowP)
        for fastP = (cdr src) then (cddr fastP)
        until (endp fastP)
        do (if (eq (car slowP) (car fastP))
            (return t)
            )
        )
    )
)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 18:07
    #36921103
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
BarloneДля односвязного списка можно без дополнительных структур, примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
bool HasLoop(Node top) {
  Node a,b;
  a=top;
  if (a==NULL) return false;
  b = a.next;
  while (b!=a && b!=NULL) {
    a=a.next;
    b=b.next;
    if(b==NULL) break;
    b=b.next;
  }
  return b==a;
}
Мило, но быстродействие будет намного хуже чем у самого примитивного алгоритма с O(N^2).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 18:10
    #36921108
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Яростный МечТут надо уточнить у ТС, можно ли менять исходный список на время выполнения алгоритма.В исходном тексте есть запрет на изменение структуры, изменение данных в оригинальном списке явно запрещено не было. Так что clihit пока лидирует :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 18:21
    #36921137
White Owl
White Owl
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
White OwlBarloneДля односвязного списка можно без дополнительных структур, примерно так:Мило, но быстродействие будет намного хуже чем у самого примитивного алгоритма с O(N^2).Нет, беру свои слова обратно. С итераторами получается в пределах O(N).
Итераторы могут в принципе сделать пару кругов по кольцу, но в максимуме это будет a+2b, где a+b=N. То есть O(N) выполняется.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 18:24
    #36921149
junior idiot
junior idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
White OwlBarloneДля односвязного списка можно без дополнительных структур, примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
bool HasLoop(Node top) {
  Node a,b;
  a=top;
  if (a==NULL) return false;
  b = a.next;
  while (b!=a && b!=NULL) {
    a=a.next;
    b=b.next;
    if(b==NULL) break;
    b=b.next;
  }
  return b==a;
}
Мило, но быстродействие будет намного хуже чем у самого примитивного алгоритма с O(N^2).
А по-моему, сложность линейна. Переменная b пробежится по петле не более двух раз.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 18:28
    #36921159
Берлuнгер
Берлuнгер
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
White OwlBarloneДля односвязного списка можно без дополнительных структур, примерно так:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
bool HasLoop(Node top) {
  Node a,b;
  a=top;
  if (a==NULL) return false;
  b = a.next;
  while (b!=a && b!=NULL) {
    a=a.next;
    b=b.next;
    if(b==NULL) break;
    b=b.next;
  }
  return b==a;
}
Мило, но быстродействие будет намного хуже чем у самого примитивного алгоритма с O(N^2).
ЩИТО ?

тут быстродействие (точнее не быстродействие, а сложность) - O(N*2)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 18:30
    #36921161
Берлuнгер
Берлuнгер
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
на самом деле линейный цикл неинтересно искать (есть чоткий алгоритм).

вопрос -- как искать на дереве с произвольным числом узлов в сети без изменения элементов
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.10.2010, 19:10
    #36921285
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
Берлuнгер O(N*2)
это и есть O(N)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.10.2010, 01:11
    #36921715
XM
XM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
дык, тупо создаём хеш-таблицу для хранения посещенных узлов, и далее при проходе (все равно как - хоть линейный список, хоть граф со многими ветвями) проверяем наличие в хеше за O(1): прекращаем если есть (цикл!), или добавляем в хеш и идем дальше.
O(N), не?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
27.10.2010, 09:17
    #36921929
Barlone
Barlone
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Экзаменационная задача
XMдык, тупо создаём хеш-таблицу для хранения посещенных узлов, и далее при проходе (все равно как - хоть линейный список, хоть граф со многими ветвями) проверяем наличие в хеше за O(1): прекращаем если есть (цикл!), или добавляем в хеш и идем дальше.
O(N), не?
Ну это смотря как проходить.
A->B
A->C
B->C
Вроде не цикл. Но если сначала занесли в хеш A, потом B и C, а дальше смотрим, что из B ссылка на C, который уже в хеше, и что?

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

Только O(N) никак не получится - может быть N^2 ветвей.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Экзаменационная задача / 19 сообщений из 19, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 486ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1343362]:
 0ms
get settings:
 6ms
get forum list:
 16ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 186ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 57ms
get tp. blocked users:
 1ms
others: 204ms
total:  486ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]