>
>http://d.hatena.ne.jp/lethevert/20070108/p1
>について scheme で解いた。→
>http://www.lingr.com/room/gauche/archives/2007/01/08#msg-709706
>
議論を追っていけばわかるけど、最初のやつは間違えている。
>
>ちなみになんで scheme かというと、 C で書くのは面倒だったから。一方で Haskell では、ノードの物理的な一致関係を計算するのがけっこう面倒なのです。
>
>(use srfi-1)
(define (chased-cell l)
(let loop ((h (cddr l)) (t (cdr l)))
(if (eq? h t) h (loop (cddr h) (cdr t)))))
(define (ring-size r)
(let loop ((c (cdr r)) (n 1))
(if (eq? c r) n (loop (cdr c) (+ n 1)))))
(define (circular-length l)
(define (loop l1 l2 s)
(if (eq? l1 l2) s (loop (cdr l1) (cdr l2) (+ s 1))))
(let* ((c (chased-cell l)) (rs (ring-size c)))
(loop l (drop l rs) rs))
(define (same-circular? l1 l2)
(define (check c1 c2)
(let loop ((c3 (cdr c1)))
(cond ((eq? c2 c3) #t)
((eq? c1 c3) #f)
(else (loop (cdr c3))))))
(check (l1c (chased-cell l1)) (l2c (chased-cell l2))))
>
>で、解説も Lingr の議論を見ればいいんだけど。
>
>3の方が簡単だから先に解説。そもそも循環リストかどうかの判定アルゴリズムには
>Gaucheクックブック
> にありますが、「うさぎとカメ」のアルゴリズムを使う。セルを2個ずつ移動するうさぎポインタと1個ずつ移動するカメポインタを用意して、リストの終端に到達したら循環でないし、うさぎがカメに追い付いたら循環している。両方動いているのがポイントで、1個しか動かさないとすると、リストの最初はふつうだけど先の方が循環しているようなリストに対応できないってわけ。
>
>さて、以上の考えかたをもとにうさぎがカメに追い付かせてみると、その追い付いたポインタは必ず循環リストでぐるぐるまわる中にある。2つの循環リストのどこかが共有されていると、かならずこのリングは共有されるはずで、そのときには一方のポインタから順番に辿っていくと、もう一方のリストの追い付きポイントに到達するはず。そうならずに自分の追い付きポイントに戻っちゃったとしたら、リングは共有されていないということになるから、判定できる。
>
>で、問題2が難しい。自分がリングだけのときには簡単で、1つずつ進めていって自分自身に戻ってきたときのステップ数がリングの大きさになる。ところが、リストの先の方がリングになっているとこれが上手く行かない。どうするか。
>
>まず同じく「うさぎとカメ」の要領で追い付きポイントを決める。すると先述したようにそこは循環している中なんだから、そこから1歩ずつ進めれば、循環部分の大きさがわかる。この大きさをnとしよう。
>
>そこで、もとのリストの先頭からn歩だけ進んだ点を用意する。そして、先頭とその点とを、いっしょに1歩ずつ動かす。すると、循環リストに接続するところでちょうど衝突する。だからそこまでの歩数を調べると、循環リストに接続するまでの長さもわかる。ので、リストの長さ(というかノード数)が調べられる。
>
>ってわけです。
>
