CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

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

(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 
13 (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 23 (+ 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 on 2008-03-28 23:44 cuigang 阅读(776) 评论(2)  编辑 收藏 引用 所属分类: Lisp/Scheme我的SICP答案

评论

# re: 我的SICP习题答案(1.21~1.23)  回复  更多评论   

(current-milliseconds)这个貌似在解释器里定义的
2010-05-11 20:04 | luthur

# re: 我的SICP习题答案(1.21~1.23)  回复  更多评论   

说错了,这个没有在解释器里定义,我用不了
2010-05-11 20:25 | luthur

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理