稳中带皮

SICP学习笔记07

vvipi

发表于2018年11月18日,阅读：2530

### 练习1.29 利用辛普森规则，函数f在范围a和b之间的定积分的近似值是： `h/3*[y0 + 4y1 +2y2 + 4y3 + 2y4 + ... + 2yn-2 + 4yn-1 + yn]` 其中h = (b - a) / n, n是某个偶数，而yk = f(a + kh),(增大n能提高近似值的精度）。请定义一个具有参数f、a、b和n，采用辛普森规则计算并返回积分值的过程。用你的函数求出cube在0和1之间的积分。 ### 解答 想出来的第一个解决方案 ```scheme (define (sum term a next b) ; 求和的公共模式，term和next是作为参数的过程，a和b是求和的起点和终点 (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) (define (cube x) (* x x x)) (define (even? x) (= 0 (remainder x 2))) ;判断偶数 (define (simpson term a b n) (let ((h (/ (- b a) n))) (define (factor k) ; 计算y的系数 (cond ((or (= k 0) (= k n)) 1) ((even? k) 2) (else 4))) (define (generate-k term k) ; 计算第k项 (* (/ (- b a) (* 3 n)) (factor k) (term (+ a (* k h))) )) (define (iter-simpson term a b k) ; 求和各项 (if (> a b) 0 (+ (generate-k term k) (iter-simpson term (+ a h) b (+ k 1))))) (iter-simpson term a b 0))) (display (simpson cube 0 1 100)) (exit) ``` ### 改进 上面的过程能够算出答案，但是存在一些问题。一方面是没有用到sum的求和模式，另一方面是变量在函数内部其实不需要重复通过参数传递。考虑了一会儿，改成下面这个。感觉逻辑清晰了一点。 参考答案中提到n不是偶数的时候可以报错提醒，未考虑到这一点。 ```scheme (define (sum term a next b) ; 求和的公共模式，term和next是作为参数的过程，a和b是求和的起点和终点 (if (> a b) 0 (+ (term a) (sum term (next a) next b)))) (define (cube x) (* x x x)) (define (even? x) (= 0 (remainder x 2))) (define (simpson term a b n) (define h (/ (- b a) n)) ; 计算步长 (define (next-a a) (+ a h)) ; a的递推 (define (factor k) ; 计算y的系数 (cond ((or (= k 0) (= k n)) 1) ((even? k) 2) (else 4))) (define (generate-k k) ; 计算第k项 (* (/ (- b a) (* 3 n)) (factor k) (term (+ a (* k h))) )) (define (generate-y ak) ; 从a算出k，代入算出y (define k (/ (- ak a) h)) (generate-k k)) (sum generate-y a next-a b)) ; 求和 (display (simpson cube 0 1 100)) (exit) ``` ### 练习1.31 模仿sum写出一个product过程，它返回给定范围中各点的某个函数值的乘积。分别写出递归版和迭代版。并按下面公式计算pi的近似值： `pi/4 = 2*4*4*6*6*8... / 3*3*5*5*7*7...` ### 解答 ```scheme ; (define (product term a next b) ; 求乘积的公共模板 ; (if (> a b) ; 1 ; (* (term a) ; (product term (next a) next b)))) (define (product term a next b) ; 迭代版本 (define (iter-product a result) (if (> a b) result (iter-product (next a) (* (term a) result)))) (iter-product a 1)) (define (factorial n) ; 阶乘 (define (next a) (+ a 1)) (define (indentity x) x) (product indentity 1 next n)) (define (pi n) ; 用n项乘积计算pi的近似值 (define (numerator k) ; 第k项分子 (if (odd? k) (+ k 1) (+ k 2))) (define (denominator k) ; 第k项分母 (if (odd? k) (+ k 2) (+ k 1))) (define (fn k) ; 第k项 (/ (numerator k) (denominator k))) (define (next a) (+ a 1)) (* 4 (product fn 1 next n))) (display (exact->inexact (pi 666))) ; exact->inexact函数可将分数转化为小数 (exit) ``` 今天学到scheme中引入其他文件中代码的方法，`(load "my-define.ss")` 可以把常用的square、cube等函数放在一个文件中，需要时载入进来，避免总是重复定义这些函数。 吐槽一下schem的中文资料真是挺少的，经常搜不到什么东西。目前看英文资料还是挺费劲的。 ### 练习1.32 sum和product都是另一个成为accumulate的更一般的概念的特殊情况，accumulate使用某些一般性累积函数组合起一系列项： `(accumulate combiner null-value term a next b)` accumulate与sum和product比，又多了一个combiner过程，它描述如何将当前项和前面各项积累结果组合起来，另外还有null-value参数，表示所有项都用完时的基本值。写出递归版和迭代版accumulate，并在其基础上重新定义sum和product。 ### 练习1.33 可以通过引入一个处理被组合项的过滤器(filter)概念，写出accumulate的更一般的版本。在计算过程中，只组合起有给定范围得到的项里那些满足特定条件的项。写出这个filtered-accumulate过程，并用它求以下内容。 1、求出区间a到b的所有素数之和（假设已经写出了prime?) 2、小于n的所有与n互素的正整数的乘积。即与n最大公约数为1切小于n的正整数的乘积。 ### 解答 ``` (load "my-define.ss") ; 载入prime?,gcd等函数 (define (accumulate combiner null-value term a next b) ； 一般化组合过程 (if (> a b) null-value (combiner (term a) (accumulate combiner null-value term (next a) next b)))) (define (sum term a next b) ; 重新定义求和 (accumulate + 0 term a next b)) (define (product term a next b) ; 重新定义求乘积 (accumulate * 1 term a next b)) ; 带过滤器的组合过程 (define (filtered-accumulate combiner null-value filter? term a next b) (define (iter-accu a result) (if (> a b) result (iter-accu (next a) (combiner result (if (filter? a) (term a) null-value))))) (iter-accu a null-value)) (define (next a) (+ a 1)) (define (sum-prime a b) ; a到b区间素数求和 (filtered-accumulate + 0 prime? indentity a next b)) (define (product-gcd n) ; 小于n与n互素的数求乘积 (define (primeto? x) (if (and (= (gcd x n) 1) (not (= x n))) #t #f)) (filtered-accumulate * 1 primeto? indentity 1 next n)) (display (sum-prime 1 10)) (newline) (display (sum-prime 1 100)) (newline) (display (product-gcd 10)) (exit) ```