国产叼嘿久久精品久久,国产精品99久久免费观看,免费国产99久久久香蕉

我的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 閱讀(698) | 評論 (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 閱讀(925) | 評論 (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 閱讀(816) | 評論 (1) | 編輯收藏

數組類型、函數類型到左值和右值的轉換

摘要: 1、左值和右值

表達式的左值是它的地址，右值是該地址所存儲的內容。比如下面代碼：

x = x + 1;

這兩個 x 有什么不同呢？閱讀全文

posted @ 2008-04-07 22:50 cuigang 閱讀(4461) | 評論 (28) | 編輯收藏

我的SICP習題答案（1.34）

這個展開過程為：

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

解釋器將報錯，‘2’是一個未定義過程。

posted @ 2008-04-06 16:46 cuigang 閱讀(824) | 評論 (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 閱讀(944) | 評論 (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 閱讀(10389) | 評論 (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 閱讀(1546) | 評論 (2) | 編輯收藏

謹記于此

我們的世界是模糊的、連續的、不精確的，但軟件是精確、離散的、形式化的，這就注定了軟件不能完全描述現實世界。因此我們需要知道描述哪些部分，忽略哪些部分，這就是軟件的本質問題。
--- Tom Demarco

任何一個正在構建大型系統的人，天天面對的中心議題就是：如何剔除不必要的、人為的、自找的復雜部分，并控制好剩下的，無可逃避的復雜性。
--- Betrand Meyer

posted @ 2008-03-30 00:23 cuigang 閱讀(1627) | 評論 (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 閱讀(787) | 評論 (2) | 編輯收藏

CG@CPPBLOG

我的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

積分與排名

最新評論

閱讀排行榜

評論排行榜