《计算机程序的构造和解释(SICP)》学习笔记
计算机科学不是一门如何使用计算机的学科,它也不是科学，就好像几何学不是教你怎么使用工具进行测量的学科。
作为一门工程学科，它有很多和其他工程学科一样的一些要点：
- 抽象
Mit-Scheme的安装和使用
在使用Mit-Schme的时候，我对里面的7 error>感到奇怪，error前面的数字是什么呢？原来表示Scheme出错循环的层数。
第一章 构造过程抽象
- 计算过程是操作计算机里面的被称为数据的精灵的魔法，程序是操作这些精灵的规则模式；
- Lisp语言最早是一种数学计数形式，它的优点：能够将过程表示为数据。
程序设计的基本元素
-
程序语言应该是能够组织有关计算过程思想的框架。包含三种机制：
- 基本表达形式（精灵，基本的规则）
- 组合的方法
- 抽象的方法
-
表达式：基本数据和基本过程表达式
- 组合式，用括号包含表达式
-
命名： 计算对象的别名
(define size 2) -
环境：维持符号与特定的值的存储
-
组合式求值：是一个递归的过程，对于一个组合式，先求其左边的值，对于其左边的组合式，也是同样地规则，先求其左边的值。
-
复合过程：用别名代替过程
(define (square x) (* x x)) -
Lisp采用应用序求值，也就是先求出每个过程的值才得到结果，而不是先展开再求值
-
条件表达式，这个是求绝对值
(define (abs x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x)) ) ) -
牛顿表达式求平方根，求x的平方根的时候，先给出一个猜测值guess，比较猜测值guess的平方与x的差是否达到了精度，达到了就返回猜测值，否则，用改进值代替猜测值guess继续计算，改进的方法是取guess和(x/guess)的平均值
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x
)
)
)
(define (improve guess x)
(average guess (/ x guess)
)
)
(define (average x y)
(/ (+ x y)
2
)
)
(define (good-enough? guess x)
(< (abs (- (square guess) x))
0.001)
)
(define (sqrt x)
(sqrt-iter 1 x)
)
- 如同摄影师知道什么样的光圈会产生什么样的结果，能够看清所考虑的动作的后果，才是专家。
- 执行递归时需要存储的操作轨迹的长度会和n成正比的递归被称为线性递归。
- 斐波拉契数列的计算，根据其定义写出来的递归过程，这是一种树形递归，会有太多的冗余计算。
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2)))
)
)
)
-
线性迭代,类似于其他语言的循环，count是初始计数，max-count是终止条件需要满足的值，product是累计的结果值，此处是求n的阶乘。
(define (fact-iter product count max-count) (if (> count max-count) product (fact-iter (* product count) (+ count 1) max-count ) ) ) (define (factorial n) (fact-iter 1 1 n) )-
把上面的计算斐波拉契数列的树形递归换成线性迭代，效率更高，但是并没有那么直观。
(define (fib-iter a b n) (if (= n 0) b (fib-iter (+ a b) a (- n 1)) ) ) (define (fib n) (fib-iter 1 0 n) )
-
-
把1美元换成1，5，10，25，50美分这五种硬币，共有多少种兑换的方式？
1.先考虑一个缩小问题规模的方式，把1美元换成1，5，10，25，50美分硬币的方式等于把1美元换成除了50美分硬币以外的所有硬币（注意：此时，问题的规模缩小了，硬币种类数降低了）的方式数加上用了50美分硬币的所有方式数，这是简单地概率学问题。
2.用了50美分硬币的情况下，可以确定至少有一个50美分硬币，也就是说其情况数等于1美元减去50美分的硬币的总额换成所有5种硬币的方式数量，（注意：此时，问题的规模缩小了，总额降低了）
3.考虑退化情况，也就是问题规模不能够再缩小的情况
- 总额为0时，可以看做有1种方式
- 总额<0时，可以看做有0种方式
- 硬币种类数<0时，可以看做有0种方式
接下来可以写程序了，用(count-changes 100)即可求出结果
(define (count-changes amount)
(cc amount 5)
)
(define (cc amount kinds-of-coins)
(cond ( (or (< amount 0)
(= kinds-of-coins 0)
)
0
)
( (= amount 0)
1
)
(else (+ (cc amount (- kinds-of-coins 1))
(cc (- amount (amount-of-coins kinds-of-coins)) kinds-of-coins)
)
)
)
)
(define (amount-of-coins count)
(cond ((= count 1) 1)
((= count 2) 5)
((= count 3) 10)
((= count 4) 25)
((= count 5) 50)
)
)
- 描述问题的计算资源消耗随问题规模增加的变化的方式，用增长阶，Θ(n)表示线性增长，Θ(1)表示常数增长。下面看一个求幂的方法的增长阶：
- Θ(n)步和Θ(n)空间,线性递归
(define (exp x n)
(if (= 0 n)
1
(* x (exp x (- n 1)))
)
)
- Θ(n)步和Θ(1)空间,线性迭代
(define (exp-iter b counter product)
(if (= 0 counter)
product
(exp-iter b (- counter 1) (* b product))
)
)
(define (exp x n)
(exp-iter x n 1)
)
- Θ(log n)的步和空间，n为奇数时，计算的方法一样，x^n = x^(n-1) * x，n为偶数时，x^n = x^(n/2) * x^(n/2)
(define (fast-exp x n)
(cond ((= 0 n) 1)
((even? n)
(* (fast-exp x (/ n 2))
(fast-exp x (/ n 2))
)
)
(else (* x (fast-exp x (- n 1)))
)
)
)
