2008年9月12日
#
转眼就好几周过去了，整天无所事事的不知道干啥，语言是最大的障碍，学了十年的英文仍然跟白痴一般。
顿顿都吃着麦当劳、肯德基、必胜客类似的东西，搞得恶心透顶了，能吃碗面或者炒个菜就好了，不用整天跟牛一样啃生菜。
没有车在美国寸步难行，几乎没有公共交通工具，1个小时一班的bus坐满了黑人和墨西哥人，火车稍微好点，但我这地方太偏僻了，要走一个小时才到火车站。
去了纽约，大瀑布，不是很激动，比较沉默。
2008年8月15日
#
没地方抽烟，几乎所有的室内都 No smoking，大街上找不到垃圾桶，烟头不知道往哪扔。
美国人不睡午觉，我中午就犯困。
他们对棒球的兴趣看来比奥运会大。
上班不打卡，公司没有保安，人很少，地方很大，几乎每个人一个房间。
干什么都要付小费。
2008年8月13日
#
象折磨一般，填表填表、安检安检，断断续续持续了一个月，终于踏上了美利坚合众国的土地，16个小时的飞机比坐硬座痛苦多了，坐在酒店来接机的小车里，整个人象磕了药一样，恍恍惚惚的看着窗外的纽约，Big 是唯一的感受，车大、路宽、交通指示牌牌大字大，连到处悬挂的美国国旗都硕大无比，在国内从来没有见过如此尺寸的旗子。
用西北人的话来说，这里野哄哄的。
2008年7月2日
#
2.36
(define s (list (list 1 2 3)(list 4 5 6)(list 7 8 9)(list 10 11 12)))
(define (accumulate-n op init seqs)
(if (null? (car seqs)) null
(cons (accumulate op init (map# (lambda(x) (car x)) seqs))
(accumulate-n op init (map# (lambda(x) (cdr x)) seqs)))))
2.38
;> (fold-right / 1 (list 1 2 3))
;3/2
;> (fold-left / 1 (list 1 2 3))
;1/6
;> (fold-right list null (list 1 2 3))
;(1 (2 (3 ())))
;> (fold-left list null (list 1 2 3))
;(((() 1) 2) 3)
; (fold-right op i (a b c)) = (op a (op b (op c i)))
; (fold-left op i (a b c)) = (op (op (op i a) b) c)
要 fold-right 和 fold-left 得到相同的结果，显然需要 op 满足交换律。
2.39
(define (reverse-1 seqs)
(fold-right (lambda(x y) (append y (list x))) null seqs))
(define (reverse-2 seqs)
(fold-left (lambda(x y) (cons y x)) null seqs))
2008年6月24日
#
2.33
(define (map+ p seque)
(accumulate (lambda(x y) (cons (p x) y)) null seque))
(define (append seq1 seq2)
(accumulate cons seq2 seq1))
(define (length seque)
(accumulate (lambda(x y) (+ 1 y)) 0 seque))
2.34
(define (horner-eval x coeff-seque)
(accumulate (lambda(this-coeff higher-coeff)
(+ this-coeff (* x higher-coeff)))
0 coeff-seque))
2.35
(define (count-leaves+ t)
(accumulate + 0 (map (lambda(x)
(if (pair? x) (count-leaves+ x) 1))
t)))
2008年6月17日
#
2.27
(define (deep-reverse lst)
(define (iter lst-o lst-d)
(cond ((null? lst-o)
lst-d)
((not (pair? (car lst-o)))
(iter (cdr lst-o)
(cons (car lst-o) lst-d)))
(else
(iter (cdr lst-o)
(cons (deep-reverse (car lst-o))
lst-d)))))
(iter lst null))
2.28
(define (fringe x)
(define (iter tree lst)
(cond ((null? tree) lst)
((not (pair? tree)) (cons tree lst))
(else (iter (car tree) (iter (cdr tree) lst)))))
(iter x null))
2.30
(define (square-tree- x)
(cond ((null? x) null)
((not (pair? x)) (* x x))
(else (cons (square-tree- (car x))
(square-tree- (cdr x))))))
(define (square-tree x)
(map (lambda(subtree)
(if (pair? subtree)
(square-tree subtree)
(* subtree subtree)))
x))
2.31
(define (tree-map proc tree)
(map (lambda(subtree)
(if (pair? subtree)
(tree-map proc subtree)
(proc subtree)))
tree))
(define (square-tree+ tree)
(tree-map (lambda(x) (* x x)) tree))
2.32
(define (subsets s)
(if (null? s)
(list null)
(let ((rest (subsets (cdr s))))
(append rest (map (lambda(x) (cons (car s) x)) rest)))))
和换零钱问题的思路是一样的，对于一个集合的所有子集的集合，可以分为两部分，含有第一个元素和不含第一个元素的集合。而且含第一个元素的所有子集除去第一个元素，恰好正是所有不含第一个元素的子集。
也可以换个思路，对于集合A，设它可以表示为 (a1)∪(a2,...,an) ，而 (a2,...,an) 的所有子集的集合是 B=(B1,...Bm),那么可以证明A的所有子集的集合 C=B∪((A1)∪B1,(A1)∪B2,...,(A1)∪Bm);
证明：设 X 是 A 的一个子集，那么如果 a1∈X，那么 X∈((A1)∪B1,(A1)∪B2,...,(A1)∪Bm)，否则X∈B，所以
X∈C
2008年6月11日
#
2.24
2.25
(car (cdaddr (list 1 3 (list 5 7) 9)))
(caar (list (list 7)))
(cadadr (cadadr(cadadr (list 1 (list 2 (list 3 (list 4 (list 5 (list 6 7)))))))))
2.26
(1 2 3 4 5 6)
((1 2 3) 4 5 6)
((1 2 3) (4 5 6))
2.17
(define (last-pair lst)
(if (null? (cdr lst))
(cons (car lst) ())
(last-pair (cdr lst))))
2.18
(define (reverse lst)
(define (iter lst-o lst-d)
(if (null? lst-o)
lst-d
(iter (cdr lst-o) (cons (car lst-o) lst-d))))
(iter lst null))
2.20
(define (same-parity x . lst)
(define (filter lst ok?)
(if (null? lst)
()
(if (ok? (car lst))
(cons (car lst) (filter (cdr lst) ok?))
(filter (cdr lst) ok?))))
(if (even? x)
(cons x (filter lst (lambda(x) (= 0 (remainder x 2)))))
(cons x (filter lst (lambda(x) (= 1 (remainder x 2)))))))
2.21
(define (square-list- items)
(if (null? items)
()
(cons (* (car items) (car items))
(square-list- (cdr items)))))
(define (square-list items)
(map (lambda(x) (* x x)) items))
2.22
第一种每次取出首元素平方后前插到新表，象reverse过程类似，所以是反的。
第二种只不过是把新表前插到元素前，得到的甚至不是一个list，而是
((((() . 1) . 4) . 9) . 16)
2.23
(define (for-each proc items)
(if (not (null? items))
((lambda() (proc (car items))
(for-each proc (cdr items))))))
2008年6月10日
#
2.01
(define (make-rat x y)
(let ((g (gcd x y)))
(if (< y 0)
(cons (/ (- x) g) (/ (- y) g))
(cons (/ x g) (/ y g)))))
2.02
(define (make-point x y) (cons x y))
(define (x-point p) (car p))
(define (y-point p) (cdr p))
(define (make-segment p1 p2) (cons p1 p2))
(define (start-seg line) (car line))
(define (end-seg line) (cdr line))
(define (midpoint-segment line)
(make-point (/ (+ (x-point (start-seg line)) (x-point (end-seg line))) 2.0)
(/ (+ (y-point (start-seg line)) (y-point (end-seg line))) 2.0)))
2.04
;;;;;;;;;;;;;;;;;;;;;;;;;
; (cdr+ (cons+ x y) = ((cons+ x y) (lambda(p q) p)))
; = (lambda(m)(m x y) (lambda(p q) p)))
; = ((lambda(p q) p) x y)
; = x
(define (cons+ x y)
(lambda(m) (m x y)))
(define (car+ z)
(z (lambda(p q) p)))
(define (cdr+ z)
(z (lambda(p q) q)))
2.05
2^a * 3^b = 2^c * 3^d (a!=c && b!=d)
2^a/2^c = 3^d/3^b
2^(a-c) = 3^(d-b)
a=c && d=b
2.06
(define one (lambda(f) (lambda(x) (f x))))
(define two (lambda(f) (lambda(x) (f (f x)))))
2.07
(define (upper-bound pair)
(if (> (car pair) (cdr pair))
(car pair)
(cdr pair)))
(define (lower-bound pair)
(if (> (car pair) (cdr pair))
(cdr pair)
(car pair)))
2.08
(define (sub-interval x y)
(add-interval x (make-interval (- (upper-bound y))
(- (lower-bound y)))))
2008年4月19日
#
;;;;;;;;;;;
;1.43
(define (double f)
(lambda(x) (f (f x))))
;;(((double (double double)) inc) 5) = 5+16 =21
;;;;;;;;;;;;;
;1.42
(define (compose f g)
(lambda(x) (f (g x))))
;;;;;;;;;;;;;;;
;1.43
(define (repeated f n)
(if(= n 1) f
(compose f (repeated f (- n 1)))))
;;;;;;;;;;;;;;;;
;1.44
(define (smooth f)
(lambda(x) (/ (+ (f (- x dx))
(f x)
(f (+ x dx)))
3)))
(define (smooth-n f)
(repeated f n))
(define (smooth-n f n)
((repeated smooth n) f))
2008年4月16日
#
1.35
若 φ=0 ， 则 φ^2=φ+1 不成立 ， 故 φ≠0
φ^2 = φ+1 ==>
φ = (φ+1)/φ = 1 + (1/φ)
(fixed-point (lambda(x) (+ 1 (/ 1 x))) 1.0)
1.36
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? x y)
(< (abs (- x y)) tolerance))
(define (try guess)
(let ((next (f guess)))
(display next)
(newline)
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
平均阻尼法和不用平均阻尼分别如下，它们步数分别为 9 和 34 。
(fixed-point (lambda(x) (/ (+ x (/ (log 1000) (log x))) 2)) 2.0)
(fixed-point (lambda(x) (/ (log 1000) (log x))) 2.0)
1.37
(define (cont-frac-r n d k)
(define (redu i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (redu n d (+ i 1))))))
(redu 1))
(define (cont-frac n d k)
(define (iter i result)
(if (= i 0)
result
(iter (- i 1) (/ (n i) (+ (d i) result)))))
(iter k 0))
(define (get-phai k)
(/ 1 (cont-frac (lambda(i) 1.0) (lambda(i) 1.0) k)))
(define (get-k)
(define (iter i)
(if (< (abs (- (get-phai i) 1.6180)) 0.00005)
i
(iter (+ i 1))))
(iter 1))
k = 11 时，精度满足 4 位 十进制数。
1.38
(define (euler-d i)
(cond ((= i 2) 2.0)
((and (> i 2) (= 0 (remainder (- i 2) 3)))
(* (/ (+ i 1) 3.0) 2.0))
(else 1.0)))
(define (get-e k)
(+ 2 (cont-frac (lambda(i) 1.0) euler-d k)))
1.39
(define (tan-cf x k)
(define (tan-n i)
(if (= 1 i)
x
(- (* x x))))
(cont-frac tan-n (lambda(i) (- (* i 2.0) 1.0)) k))
2008年4月7日
#
摘要: 1、左值和右值
表达式的左值是它的地址，右值是该地址所存储的内容。比如下面代码：
x = x + 1;
这两个 x 有什么不同呢？
阅读全文
2008年4月6日
#
这个展开过程为：
(f f)
(f 2)
(2 2)
解释器将报错，‘2’是一个未定义过程。
1.29
(define (simpson f a b n)
(define (get-h) (/ (- b a) n))
(define (get-y k) (f (+ a (* k (get-h)))))
(define (simpson-term k)
(cond ((= k 0) (get-y k))
((= k n) (get-y k))
((= (remainder k 2) 0) (* 2.0 (get-y k)))
(else (* 4.0 (get-y k)))))
(define (simpson-next k) (+ k 1))
(* (/ (get-h) 3.0) (sum simpson-term 0 simpson-next n)))
1.30
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
1.31
;;递归
(define (product-re term a next b)
(if (> a b)
1
(* (term a)
(product-re term (next a) next b))))
;;迭代
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* result (term a)))))
(iter a 1))
(define (pi-product b)
(define (pi-term k) (/ (* (- k 1) (+ k 1)) k k))
(define (pi-next k) (+ k 2))
;;(* 4.0 (product-re pi-term 3.0 pi-next b))) ;;递归
(* 4.0 (product pi-term 3.0 pi-next b))) ;;迭代
1.32
(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 (accumulate-re combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a)
(accumulate-re combiner null-value term (next a) next b))))
;;迭代
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
1.33
(define (filtered-accumulate combiner null-value term a next b filter?)
(define (iter a result)
(if (> a b)
result
(if (filter? (term a))
(iter (next a) (combiner (term a) result))
(iter (next a) result))))
(iter a null-value))
(define (sum-prime a b)
(define (sum-prime-term k) k)
(define (sum-prime-next k) (+ k 1))
(filtered-accumulate + 0 sum-prime-term a sum-prime-next b prime?))
(define (relatively-prime-product n)
(define (relatively-prime? k) (= (gcd k n) 1))
(define (term k) k)
(define (next k) (+ k 1))
(filtered-accumulate * 1 term 2 next (- n 1) relatively-prime?))
2008年4月4日
#
摘要: 这两天有人问以下有什么代码有什么不同？
1 int array[100];
2
3 memset(array, 0, sizeof(array));
4 memset(&array, 0, sizeof(array));
阅读全文
2008年3月31日
#
1.24
对于Fermat检查，因为具有log n 的增长阶，所以对于 n^2 和 n 的检查的时间比 理论上应该是 2：1， 实际上，经过测试也比较接近，当n比较大时。
若与预计不符，可能因为 n 比较小，或者字长发生变化，比如 n > 2^32 （参见下题）
1.25
仅从理论分析，Alyssa 的改动不会引起增长阶的变化，但实际上当 Fermat 检查的 n 稍微大一点，速度就会很慢。主要原因 就是 base^exp 是一个非常大的数，可能远远超过 一个32位机字的表示范围 2^32 ，在 scheme 里可能用若干个 32-bit 靠软件实现运算，这将导致计算急速增长。无论是传递、运算还是求模。
实际上 1.22、1.23、1.24 的几个题目可能都会遇到字长变化引起的计算速度突变。
1.26
Fermat 检查正是因为 连续求平方的求幂方法，使得的增长阶变为 log n， 而这均来源于 b^(2n) = (b^n)^2，Louis 的方法让求幂又变成了连乘，b^(2n) = b^n*b^n = (b*b*...*b)*(b*b*...*b)，求幂的增长阶变成了 O(n)，Fermat 检查的增长阶自然也变成了 O(n)。
1.27
(define (fermat-test n)
(fermat-iter (- n 1) n))
(define (fermat-iter a n)
(cond ((= a 0) #t)
((= (expmod a n n) a) (fermat-iter (- a 1) n))
(else #f)))
1.28
首先来看，Fermat 小定理的一个变形：
p 是素数, 1<a<p, 有 a^p % p = a
==> a^p = kp + a ==> a^p - a = kp ==> a(a^(p-1)-1) = kp ==> a^(p-1) -1 = k'p
==> a^(p-1) % p = 1
这个变形就是题目中提到的，这个形式和费马小定理是等价的（但是奇怪的是，我没有发现已知的几个Carmichael数能够躲过这个变形的检查，有待研究①）
再来看，miller-rabin 素性测试的原理：
p 是素数， 1<a<p, 且 a^2 % p = 1
==> (a^2-1) % p = 0 ==> (a+1)(a-1) % p =0
那么 a+1 % p = 0 或者 a-1 % p =0,
又 a<p 且 p 是素数，所以
a = 1 或者 a = p-1 （这两个叫做 1模n的平凡平方根）
代码如下：
(define (check-nontrivial-sqrt-of-one a n)
(define (check-1? t)
(if (and (> a 1)
(< a (- n 1))
(= t 1))
0 t))
(check-1? (remainder (square a) n)))
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
;(remainder (square (expmod base (/ exp 2) m)) m))
(check-nontrivial-sqrt-of-one (expmod base (/ exp 2) m) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))
(define (miller-rabin-test n)
(define (iter x n)
(cond ((= x 0) #t)
((= (expmod x (- n 1) n) 1) (iter (- x 1) n))
(else #f)))
(iter (- n 1) n))
① 对于 Carmichael 数 n ，实际上不能完全通过 a^(n-1)%n = 1 的检查，除非 a 与 n 互素，当 a 为 n 的素因子时，不能通过，比如 Carmichael 第一个 561 = 3*11*17， 而 3^560%561 = 375 ≠ 1 。可以程序验证这个。 所以我认为，a^(n-1)%n = 1 的检查比 a^n%n = a 的检查更严格，是不是不存在合数通过完全的 a^(n-1)%n = 1 的检查呢？我不敢说。但把这个结论暂时记在这里，希望能得到帮助或者反驳。2008-04-02 23:56
2008年3月30日
#
我们的世界是模糊的、连续的、不精确的，但软件是精确、离散的、形式化的，这就注定了软件不能完全描述现实世界。因此我们需要知道描述哪些部分，忽略哪些部分，这就是软件的本质问题。
--- Tom Demarco
任何一个正在构建大型系统的人，天天面对的中心议题就是：如何剔除不必要的、人为的、自找的复杂部分，并控制好剩下的，无可逃避的复杂性。
--- Betrand Meyer
2008年3月28日
#
1.21
> (smallest-divisor 199)
199
> (smallest-divisor 1999)
1999
> (smallest-divisor 19999)
7
>
1.22
在 DrScheme 中没有对应的 runtime 过程，我们用内建的 current-milliseconds
来代替，这个过程返回的是系统的 ms 数。
同时，在 Windows 下无法精确表示 16ms 以下的精度（可能时间片的大小是 16ms ），所以这里用比较大的数来测试。
代码如下
(define (even? x) (= (remainder x 2) 0))
(define (runtime) (current-milliseconds))
(define (start-prime-test n start-time)
(and (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
(define (search-iter cur-num index start-time)
(newline)
(display cur-num)
(if (not (= index 0))
(if (start-prime-test cur-num start-time)
(search-iter (+ cur-num 2) (- index 1) start-time)
(search-iter (+ cur-num 2) index start-time))))
(define (search-for-primes start-number)
(if (even? start-number)
(search-iter (+ start-number 1) 3 (runtime))
(search-iter start-number 3 (runtime))))
这里用到了 prime? 谓词，代码不再复述。
|------+--------+--------+-------|
|10^9 | 10^10 | 10^11 | 10^12 | => start-number
|------+--------+--------+-------|
|31 | 250 | 609 | 1953 | (ms)
|47 | 406 | 1203 | 3844 |
|78 | 625 | 1859 | 5719 |
|------+--------+--------+-------|
从上表可以看出，除了前两列之间，后列的数字都是前列数字的 3 倍左右，近似于 √10 ≈ 3.16。实际上，随着 n 的不断增大，这个数会逐渐逼近 √10。
1.23
(define (next n)
(if (= n 2) 3 (+ n 2)))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
计算结果如下：
|--------+--------+-------|
| 10^10 | 10^11 | 10^12 | => start-number
|--------+--------+-------|
| 141 | 297 | 1078 | (ms)
| 219 | 609 | 2093 |
| 313 | 984 | 3140 |
|--------+--------+-------|
可以看出这个比值大约在 1.8(1/0.55) 左右，可能原因是其它的计算需要时间，但当 n 不断增大，其它计算是常数阶，这个比值会不断接近2。
2008年3月27日
#
1.20
下面用 % 表示过程 remainder，那么正则序的过程如下：
(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40)))
(gcd 40 (% 206 40))
(if (= (% 206 40) 0) ;<## 1> [6]
40
(gcd (% 206 40) (% 40 (% 206 40))
(gcd (% 206 40) (% 40 (% 206 40)))
(if (= (% 40 (% 206 40)) 0) ;<## 2> [4]
(%