На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Закрыто esperanto 28-09-2004: задача решена
  
> Определить циклы в списке, задачка простенькая
    Есть список, элемент списка - указатель на следующий элемент или NULL. В списке могут быть циклы (элемент указывает на один из предидущих элементов).

    Нужно определить наличие циклов, либо длину списка если циклов нет.

    В случае отсутствия циклов сложность алгоритма должна быть линейна (O(n) кажись?).
    Используемые ресурсы должны быть статичными (не зависящими от размера задачи) - тоесть маркеры пройденных элементов использовать нельзя.

    Решение? :whistle:
    Сообщение отредактировано: Yuri Burger -
      ExpandedWrap disabled
        int smth(list_ *list) {
          count = 0;
          X = head(list);
          while (X != NULL) {
             if (X == 0xdeadbeaf)
                return -1;
             count++;
             if (X->next == NULL)
                return count;
             Y = X;
             X = X->next;
             Y = 0xdeadbeaf;
          };
          return count; // -1 в случае, если цикл
        };


      :D
      Я не могу тебя забыть, ты снишься мне ночами, твой нежный запах, вкус и цвет стоят перед глазами.
      Когда тебя со мною нет, так тоскливо, и без тебя я не могу, мое ПИВО...
        Deil, а можно этот код на Pascal'е, а то я не настолько хорошо знаю С, чтобы понять например это:
        ExpandedWrap disabled
               Y = X;
               X = X->next;
               Y = 0xdeadbeaf;
            
        :huh:
          ExpandedWrap disabled
            var t,tt:the_list;len,thr,i:longint;
            begin
              t:=head;
              tt:=head;
              len:=0;
              thr:=1;
              i:=1;
              while t<>nil do begin
                t:=t^.next;
                if t=tt then break;
                inc(len);
                dec(i);
                if i=0 then begin
                  thr:=2*thr;
                  tt:=t;
                  i:=thr;
                end;
              end;
              if t=nil then begin
                writeln('Dlina=',len);
                exit
              end;
              writeln('There are cycles in the list!');
            end.
          во
          гребаный комстар не дал вчера в 18:00 запостить >:( >:(
          Долог путь в бессмертие... я еще вернусь.
          Профильный скилл "Телепатия" 8%
          ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
          Прошу потестить игру.
            Цитата DEiL @ 22.09.04, 02:30
            ExpandedWrap disabled
               
              ...
                   if (X == 0xdeadbeaf)
                      return -1;
                   count++;
                   if (X->next == NULL)
                      return count;
                   Y = X;
                   X = X->next;
                   Y = 0xdeadbeaf;

            шот я не понял, с какой радости при наличии циклов X станет равным 0xdeadbeaf ?
              Алгоритм DEiLа модифицирует список, а это, наверное, делать нельзя.
              Юзайте Vesperа ! :)
              - Свет мой зеркальце, скажи, да всю правду доложи.
              Я ль на свете всех дурнее, всех ленивей и тупее?!
              Молвит зеркальце в ответ:
              - Ты - придурок, спору нет!
              Но живет на белом свете вот таких еще две трети.
                ExpandedWrap disabled
                  typedef enum {
                    arUnknow,
                    arSuccess,
                    arSpoiled
                  } AnalyzeResult;
                   
                  AnalyzeResult AnalyzeCycle( cCustomListItem *head ){
                    if( head == NULL )return arSpoiled;
                    long deep = 1;
                    cCustomListItem *cursor = head;
                   
                    while( true ){
                      cursor = cursor->next();
                      if( cursor == NULL )return arSpoiled;
                      deep++;
                   
                      cCustomListItem *cursor2 = cursor;
                      for( int i=0;i<deep;i++ ){
                        cursor2 = cursor2->Next();
                        if( cursor2 == NULL )return arSpoiled;
                        if( cursor == cursor2 )return arSuccess;
                      }
                      cursor = cursor2;
                      deep = deep + deep;
                    }
                   
                    return arUnknow;
                  }

                Вроде однопроходный если не ошибся, так как потестить неначем.
                Смысл такой, что берем сначала один элемент, потом крутим от этого элемента не назад а вперед тоже на один. Получаем либо нуль либо цикл либо продолжаем. Если продолжаем, то уже с третьего. Если есть цикл из трех мы повторимся если нет окажимся уже на шестом... и т.д. :whistle:
                Dixi et ahinam levavi.
                  CD_Eater, МЕНЯ юзать не надо :tong: а алгоритм можно.
                  Sazabis, почти то же, что у меня ;)

                  Добавлено
                  только я шел сразу с удвоением, а ты еще единицу прибавляешь время от времени
                  Долог путь в бессмертие... я еще вернусь.
                  Профильный скилл "Телепатия" 8%
                  ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
                  Прошу потестить игру.
                  0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                  0 пользователей:
                  Закрыто esperanto 28-09-2004: задача решена


                  Рейтинг@Mail.ru
                  [ Script Execution time: 0,1083 ]   [ 16 queries used ]   [ Generated: 20.07.19, 22:09 GMT ]