LoginSignup
0
0

More than 5 years have passed since last update.

@cocodrips(くーむ)

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

Last updated at Posted at 2016-06-08

オンライン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

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0