計算機科學不是一門如何使用計算機的學科,它也不是科學斗塘，就好像幾何學不是教你怎么使用工具進行測量的學科胀屿。
作為一門工程學科帕胆，它有很多和其他工程學科一樣的一些要點：
- 抽象
Mit-Scheme的安裝和使用
在使用Mit-Schme的時候轴捎，我對里面的7 error>感到奇怪召耘，error前面的數(shù)字是什么呢百炬？原來表示Scheme出錯循環(huán)的層數(shù)。
第一章 構造過程抽象
- 計算過程是操作計算機里面的被稱為數(shù)據(jù)的精靈的魔法污它，程序是操作這些精靈的規(guī)則模式剖踊；
- Lisp語言最早是一種數(shù)學計數(shù)形式庶弃，它的優(yōu)點：能夠?qū)⑦^程表示為數(shù)據(jù)。
程序設計的基本元素
-
程序語言應該是能夠組織有關計算過程思想的框架德澈。包含三種機制：
- 基本表達形式（精靈歇攻，基本的規(guī)則）
- 組合的方法
- 抽象的方法
-
表達式：基本數(shù)據(jù)和基本過程表達式
- 組合式，用括號包含表達式
命名： 計算對象的別名
(define size 2)環(huán)境：維持符號與特定的值的存儲
組合式求值：是一個遞歸的過程梆造，對于一個組合式缴守，先求其左邊的值，對于其左邊的組合式澳窑，也是同樣地規(guī)則斧散，先求其左邊的值。
復合過程：用別名代替過程
(define (square x) (* x x))Lisp采用應用序求值摊聋，也就是先求出每個過程的值才得到結果，而不是先展開再求值
-
條件表達式栈暇，這個是求絕對值
(define (abs x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x)) ) ) 牛頓表達式求平方根麻裁，求x的平方根的時候，先給出一個猜測值guess源祈，比較猜測值guess的平方與x的差是否達到了精度煎源，達到了就返回猜測值，否則香缺，用改進值代替猜測值guess繼續(xù)計算手销，改進的方法是取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)
)
- 如同攝影師知道什么樣的光圈會產(chǎn)生什么樣的結果，能夠看清所考慮的動作的后果图张，才是專家锋拖。
- 執(zhí)行遞歸時需要存儲的操作軌跡的長度會和n成正比的遞歸被稱為線性遞歸。
- 斐波拉契數(shù)列的計算祸轮，根據(jù)其定義寫出來的遞歸過程兽埃，這是一種樹形遞歸，會有太多的冗余計算适袜。
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2)))
)
)
)
-
線性迭代,類似于其他語言的循環(huán)柄错，count是初始計數(shù)，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) )-
把上面的計算斐波拉契數(shù)列的樹形遞歸換成線性迭代疫萤，效率更高颂跨，但是并沒有那么直觀。
(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.先考慮一個縮小問題規(guī)模的方式，把1美元換成1斑粱，5弃揽，10，25则北，50美分硬幣的方式等于把1美元換成除了50美分硬幣以外的所有硬幣（注意：此時矿微，問題的規(guī)模縮小了尚揣，硬幣種類數(shù)降低了）的方式數(shù)加上用了50美分硬幣的所有方式數(shù)涌矢，這是簡單地概率學問題。
2.用了50美分硬幣的情況下快骗，可以確定至少有一個50美分硬幣娜庇，也就是說其情況數(shù)等于1美元減去50美分的硬幣的總額換成所有5種硬幣的方式數(shù)量，（注意：此時方篮，問題的規(guī)拿悖縮小了，總額降低了）
3.考慮退化情況藕溅，也就是問題規(guī)模不能夠再縮小的情況
- 總額為0時匕得，可以看做有1種方式
- 總額<0時，可以看做有0種方式
- 硬幣種類數(shù)<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)
)
)
- 描述問題的計算資源消耗隨問題規(guī)模增加的變化的方式，用增長階攒发，Θ(n)表示線性增長调塌，Θ(1)表示常數(shù)增長。下面看一個求冪的方法的增長階：
- Θ(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為奇數(shù)時羔砾，計算的方法一樣，x^n = x^(n-1) * x偶妖，n為偶數(shù)時姜凄，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)))
)
)
)
