Xeraph@NCHOVY

토끼와 거북이 알고리즘

앗.. 트랙백 걸고 보니 바보같이 hare를 무의식 중에 hair로 쳤다 -_-;;;

리스트를 살펴보고 그 속에 고리가 들어 있는지 살펴보는 프로시저를 만들어라. 리스트 속에 고리가 있다면, 리스트 끝을 cdr 연산으로 찾으려 해도 끝이 나지 않는다. 딱 정해진 만큼의 공간만 쓰는 알고리즘을 만들어 풀어 보아라.

(define (cycle? lst)
  (define (race tortoise hare)
    (cond ((eq? tortoise hare) #t)
          ((null? tortoise) #f)
          ((null? hare) #f)
          ((null? (cdr tortoise)) #f)
          ((null? (cdr hare)) #f)
          (else (race (cdr tortoise) (cddr hare)))))
 
  (race (cdr lst) (cddr lst)))

(define cycle '(a b c))
(set-cdr! (cddr cycle) cycle)

(cycle? cycle)
(cycle? '(1 2 3 4 5))