SICPを読む(102) 問題 3.16 - 3.20 対の数

ガンガンいくぞー。

問題 3.16

Benの手続きがうまくいかい理由。

(define a (cons 0 1))
(define b (cons 2 3))

(count-pairs (cons a b)) ; 3

(set-car! b a)
(count-pairs (cons a b)) ; 4

(set-car! b a)
(set-cdr! b a)
(count-pairs (cons b b)) ; 7

無限ループはパス・・・。

問題 3.17

Benのを修正する。

(define (count-pairs x)
  (letrec ((cache '())
           (iter (lambda (x)
                   (if (not (pair? x))
                       0
                       (+ (iter (car x))
                          (iter (cdr x))
                          (if (find (lambda (a) (eq? a x)) cache)
                              0
                              (begin  (set! cache (cons x cache))
                                      1)))))))
          (iter x)))

(define a (cons 0 1))
(define b (cons 2 3))

(count-pairs (cons a b)) ; 3

(set-car! b a)
(count-pairs (cons a b)) ; 3

(set-car! b a)
(set-cdr! b a)
(count-pairs (cons b b)) ; 3

禁断のset!を使ってしまった・・・。

問題 3.18

循環リストかどうか。

ウサギとカメのアルゴリズムを利用して、カメが1歩、ウサギが2歩進むようにする。ウサギがカメに追いついたら循環している。

(define (cycle? l)
  (letrec ((iter (lambda (u k)
                   (cond ((or (null? u) (null? (cdr u))) #f)
                         ((eq? u k) #t)
                         (else
                           (iter (cddr u) (cdr k)))))))
          (iter (cdr l) l)))

(cycle? '(a b c d)) ; #f
(cycle? (cons 'hoge (make-cycle '(a b c d)))) ; #t

ツリーには未対応。割と簡単だったり。(SRFI-1の仕様を見たところ、初回のウサギを先に進めてなかった)


ウサギはカメさんを追い抜いちゃったりしないの!?とか思ったけど、偶数でも奇数でもうまくいく。不思議だ。

ウサギとカメの考察

なぜ追い抜かないのか考える。

  • 2歩前にカメがいたら、次のカウントでカメは1歩前にいる。
  • 1歩前にカメがいたら、次のカウントで追いつく。

1カウントで1歩づつ差が詰まるので、絶対に追い抜くことは無い。

へぇぇ。おもろいな。

問題 3.19

うぅん。どういう意味かわからん・・・。と、考え込んでいたら、前の問題の答えがソレで。

3.18は、辿ったリストのキャッシュを検索する方法で見るみたい。アルゴリズムを知ってると他の考え方が浮かばない(汗

問題 3.20

今回は環境を共有している部分がある。

図は面倒なので、略!