SICP 読み (6)

scheme SICP

正月恒例の吉本の漫才番組を見つつ 1 章の残りを。
14:00 から家の近くで獅子舞とか旗頭行列があるらしい。で、2 日午後からの悪い頭で検討したナニを以下に。

問題 1.35

黄金比Φ は 1.2.2 節の解説によれば

Φ * Φ = Φ + 1

との事なんで両方を Φ で割れば

Φ = 1 + 1/Φ

になるな。
これを以下な fixed-point にあてはめてみる。

(define tolerance 0.000001)
(define (fixed-point f first-guess)
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (if (close-enough? guess next)
	  next
	  (try next))))
  (try first-guess))

試験な手続きを書いてないな。

guile> (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
1.61803381340013
guile>

SICP の 21p によれば Φ は 1.6180 なってますので、OK で良いかな。

問題 1.36

問題 1.22 はスルーだったな。あら、今気がついたんですがこのあたりで prime? の定義なサンプルが出てるのか。27p から 31p までは早目にやっておいた方が良いな。

一応やってみた。セイフかダウトかは不明。

guile> (fixed-point (lambda (x) (/ (log 1000) (log x))) 1.1)
1.1
72.4765737842904
1.61273184741096
14.4535013863653
2.58626694153851
7.26967227336705
3.48223836208485
5.5365008102367
4.03640640628811
4.95053682041456
4.3187073901808
4.7217787871451
4.45034106888491
4.62682143410612
4.50936094529321
4.58634950091551
4.53537263959459
4.56890148484532
4.54675110077754
4.56134197174174
4.55171223064123
4.55805967167759
4.55387226495538
4.55663317765417
4.55481214469646
4.55601296773654
4.55522099768331
4.55574326555224
4.55539883024365
4.55562597481627
4.55547617543217
4.55557496455779
4.55550981463675
4.55555277964776
4.55552444496116
4.55554313113059
4.55553080793852
4.5555389348485
4.55553357530074
4.55553710982149
4.55553477887058
4.55553631608902
4.55553530232207
4.55553597088242
guile> (fixed-point (lambda (x) (+ (/ x 2) (* (/ 1 2) (/ (log 1000) (log x))))) 1.1)
1.1
36.7882868921452
19.3521755318825
10.8418336795757
6.87004835214177
5.22722496196716
4.70196019515929
4.58219677320112
4.56013422970368
4.55632041943096
4.55566936178404
4.55555846297564
4.55553957996306
4.55553636491178
4.55553581751808
guile>

問題 1.37 (無限連分数の展開)

こんな感じかなぁ。

(define f (lambda (x) 1.0))
(/ 1 (+ 1 (cont-frac f f (- k 1))))

て事は再帰的なナニだと以下でよいかなぁ。

(define (cont-frac n d k)
  (if (= k 0)
      0
      (/ (n k) (+ (d k) (cont-frac n d (- k 1))))))

動かしてみる。

guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 100)
0.618033988749895
guile> (/ 1 1.6180)
0.618046971569839
guile>

一応近い値にはなってるなぁ。一応小数点以下 4 桁は合ってはいるのですが、再帰なのであまり k をでっかい値にできん。反復版はどう書けば良いのか。

てーか、なにか勘違いしてる気がする。がしかし、とりあえずスルーで考えよう、と思いつつどうやれば良いのかさっぱり分からんぞ。頭悪いなぁ。

で、一日が経過してようやく法則みたいなのを発見。以下で OK かなぁ。

  • 一回目 : (/ 1 1) => 1
  • 二回目 : (/ 1 (+ 1 (/ 1 1))) => 1/2
  • 三回目 : (/ 1 (+ 1 (/ 1 (+ 1 (/ 1 1))))) => 2/3
  • 四回目 : (/ 1 (+ 1 (/ 1 (+ 1 (/ 1 (+ 1 (/ 1 1))))))) => 3/5
  • 五回目 : (/ 1 (+ 1 (/ 3 5))) => 5/8
  • 六回目 : (/ 1 (+ 1 (/ 5 8))) => 8/13
  • 七回目 : (/ 1 (+ 1 (/ 8 13))) => 13/21
  • 八回目 : (/ 1 (+ 1 (/ 13 21))) => 21/34

続く

てコトはこんなカンジで OK か。

(define (cont-frac n d k)
  (let f ((n n) (d d) (k k) (result 1))
    (if (= k 0)
	result
	(f n d (- k 1) (/ (n k) (+ (n k) result))))))

試験な手続きも書きたいが ...

guile> (/ 1 1)
1
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 0)
1
guile> (/ 1 2)
0.5
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 1)
0.5
guile> (/ 2 3)
0.666666666666667
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 2)
0.666666666666667
guile> (/ 3 5)
0.6
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 3)
0.6
guile> (/ 5 8)
0.625
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 4)
0.625
guile> (/ 8 13)
0.615384615384615
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 5)
0.615384615384615
guile> (/ 13 21)
0.619047619047619
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 6)
0.619047619047619
guile> (/ 21 34)
0.617647058823529
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 7)
0.617647058823529
guile> (/ 34 55)
0.618181818181818
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 8)
0.618181818181818
guile> (/ 55 89)
0.617977528089888
guile> (cont-frac (lambda (x) 1.0) (lambda (x) 1.0) 9)
0.617977528089888
guile>

やってる事同じなので値は同一にならんとおかしいんだけど。

やっぱ手と紙を使わんとこういったナニは分からんな。(とほほ

続き

問題 1.38 および 1.39 を解くにあたっては上記の 1.37 の解では微妙なカンジ。スルー分も含めてもう一度確認した方が良いな。

現時点でスルーしている問題

備忘録まで

  • 問題 1.1 〜 4
  • 問題 1.7、8
  • 問題 1.11 〜 15
  • 問題 1.19
  • 1.2.5 および 6 節
  • 問題 1.20 〜 29
  • 問題 1.38 および 39 (1.37 の再検討??)

結構多いな。あまり現実トウヒのネタは欲しくないのですが ...