计算机程序的构造和解释(SICP) Assignment 4 Continued fractions

这次回顾Assignment 4 Continued fractions。

学习资料：

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-001-structure-and-interpretation-of-computer-programs-spring-2005/index.htm

https://github.com/DeathKing/Learning-SICP

https://mitpress.mit.edu/sites/default/files/sicp/index.html

https://www.bilibili.com/video/BV1Xx41117tr?from=search&seid=14983483066585274454

作业地址：

https://mitpress.mit.edu/sites/default/files/sicp/psets/index.html

Exercise 2.3

公式：

$$\sin(x) = 3\sin \left(\frac x 3\right) - 4\sin^3 \left(\frac x 3\right)$$

如果

$$\frac{x}{3^n} < \epsilon$$

则迭代终止。

所以迭代次数为

$$O\left(-\log \left(\epsilon\right) \right)$$

Exercise 2.4

$$\begin{aligned} \text{((repeated square 2) 5)}&= (5^2)^2=625\\ \text{((repeated square 5) 2)}&= ((((2^2)^2)^2)^2)^2=2^{32} \end{aligned}$$

代码：

(define (repeated p n)
    (cond ((= n 0) (lambda (x) x))
          ((= n 1) p)
          (else (lambda (x) (p ((repeated p (-1+ n)) x))))))

((repeated square 2) 5)

((repeated square 5) 2)

实验结果：

1 ]=> ((repeated square 2) 5)
;Value: 625

1 ]=> ((repeated square 5) 2)
;Value: 4294967296

Pre-Lab Exercise 2.1

这里假设

$$\begin{aligned} N_i&=n \\ D_i&=d\\ i&\in \mathbb N^+ \end{aligned}$$

记

$$\begin{aligned} f_1&=\frac{n_1}{d_1}\\ f_{k+1} &=\frac{n_1}{d_1 + f_k} \end{aligned}$$

代码：

(define (cont-frac-r n d k)
    (define (rec i)
        (if (= i k)
            (/ (n i) (d i))
            (/ (n i) (+ (d i) (rec (+ i 1))))))
    (rec 1))

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

(* (cont-frac-r 
        (lambda (i) 1)
        (lambda (i) 1)
        10) 1.0)

(* (cont-frac-i 
        (lambda (i) 1)
        (lambda (i) 1)
        10) 1.0)

实验结果：

1 ]=> (* (cont-frac-r 
        (lambda (i) 1)
        (lambda (i) 1)
        10) 1.0)
;Value: .6179775280898876

1 ]=> (* (cont-frac-i 
        (lambda (i) 1)
        (lambda (i) 1)
        10) 1.0)
;Value: .6179775280898876

Lab Exercise 2.2

代码：

(load "lab_e2.1.scm")

(define (cont-frac n d k)
    ; (cont-frac-r n d k))
    (cont-frac-i n d k))

(define (estimate-pi k)
    (/ 4 (+ (brouncker k) 1)))

(define (square x) (* x x))

(define (brouncker k)
    (cont-frac (lambda (i) (square (- (* 2 i) 1)))
               (lambda (i) 2)
               k))

(* (estimate-pi 100) 1.0)

实验结果：

1 ]=> (* (estimate-pi 100) 1.0)
;Value: 3.1514934010709905

Pre-Lab Exercise 2.3

代码：

(load "lab_e2.1.scm")

(define (cont-frac n d k)
    ; (cont-frac-r n d k))
    (cont-frac-i n d k))

(define pi/4 (atan 1 1))
(define pi (* 4 pi/4))

(define (atan-cf k x)
    (/ x 
        (+ 1 
            (cont-frac-i
                (lambda (i) (square (* i x)))
                (lambda (i) (+ (* 2 i) 1))
                k))))

( * (atan-cf 10 1) 1.0)

(atan 1)

实验结果：

1 ]=> ( * (atan-cf 10 1) 1.0)
;Value: .7853981682575837

1 ]=> (atan 1)
;Value: .7853981633974483

Lab Exercise 2.4

略过。

Pre-Lab Exercise 2.5

代码：

(define (nested-acc op r term k)
    (define (iter i res)
        (if (= i k)
            res
            (iter (+ i 1) ((op i) res (term i)))))
    (iter 0 r))

(define (sqrt_ a b)
    (sqrt a))

(define (f x k)
    (define (op i)
        (if (= (remainder i 2) 0)
            +
            sqrt_))
    (define (term i)
        x)
    (nested-acc op 0 term k))

(f 1 100)

Exercise 2.6

实验结果：

(f 1 100)
;Value: 1.618033988749895

Lab Exercise 2.7

计算方式：

$$\begin{aligned} \sin x &=\sum_{i=1}^{\infty}\frac {(-1)^{i+1}} {(2i-1)!} x^{2i-1} \end{aligned}$$

代码：

(define (nested-acc op r term k)
    (define (iter i res)
        (if (= i k)
            res
            (iter (+ i 1) ((op i) res (term i)))))
    (iter 0 r))

(define (fact i)
    (define (iter j res)
        (if (> j i)
            res
            (iter (+ j 1) (* j res))))
    (iter 1 1))

(define (f x k)
    (define (op i)
        +)
    (define (term i)
        (let ((j (- (* 2 i) 1)))
            (if (= i 0)
                0
                (/ (* (expt -1 (+ i 1)) (expt x j)) (fact j)))))
    (nested-acc op 0 term k))

(define pi/4 (atan 1 1))
(define pi (* 4 pi/4))

(* (f (/ pi 6) 20) 1.0)
(sin (/ pi 6))


(* (f 1 100) 1.0)
(sin 1)

实验结果：

1 ]=> (* (f (/ pi 6) 20) 1.0)
;Value: .49999999999999994

1 ]=> (sin (/ pi 6))
;Value: .49999999999999994

1 ]=> (* (f 1 100) 1.0)
;Value: .8414709848078965

1 ]=> (sin 1)
;Value: .8414709848078965

Pre-Lab Exercise 2.8

前两项的结果：

$$\begin{aligned} \frac{1}{2 + 3} &=\frac 1 5\\ \frac{1}{2 + \frac 1 5} &=\frac 5 {11} \end{aligned}$$

代码：

(define (repeated p n)
    (cond ((= n 0) (lambda (x) x))
          ((= n 1) p)
          (else (lambda (x) (p ((repeated p (-1+ n)) x))))))

(define (build n d b)
    (/ n (+ d b)))

(define (repeated-build k n d b)
    (define (build_ x)
        (build n d x))
    ((repeated build_ k) b))

(repeated-build 1 1 2 3)

(repeated-build 2 1 2 3)

(* (repeated-build 100 1 1 1) 1.0)

实验结果：

1 ]=> (repeated-build 1 1 2 3)
;Value: 1/5

1 ]=> (repeated-build 2 1 2 3)
;Value: 5/11

1 ]=> (* (repeated-build 100 1 1 1) 1.0)
;Value: .6180339887498949

Exercise 2.9

见2.8。

Exercise 2.10

代码：

(define (repeated p n)
    (cond ((= n 0) (lambda (x) x))
          ((= n 1) p)
          (else (lambda (x) (p ((repeated p (-1+ n)) x))))))

(define (r k)
    (define (f x)
        (/ 1 (+ 1 x)))
    (repeated f k))

((r 2) 0)

((r 3) 0)

((r 4) 0)

实验结果：

1 ]=> ((r 2) 0)
;Value: 1/2

1 ]=> ((r 3) 0)
;Value: 2/3

1 ]=> ((r 4) 0)
;Value: 3/5

Optional Problem

代码：

(define (cont-frac-r n d k)
    (define (iter i ab1 ab2)
        (if (= i k)
            (/ (car ab1) (cdr ab1))
            (iter (+ i 1) 
                  (cons (+ (* (d i) (car ab1)) (* (n i) (car ab2)))
                        (+ (* (d i) (cdr ab1)) (* (n i) (cdr ab2))))
                  ab1)))
    (iter 1 (cons 0 1) (cons 1 0)))

(define (atan-cf k x)
    (/ x 
        (+ 1 
            (cont-frac-r
                (lambda (i) (square (* i x)))
                (lambda (i) (+ (* 2 i) 1))
                k))))

(* (atan-cf 10 1) 1.0)
(atan 1)

(* (atan-cf 10 2) 1.0)
(atan 2)

实验结果：

1 ]=> (* (atan-cf 10 1) 1.0)
;Value: .785398135111635

1 ]=> (atan 1)
;Value: .7853981633974483

1 ]=> (* (atan-cf 10 2) 1.0)
;Value: 1.1070217228310255

1 ]=> (atan 2)
;Value: 1.1071487177940904