C++博客-(define (cuigang) (coding))

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

cuigang — Sat, 19 Apr 2008 15:49:00 GMT

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

cuigang 2008-04-19 23:49 发表评论

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

cuigang — Tue, 15 Apr 2008 16:22:00 GMT

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

cuigang 2008-04-16 00:22 发表评论

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

cuigang — Mon, 07 Apr 2008 14:50:00 GMT

摘要: 1、左值和右值

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

x = x + 1;

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

cuigang 2008-04-07 22:50 发表评论

我的SICP习题答案（1.34）

cuigang — Sun, 06 Apr 2008 08:46:00 GMT

这个展开过程为：

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

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

cuigang 2008-04-06 16:46 发表评论

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

cuigang — Sun, 06 Apr 2008 08:12:00 GMT

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

cuigang 2008-04-06 16:12 发表评论

对数组名取地址是什么？

cuigang — Fri, 04 Apr 2008 12:06:00 GMT

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

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

cuigang 2008-04-04 20:06 发表评论

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

cuigang — Sun, 30 Mar 2008 16:21:00 GMT

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 = 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^2-1) % p = 0 ==> (a+1)(a-1) % p =0
那么 a+1 % p = 0 或者 a-1 % p =0,
又 a

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

cuigang 2008-03-31 00:21 发表评论

谨记于此

cuigang — Sat, 29 Mar 2008 16:23:00 GMT

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

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

cuigang 2008-03-30 00:23 发表评论

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

cuigang — Fri, 28 Mar 2008 15:44:00 GMT

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。

cuigang 2008-03-28 23:44 发表评论

我的SICP习题答案（1.20）

cuigang — Thu, 27 Mar 2008 13:59:00 GMT

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]
     (% 206 40)
     (gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40)))))
(gcd (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))
(if (= (% (% 206 40) (% 40 (% 206 40))) 0) ;<## 4>[2]
     (% 40 (% 206 40))
     (gcd (% (% 206 40) (% 40 (% 206 40)))
          (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
(gcd (% (% 206 40) (% 40 (% 206 40)))
      (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))))
(if (= (% (% 40 (% 206 40)) (% (% 206 40) (% 40 (% 206 40))))) 0) ;<## 7>[0]
     (% (% 206 40) (% 40 (% 206 40)))
     (gcd ...)
(% (% 206 40) (% 40 (% 206 40)))  ;<## 4>[2]

可以看出需要调用 remainder 共 1+2+4+7+4 = 18 次。

应用序计算过程如下：

(gcd 206 40)
(if (= 40 0) 206 (gcd 40 (% 206 40))) ;<##>
(gcd 40 6)
(if (= 6 0) 40 (gcd 6 (% 40 6)))      ;<##>
(gcd 6 4)
(if (= 4 0) 6 (gcd 4 (% 6 4)))        ;<##>
(gcd 4 2)
(if (= 2 0) 4 (gcd 2 (% 4 2)))        ;<##>
(gcd 2 0)
(if (= 0 0) 2 (gcd 0 (% 2 0)))
2

可以看出共需 4 次。

cuigang 2008-03-27 21:59 发表评论