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
今回は環境を共有している部分がある。
図は面倒なので、略!