CG@CPPBLOG

我的SICP习题答案（2.01~2.08）

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)))))

posted @ 2008-06-10 22:01 cuigang 阅读(688) | 评论 (0) | 编辑收藏

我的SICP习题答案（1.40~1.44）

;;;;;;;;;;;
;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))

posted @ 2008-04-19 23:49 cuigang 阅读(914) | 评论 (6) | 编辑收藏

我的SICP习题答案（1.35~1.39）

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))

posted @ 2008-04-16 00:22 cuigang 阅读(807) | 评论 (1) | 编辑收藏

数组类型、函数类型到左值和右值的转换

摘要: 1、左值和右值

表达式的左值是它的地址，右值是该地址所存储的内容。比如下面代码：

x = x + 1;

这两个 x 有什么不同呢？阅读全文

posted @ 2008-04-07 22:50 cuigang 阅读(4439) | 评论 (28) | 编辑收藏

我的SICP习题答案（1.34）

这个展开过程为：

(f f)
(f 2)
(2 2)

解释器将报错，‘2’是一个未定义过程。

posted @ 2008-04-06 16:46 cuigang 阅读(815) | 评论 (0) | 编辑收藏

我的SICP习题答案（1.29~1.33）

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?))

posted @ 2008-04-06 16:12 cuigang 阅读(935) | 评论 (0) | 编辑收藏

对数组名取地址是什么？

摘要: 这两天有人问以下有什么代码有什么不同？

1 int array[100];
2
3 memset(array, 0, sizeof(array));
4 memset(&array, 0, sizeof(array)); 阅读全文

posted @ 2008-04-04 20:06 cuigang 阅读(10360) | 评论 (21) | 编辑收藏

我的SICP习题答案（1.24~1.28）

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

posted @ 2008-03-31 00:21 cuigang 阅读(1536) | 评论 (2) | 编辑收藏

谨记于此

我们的世界是模糊的、连续的、不精确的，但软件是精确、离散的、形式化的，这就注定了软件不能完全描述现实世界。因此我们需要知道描述哪些部分，忽略哪些部分，这就是软件的本质问题。
--- Tom Demarco

任何一个正在构建大型系统的人，天天面对的中心议题就是：如何剔除不必要的、人为的、自找的复杂部分，并控制好剩下的，无可逃避的复杂性。
--- Betrand Meyer

posted @ 2008-03-30 00:23 cuigang 阅读(1614) | 评论 (5) | 编辑收藏

我的SICP习题答案（1.21~1.23）

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。

posted @ 2008-03-28 23:44 cuigang 阅读(776) | 评论 (2) | 编辑收藏

我的SICP习题答案（2.01~2.08）

我的SICP习题答案（1.40~1.44）

我的SICP习题答案（1.35~1.39）

数组类型、函数类型到左值和右值的转换

我的SICP习题答案（1.34）

我的SICP习题答案（1.29~1.33）

对数组名取地址是什么？

我的SICP习题答案（1.24~1.28）

谨记于此

我的SICP习题答案（1.21~1.23）

导航

留言簿(5)

随笔分类(100)

随笔档案(76)

文章分类(38)

文章档案(39)

Others

SICP

Wiki

积分与排名

最新评论

阅读排行榜

评论排行榜