SICP第一章习题

习题1.3

摘自http://sicp.readthedocs.io/en/latest/chp1/3.html

1
2
3
4
5
6
7
8
9
10
11
12
13
求3个数a,b,c之中两个较大数平方之和,其实只有三种情况:a最小,b最小和c最小。程序如下:
(define (sum_sq_bigger2 a b c)
(cond ((and (>= a c) (>= b c))
(+ (* a a) (* b b))
)
((and (>= a b) (>= c b))
(+ (* a a) (* c c))
)
(else
(+ (* b b) (* c c))
)
)
)

习题1.4

Note 在一些语言中, + 和 - 都是具有特殊作用的运算符(operator),但是在 scheme (和许多其他函数式语言)中,它们只是函数。

习题1.5

摘自1.5解答
首先,可以确定的是,无论解释器使用的是什么求值方式,调用 (p) 总是进入一个无限循环(infinite loop),因为函数 p 会不断调用自身:

1
(define (p) (p))

具体到解释器中,执行 (p) 调用会让解释器陷入停滞,最后只能强制将解释器进程杀掉:

1
2
3
4
1 ]=> (p)
^Z
[1]+ 已停止 mit-scheme
$ killall mit-scheme

在应用序中,所有被传入的实际参数都会立即被求值,因此,在使用应用序的解释器里执行 (test 0 (p)) 时,实际参数 0 和 (p) 都会被求值,而对 (p) 的求值将使解释器进入无限循环,因此,如果一个解释器在运行 Ben 的测试时陷入停滞,那么这个解释器使用的是应用序求值模式。

另一方面,在正则序中,传入的实际参数只有在有需要时才会被求值,因此,在使用正则序的解释器里运行 (test 0 (p)) 时, 0 和 (p) 都不会立即被求值,当解释进行到 if 语句时,形式参数 x 的实际参数(也即是 0)会被求值(求值结果也是为 0 ),然后和另一个 0 进行对比((= x 0)),因为对比的值为真(#t),所以 if 返回 0 作为值表达式的值,而这个值又作为 test 函数的值被返回。

因为在正则序求值中,调用 (p) 从始到终都没有被执行,所以也就不会产生无限循环,因此,如果一个解释器在运行 Ben 的测试时顺利返回 0 ,那么这个解释器使用的是正则序求值模式。

Note 另一个需要说明的地方是『形式参数』和『实际参数』两个名词。
对于一个函数来说,它接受的参数的局部名被称为形式参数。
而调用函数时传入的表达式,被称为实际参数。

比如说,对于函数 (define (square x) (* x x)) 来说, x 就是形式参数,当进行调用 (square 2) 时, 2 就是形式参数 x 的实际参数。
当人们只说『参数』而不说明它是『形式参数』还是『实际参数』时,他们一般指的是『形式参数』,但是具体还是要看上下文来决定。

习题1.6

摘自习题1.6

至于造成 sqrt-iter 函数出错的原因,毫无疑问就是新定义的 new-if 了。

根据书本 12 页所说, if 语句是一种特殊形式,当它的 predicate 部分为真时, then-clause 分支会被求值,否则的话, else-clause 分支被求值,两个 clause 只有一个会被求值。

而另一方面,新定义的 new-if 只是一个普通函数,它没有 if 所具有的特殊形式,根据解释器所使用的应用序求值规则,每个函数的实际参数在传入的时候都会被求值,因此,当使用 new-if 函数时,无论 predicate 是真还是假, then-clause 和 else-clause 两个分支都会被求值。

可以用一个很简单的实验验证 if 和 new-if 之间的差别,如果使用 if 的话,那么以下的代码只会打印 good :

1
2
3
1 ]=> (if #t (display "good") (display "bad"))
good
;Unspecified return value

如果使用 new-if 的话,那么两个语句都会被打印:

1
2
3
1 ]=> (new-if #t (display "good") (display "bad"))
badgood
;Unspecified return value

总结:还是应用序与正则序的问题。

习题1.7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1 ]=> (load "p16-sqrt.scm")

;Loading "p16-sqrt.scm"...
; Loading "p15-sqrt-iter.scm"...
; Loading "p15-good-enough.scm"... done
; Loading "p15-improve.scm"...
; Loading "p15-average.scm"... done
; ... done
; ... done
;... done
;Value: sqrt

1 ]=> (sqrt 0.00009) ; 正确答案应该是 9.486832980505138e-3
;Value: .03220324381282134


1 ]=> (sqrt 900000000000000000000000000000000000000000
000000000000000000000000000000000000000000) ; 死循环
^C

可以发现,对于特别小的数,比如 0.00009 ,书本给出的 sqrt 并不能计算出正确的答案; 而对于特别大的数,因为 mit-scheme 实现的小数精度不足以表示两个大数之间的差,所以 sqrt 会陷入死循环而无法得出正确结果。

要避免这一错误,我们按照练习所说,对 good-enough? 进行修改:不再检测猜测值 guess 的平方与 x 之间的差,而是检测新旧两次猜测值之间的比率,当比率变化非常小时,程序就停止 improve 。

新的函数定义如下:

1
2
3
4
5
6
;;; 7-good-enough.scm

(define (good-enough? old-guess new-guess)
(> 0.01
(/ (abs (- new-guess old-guess))
old-guess)))

1
2
3
4
5
(define (sqrt-iter guess x)
(if (good-enough? guess (improve guess x)) ; 调用新的 good-enough?
(improve guess x)
(sqrt-iter (improve guess x)
x)))

acfasj • 1年前
“而对于特别大的数,因为 mit-scheme 实现的小数精度不足以表示两个大数之间的差,所以 sqrt 会陷入死循环而无法得出正确结果”,这句话不是很理解,有哪位可以帮忙解释一下吗?

答: 因为表达数字的位数是一定的,如果整数部分比较大的话,小数部分所能表达的位数就很有限了。很关键

1.2笔记:

代换模型揭示出一种先逐步展开而后收缩的形状,在展开阶段里,这一计算过程构造起一个推迟进行的操作而形成的链条,收缩阶段表现为这些运算的实际执行。这种类型的计算过程由一个推迟执行的运算链条刻画,称为一个 递归计算过程。在计算阶乘n!时,推迟执行的乘法链条的长度也就是为保存其轨迹需要保存的信息量,这个长度随着n值增长而线性增长,这样的计算过程称为一个 线性递归过程

与之相对应,第二个计算过程里没有任何增长或收缩,在计算过程中的每一步,在我们需要保存的轨迹里,所有的东西就是变量product,counter,和max-count的当前值,我们称这种过程为一个 迭代计算过程 。一般来说,迭代计算过程就是那种 其状态可以用固定数目的状态变量描述的计算过程;而与此同时,又存在着一套固定的规则,描述了计算过程在从下一个状态到下一个状态转换时,这些变量的更新方式。另外,还有一个(可能有的)结束检测,它描述这一计算过程应该终止的条件。这种过程称为 线性迭代过程

习题1.10: 此题存疑!!!

Exercise 1.10. The following procedure computes a mathematical function called Ackermann’s function.

(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n2.

实例:换零钱

给定任意数量的现金,我们能写出一个程序,计算出所有换零钱方式的种数吗?

将总数为a的现金换成n种硬币的不同方式的数目等于

  • 将现金数a换成除第一种硬币之外的所有其他应比的不同方式数目,
  • 将现金数a-d换成所有种类的硬币的不同方式数目,其中的d是第一种硬币的币值。

为什么这个说法是对的?
第一组里没有使用第一种硬币,而第二组李使用了第一种硬币。
显然,换成零钱的全部方式的数目,就等于完全不用第一种硬币的方式的数目,加上用了第一种硬币的换零钱方式的数目。而后一个数目也就等于去掉一个第一种硬币值后,剩下的现金数的换零钱方式数目。

规约算法

  • 如果a就是0,应该算作是有1种换零钱的方式。
  • 如果a小于0,应该算作是有0种换零钱的方式。
  • 如果n是0, 应该算作是有0种换零钱的方式。