SICP読書女子会 #11,12 1.4.6 返り値としての手続き まとめ

  • 0
    いいね
  • 0
    コメント
    この記事は最終更新日から1年以上が経過しています。

    オンラインSICP読書女子会 #12 (1.3.4)

    1.40 newton法

    (load "./newtons-method.scm")
    (define (cube x) (* x x x))
    
    ; 不動点プロセスで x^3 + a*x^2 + b*x + c = 0 の零点の近似値を求める
    (define (cubic a b c)
      (lambda (x) (+ (cube x)
             (* a (square x))
             (* b x)
             c)))
    
    (newtons-method (cubic -3 3 -1) 1) ;1.0
    

    1.41 手続きを二回適用する手続き

    (define (inc x) (+ x 1))
    
    (define (double f)
      (lambda (x) (f (f x))))
    
    ((double inc) 1) ; 3
    (((double (double double)) inc) 5) ; 21 (+16)
    

    1.42

    関数の合成を実装する手続きをcomposeを実装する

    x -> f(g(x))

    ;; 1.42
    
    (define (compose f g)
      (lambda (x) (f (g x)) ))
    
    (define (square x) (* x x))
    (define (inc x) (+ x 1))
    ((compose square inc) 6) ;; 49
    ((compose square inc) 11) ;; 144
    

    1.43

    n回fを適用する手続き repeatedを

    fがsquareだったら、n回適用すれば引数を2^nする関数になる
    f(f(......f(x)))

    ;; 1.43
    (load "./1.42.scm")
    (define (inc x) (+ x 1))
    
    (define (repeated func n)
      (if (= n 1)
          func
          (compose func (repeated func (- n 1)))))
    
    
    ((repeated square 2) 5) ;; 625
    (time ((repeated inc 10000000) 1))
    ; real   0.558
    ; user   0.550
    ; sys    0.000
    
    ;; hioさんの見習う
    
    (define (repeated func n)
      (cond ((= n 1)
         func)
        ((= (remainder n 2) 1)
         (compose func (repeated func (- n 1))))
        (else
         (let ((f (repeated func (/ n 2))))
           (compose f f)))
        ))
    
    ((repeated square 2) 5) ;; 625
    (time ((repeated inc 10000000) 1))
    ; real   0.552
    ; user   0.540
    ; sys    0.000
    
    
    ;; hioさんの末尾再帰版
    (define (repeated f n)
      (define (iter i val)
        (if (>= i n)
        val
        (iter (+ i 1) (f val))))
      (lambda (x) (iter 0 x)))
    (time ((repeated inc 10000000) 1))
    ; real   0.476
    ; user   0.480
    ; sys    0.000
    ;; そんな時間かわらないな
    ;; これだと手続き
    

    1.44

    平滑化: dxが小さな値であるとき、 f(x - dx), f(x), f(x + dx) の平均をとったもの
    平滑化したものを計算するsmoothの手続きをかけ。
    また、n重平滑化関数をrepeatedを使って示す。

    ;; 1.44
    (load "./1.43.scm")
    
    (define (smooth f)
      (define dx 0.0001)
      (lambda (x)
        (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3) ))
    
    ((smooth square) 2) ;; 4.000000006666666
    
    (define (n-fold-smooth f n)
      (repeated (smooth f) n))
    
    ((n-fold-smooth square 4) 2) ;; 65536.00098646007 (2 ^ 16)
    
    

    1.45 (未解決)

    n乗根を求める

    source

    ;; fixed-point
    (define tolerance 0.0001)
    (define max-recursion 8)
    (define (fixed-point f first-guess)
      (define (close-enough? v1 v2)
        (< (abs (- v1 v2)) tolerance))
    
      (define (try guess i)
        (print "guess:" i "回目 " guess)
        (let ((next (f guess)))
          (if (or (close-enough? guess next) (= i max-recursion))
          next
          (try next (+ i 1)))))
      (try first-guess 1))
    
    (define (average-damp f)
      (lambda (x) (/ (+ (f x) x) 2.0)))
    
    
    ;; 2, 3乗根
    (define (nth-root x n)
      (fixed-point
       (average-damp (lambda (y) (/ x (expt y (- n 1))))) 1.0))
    
    ;;(print (nth-root 100 2)) ;;10.0
    ;;(print (nth-root 1000 3)) ;; 10.000002544054729
    ;; (nth-root 10000 4) ;;無限にfixせず、、、、
    
    
    ;; 4乗根以上
    (define (repeated func n)
      (if (= n 1)
          func
          (compose func (repeated func (- n 1)))))
    
    (define (repeated-nth-root x n m)
      (fixed-point
       (repeated (average-damp (lambda (y) (/ x (expt y (- n 1))))) m) 1.0))
    
    (define (try-repeat m n root)
      (define (iter i)
        (print "----------------------------------")
        (print  m " ^ 1 / " root " の" i "重平均緩和")
        (print "----------------------------------")
        (repeated-nth-root m (+ i 1) root)
        (if (= i n)
        0
        (iter (+ i 1))))
      (iter 1))
    
    (print "2のn乗のn乗根をしらべる")
    
    (print "==========================")
    (print "2乗根")
    (print "==========================")
    (try-repeat (expt 2 2) 3 2)
    
    (print "==========================")
    (print "3乗根")
    (print "==========================")
    (try-repeat (expt 2 3) 5 3)
    
    (print "==========================")
    (print "4乗根")
    (print "==========================")
    (try-repeat (expt 2 4) 5 4)
    
    (print "==========================")
    (print "5乗根")
    (print "==========================")
    (try-repeat (expt 2 5) 10 5)
    

    結果

    2のn乗のn乗根をしらべる

    ==========================
    2乗根
    ==========================
    ----------------------------------
    4 ^ 1 / 2 の1重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 2.05
    guess:3回目 2.0000000929222947
    ----------------------------------
    4 ^ 1 / 2 の2重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.57
    guess:3回目 1.5829814190634435
    guess:4回目 1.586291563873137
    guess:5回目 1.5871233896905939
    guess:6回目 1.5873316181944288
    ----------------------------------
    4 ^ 1 / 2 の3重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.3780000000000001
    guess:3回目 1.3781971576084833
    guess:4回目 1.3783910746470118
    guess:5回目 1.3785818395983083
    guess:6回目 1.3787695375836293
    guess:7回目 1.3789542505257217
    guess:8回目 1.3791360573022022
    ==========================
    3乗根
    ==========================
    ----------------------------------
    8 ^ 1 / 3 の1重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 2.843780727630285
    guess:3回目 2.82842712474619
    ----------------------------------
    8 ^ 1 / 3 の2重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.8914996576441667
    guess:3回目 2.0151199754332096
    guess:4回目 1.998142301706526
    guess:5回目 2.0002326972862416
    guess:6回目 1.999970920454376
    ----------------------------------
    8 ^ 1 / 3 の3重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.478337540623817
    guess:3回目 1.9239087525290877
    guess:4回目 1.5363162465727038
    guess:5回目 1.8553689987180662
    guess:6回目 1.560512615640326
    guess:7回目 1.8244440279220622
    guess:8回目 1.575115962052684
    ----------------------------------
    8 ^ 1 / 3 の4重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.28327359906296
    guess:3回目 2.227954293124733
    guess:4回目 1.2615306050241493
    guess:5回目 2.1609515864967843
    guess:6回目 1.2706420422133782
    guess:7回目 2.192947191071957
    guess:8回目 1.2662518335488215
    ----------------------------------
    8 ^ 1 / 3 の5重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.1951167859192295
    guess:3回目 2.2691905546161637
    guess:4回目 1.1778909647032938
    guess:5回目 2.025355582188155
    guess:6回目 1.393915404078827
    guess:7回目 1.6030012367264348
    guess:8回目 1.2279607772464904
    ==========================
    4乗根
    ==========================
    ----------------------------------
    16 ^ 1 / 4 の1重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 4.002257524798522
    guess:3回目 4.0
    ----------------------------------
    16 ^ 1 / 4 の2重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 2.4829963306881875
    guess:3回目 2.5174777560877635
    guess:4回目 2.5196940687432705
    guess:5回目 2.519832846830349
    ----------------------------------
    16 ^ 1 / 4 の3重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.8341723103276433
    guess:3回目 1.8527375467627856
    guess:4回目 1.8658611343368858
    guess:5回目 1.875827463108303
    guess:6回目 1.8837545613602775
    guess:7回目 1.8902683221588625
    guess:8回目 1.895752040837725
    ----------------------------------
    16 ^ 1 / 4 の4重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.4493508391103145
    guess:3回目 1.4519931178812753
    guess:4回目 1.4536080602027628
    guess:5回目 1.4545943546784106
    guess:6回目 1.455195179157848
    guess:7回目 1.4555603374021737
    guess:8回目 1.4557818914922966
    ----------------------------------
    16 ^ 1 / 4 の5重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.2475321803127808
    guess:3回目 1.9040376089300204
    guess:4回目 1.666016805952454
    guess:5回目 3.1599408649420493
    guess:6回目 1.4616166208630994
    guess:7回目 1.5843404568698387
    guess:8回目 1.540218409475213
    ==========================
    5乗根
    ==========================
    ----------------------------------
    32 ^ 1 / 5 の1重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 5.65697670118682
    guess:3回目 5.65685424949238
    ----------------------------------
    32 ^ 1 / 5 の2重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 3.2611793503277537
    guess:3回目 3.1722582719630483
    guess:4回目 3.1748817299345116
    ----------------------------------
    32 ^ 1 / 5 の3重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 2.464263577716512
    guess:3回目 2.3026699635645205
    guess:4回目 2.460267138779624
    guess:5回目 2.305728778345352
    guess:6回目 2.4567770089373733
    guess:7回目 2.3084377997602075
    guess:8回目 2.4536947950137824
    ----------------------------------
    32 ^ 1 / 5 の4重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.8527388808054341
    guess:3回目 2.986203929953016
    guess:4回目 1.684603068446882
    guess:5回目 2.8502360866346947
    guess:6回目 1.6695442360756085
    guess:7回目 2.8887323780143497
    guess:8回目 1.6735434538049703
    ----------------------------------
    32 ^ 1 / 5 の5重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.4528868735679294
    guess:3回目 3.435041945724486
    guess:4回目 1.4526447052333216
    guess:5回目 3.4265251637273857
    guess:6回目 1.4336537993747493
    guess:7回目 2.5063074888395556
    guess:8回目 1.829979040239805
    ----------------------------------
    32 ^ 1 / 5 の6重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.238771352270022
    guess:3回目 1.8227353362149372
    guess:4回目 1.9525400393432408
    guess:5回目 4.780617424956585
    guess:6回目 1.2363480996581633
    guess:7回目 1.76652059151728
    guess:8回目 1.4114961694924677
    ----------------------------------
    32 ^ 1 / 5 の7重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.1321524709422879
    guess:3回目 6.539943947950366
    guess:4回目 1.466902719615096
    guess:5回目 1.6646927417487603
    guess:6回目 4.484304705092539
    guess:7回目 1.4331808312190746
    guess:8回目 1.8924176928951446
    ----------------------------------
    32 ^ 1 / 5 の8重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.0801710623656842
    guess:3回目 5.215018392022435
    guess:4回目 3.2415512094000114
    guess:5回目 1.5007653145374489
    guess:6回目 5.542008185531579
    guess:7回目 12.058755661446032
    guess:8回目 2.143355616495691
    ----------------------------------
    32 ^ 1 / 5 の9重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.0549588781203105
    guess:3回目 2.114424633995316
    guess:4回目 1.1136325618984133
    guess:5回目 16.786757179080805
    guess:6回目 9.27611486764099
    guess:7回目 2.2729115607246606
    guess:8回目 2.008299076235135
    ----------------------------------
    32 ^ 1 / 5 の10重平均緩和
    ----------------------------------
    guess:1回目 1.0
    guess:2回目 1.0427412930632205
    guess:3回目 1.3213126383907263
    guess:4回目 8.168781903627231
    guess:5回目 5.996862265689423
    guess:6回目 6.317346815038818
    guess:7回目 12.877405341365169
    guess:8回目 29.6151176920096
    
    
    
    • 2乗根:1重平均緩和
      というのが最初にわかっていた内容

    • 3乗根:2重平均緩和(あれ、SICPによると1重平均緩和でできるはず・・・

    • 4乗根は、3重の平均緩和でそれらしい値になる (あれ、SICPによると2重平均緩和でできるはず・・・

    • 5乗根は無理じゃないか・・・

    repeatのn回目nの数え方がおかしい?
    わからなすぎてギブアップ\(^o^)/

    1.46

    十分になるまで改善を繰り返すような手続き(反復改良法)を返す手続き

    (define (iterative-improve improve enough?)
      (lambda (guess)
        (define (iter guess)
          (if (enough? guess)
          guess
          (iter (improve guess))))
        (iter guess)))
    
    ;; sqrt
    (define (sqrt x)
      (define (enough? guess)
        (< (abs (- (square guess) x)) 0.001))
      (define (improve guess)
        (average guess (/ x guess)))
    
      (define (average x y) (/ (+ x y) 2))
      ((iterative-improve improve enough?) 1.0))
    
    (print "sqrt 2 = " (sqrt 2)) ;; 1.4142156862745097
    (print "sqrt 4 = " (sqrt 4)) ;; 2.0000000929222947
    
    
    ;; fix-point
    (define (fix-point f first-guess)
      (define (enough? guess)
        (< (abs (- guess (f guess))) 0.00001))
      (f ((iterative-improve f enough?) first-guess)))
    
    
    ;; golden ratio
    (define (g x)
      (+ 1 (/ 1 x)))
    (print "fix-point golden ratio = " (fix-point g 1.0)) ;;1.6180327868852458
    

    参考 - 問題1.46 – SICP(計算機プログラムの構造と解釈)その24 : Serendip - Webデザイン・プログラミング
    ga