随兴做的一些有关第一章的学习记录。

程序设计的基本元素

过程和它们所产生的计算

练习 1.19

题目

使用尾递归计算斐波那契数列的过程中,状态变量a和b有以下变换规则,a←a+b和b←a,现在将这种变换称为T变换。从1和0开始将T反复应用n次,将产出一对数Fib(n+1)和Fib(n)。

换句话说,斐波那契数可以通过将应用于对偶(1, 0)而产生出来。

现在将T看做是变换族中p=0且q=1的特殊情况,其中是对偶(a, b)按照a←bq+aq+ap和b←bp+aq规则的变换。请证明,如果我们应用变换两次,其效果等同于应用同样形式的一次变换,其中p'和q'可以由p和q计算出来。这就指明了一条求出这种变换的平方的路径。将所有的这些集中到一起,形成下面的过程,其运行只需要对数的步数:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
          (fib-iter a
                    b
                    <??>      ; compute p'
                    <??>      ; compute q'
                    (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b q) (* a q))
                        p
                        q
                        (- count 1)))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

解:

已知,这是, 的关系。所以要求出这种变换的平方的路径就是求出, , 的关系。

应用关系可得:

代入计算可得:

由于,所以:

所以答案为:

(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
          (fib-iter a
                    b
                    (+ (* q q) (* p p))      ; compute p'
                    (+ (* q q) (* 2 q p))    ; compute q'
                    (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b q) (* a q))
                        p
                        q
                        (- count 1)))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

用高阶函数做抽象

人们对功能强大的程序设计语言有一个必然要求,就是能为公共的模式命名,建立抽象,而后直接在抽象的层次上工作。

过程作为参数

3个例子

  • 计算从a到b的各整数之和:
(define (sum-integers a b)
  (if (> a b)
      0
      (+ a (sum-integers (+ a 1) b))))
1
2
3
4
  • 计算给定范围内的整数的立方和:
(define (cube x) (* x x x))
(define (sum-cubes a b)
  (if (> a b)
      0
      (+ (cube a) (sum-cubes (+ a 1) b))))
1
2
3
4
5
  • 计算序列之和:
(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))
1
2
3
4

可以看出,这三个过程共享着一种公共的基础模式,称为求和记法

求和记法

翻译成程序语言即是:

(define (sum term a next b)
  (if (> a b)
      0
      (+ (term a)
         (sum term (next a) next b))))
1
2
3
4
5

利用这个公共模式,上面三个例子可以改写为:

(define (inc n) (+ n 1))
; 计算从a到b的各整数之和
(define (identity x) x)
(define (sum-integers a b)
  (sum identity a inc b))
; 计算给定范围内的整数的立方和
(define (sum-cubes a b)
  (sum cube a inc b))
; 计算序列之和
(define (pi-sum a b)
  (define (pi-term x)
    (/ 1.0 (* a (+ a 2))))
  (define (pi-next x)
    (+ x 4))
  (sum pi-term a pi-next b))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

example

求函数在范围a和b之间的定积分的近似值,可以用下面的公式完成

描述为一个过程:

(define (integral f a b dx)
  (define (add-dx x) (+ x dx))
  (* (sum f (+ a (/ dx 2.0)) add-dx b)
     dx)
1
2
3
4

练习1.29

辛普森积分法

辛普森规则求定积分,公式为:

其中h=(b-a)/n,n是某个偶数,而。请定义出一个具有参数f、a、b和n,采用该规则计算并返回积分值的过程,求出cube在0和1之间的积分(用n=100和n=1000)

解:

观察公式,我们知道了求和部分为,当k为0或n时的常数为0,当k为奇数时,常数为4,k为偶数时常数则为2。

当我们尝试往过程(sum term a next b)中代入参数时,得到term=f、a=0、next=inc、b=n的结果。但实际上每一轮的(term a)返回值根据k而变化。

因此我们应当把分别看成一个内含f的整体,即定义一个过程simpson-term

(define (simpson-term k f a h n)
  (define y (f (+ a (* k h))))
  (if (or (= k 0) (= k n))
      y
      (if (even? k)
          (* 2 y)
          (* 4 y))))
1
2
3
4
5
6
7

现在我们有term=simson-term、a=0、next=inc、b=n,可得:

(define (simpson-integral f a b n)
  (define h (/ (- b a) n))
  (define (simpson-term k)
    (define y (f (+ a (* k h))))
    (if (or (= k 0) (= k n))
        y
        (if (even? k)
            (* 2 y)
            (* 4 y))))
  (* (/ h 3)
     (sum simpson-term 0 inc n)))
1
2
3
4
5
6
7
8
9
10
11

在线演示

辛普森积分法

有趣的是,上文解题过程中,将过程f包裹起来加上一层simpson-term外壳,进行额外处理然后返回的行为,就是所谓的装饰器模式Decorator Pattern)。


以下草稿,分析过程待补完...

1.30 将sum重写为线性迭代的过程

  • 什么是线性递归和线性递归(概念)?
  • 两者区别?
(define (sum term a next b)
	(define (iter a result)
		(if (> a b)
		  result
			(iter (next a) (+ result (term a)))))
	(iter a 0))
1
2
3
4
5
6

1.31 抽象出product过程用来定义factorial(阶乘)

; 线性迭代写法
(define (product term a next b)
  (define (iter a result)
    (if (> a b)
      result
      (iter (next a) (* result (term a)))))
  (iter a 1))
  
; 线性递归写法
(define (product term a next b)
  (if (> a b)
    1
    (* (term a)
       (product term (next a) next b))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

按照公式π计算π的近似值?

1.32 抽象出sum和product的公共模式accumulate

; 线性迭代写法
(define (accumulate combiner null-value term a next b)
	(define (iter a result)
		(if (> a b)
			result
			(iter (next a) (combiner result (term a)))))
	(iter a null-value))

; 线性递归写法
(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))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

练习1.33 引入过滤器概念,实现更一般版本的filter-accumulate抽象过程

提示:判断奇偶就是一种过滤过程


to be continued.