Проверьте список для циклов


Из SICP:

Упражнение 3.18. Написать процедуру, которая рассматривает список и определяет, является ли она содержит цикл, то есть ли программа, которая пыталась найти конец из списка путем принятия последовательных кдрс пошел бы в бесконечный цикл. Упражнение 3.13 построены такие списки.

Я написал следующее (пересмотренное решение):

(define (has-cycle? l)
  (define (rec nodes-visited remains)
    (define (leaf? node) (not (pair? node)))
    (define (have-seen? node)
      (define (rec rest)
        (if (null? rest) #f
             (or (eq? (car rest) node)
                 (rec (cdr rest)))))
      (rec nodes-visited))
    (cond
      ((leaf? remains) #f)
      ((have-seen? remains) #t)
      (else
       (or (rec (cons remains nodes-visited) (car remains))
           (rec (cons remains nodes-visited) (cdr remains))))))
  (rec '() l))

(define (last-pair x)
  (if (null? (cdr x))
      x
      (last-pair (cdr x))))

(define a '(a b c))
(has-cycle? a)
(set-car! (last-pair a) a)
a
(has-cycle? a)

(define b '(a b c))
(set-car! b (last-pair b))
b
(has-cycle? b)

(define c '(a b c d))

(set-car! (cddr c) (cdr c))
c
(has-cycle? c)

(define d (cons 'z a))
d
(has-cycle? d)

(define e '(a b c d e))
e
(has-cycle? e)
  1. Как его можно улучшить?

Упражнение 3.19. Повторить упражнение 3.18 с помощью алгоритма, который принимает только постоянный объем пространства. (Это требует очень умная мысль.)

  1. Я не знаю, как до сих пор выполнить это требование.


552
5
задан 20 мая 2011 в 04:05 Источник Поделиться
Комментарии
1 ответ

Я не могу выразить это в Lisp, но идея такова:

использовать два указателя, на старте оба списка голове. Тогда, приращение одного указателя на 1, а другой 2. Если вы обнаружили две равные объектов, в конечном счете, это означает, что список имеет петли. В псевдо-код:

P0 = head;
P1 = head;
while(P0 != null and P1 != null) // Detect end of the list
P0 = next(P0);
P1 = next(next(P1));
if ( *P0 == *P1 ) signal loop detected
end while

Конечно, объекты списка должны быть четкими, сравнимыми, и следующая функция должна быть правильной.

Доказательство не сложно. Во-первых, рассмотрим случай "чистого" цикла, когда хвост связан с головой.

На шаге N (где n-й итерации цикла while в коде), Р0-за пункта (п п) и Р1 на товар (2Н мод Н), которые равны, если n является конечной и N П == 0, или просто н = н

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

Надеюсь, что это помогает. Вы можете узнать больше о цикле обнаружения в Википедии.

3
ответ дан 16 марта 2012 в 01:03 Источник Поделиться