|
|
sicp习题试解 (1.22) |
|
|
作者:未知 来源:月光软件站 加入时间:2005-5-13 月光软件站 |
; ====================================================================== ; ; Structure and Interpretation of Computer Programs ; (trial answer to excercises) ; ; 计算机程序的构造和解释(习题试解) ; ; created: code17 02/28/05 ; modified: ; (保持内容完整不变前提下,可以任意转载) ; ======================================================================
;; SICP No.1.22
;; 在PLT Scheme中,测当前时间的函数使用current-inexact-millseconds,需要将 ;; 原代码中对应的current-time替换
;; 因为需要控制寻找质数的数目,我们必须知道timed-prime-test是否成功,而在 ;; 原来的函数定义中并没有将是否成功的信息作为结果返回。因此如果我们需要使用 ;; timed-prime-test,我们需要原定义做一处的修改,如下 (define (timed-prime-test n) (newline) (display n) (start-prime-test n (current-inexact-milliseconds)))
(define (start-prime-test n start-time) (if (prime? n) (report-prime (- (current-inexact-milliseconds) start-time)) #f)) ;; 这是唯一需要改的地方!
(define (report-prime elapsed-time) (display " *** ") (display elapsed-time))
;; 主函数search-for-primes可简单定义为 (define (search-for-primes from n) (cond ((= n 0) (newline) (display "finish") (newline)) ((even? from) (search-for-primes (+ from 1) n)) ((timed-prime-test from) (search-for-primes (+ from 2) (- n 1))) (else (search-for-primes (+ from 2) n))))
;; Test-it:: ;; ;; 从运行时间测试可以看出,函数(prime? n)的时间复杂度确实近似地符合 ;; [theta]([sqrt](n))的规律: ;; 其中n=1000左右的运行时间为0.039ms左右 ;; n=10000左右的运行时间为0.115左右 ;; n=100000左右的运行时间为0.363左右 ;; t(10n) = [sqrt](10)t(n) = 3.1622776601683795 ;; ;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc. ;; > (search-for-primes 1000 3) ;; ;; 1001 ;; 1003 ;; 1005 ;; 1007 ;; 1009 *** 0.0390625 ;; 1011 ;; 1013 *** 0.039794921875 ;; 1015 ;; 1017 ;; 1019 *** 0.0390625 ;; finish ;; ;; > (search-for-primes 10000 3) ;; ;; 10001 ;; 10003 ;; 10005 ;; 10007 *** 0.117919921875 ;; 10009 *** 0.114990234375 ;; 10011 ;; 10013 ;; 10015 ;; 10017 ;; 10019 ;; 10021 ;; 10023 ;; 10025 ;; 10027 ;; 10029 ;; 10031 ;; 10033 ;; 10035 ;; 10037 *** 0.116943359375 ;; finish ;; ;; > (search-for-primes 100000 3) ;; ;; 100001 ;; 100003 *** 0.36376953125 ;; 100005 ;; 100007 ;; 100009 ;; 100011 ;; 100013 ;; 100015 ;; 100017 ;; 100019 *** 0.362060546875 ;; 100021 ;; 100023 ;; 100025 ;; 100027 ;; 100029 ;; 100031 ;; 100033 ;; 100035 ;; 100037 ;; 100039 ;; 100041 ;; 100043 *** 0.364990234375 ;; finish ;; > ;;

|
|
相关文章:相关软件: |
|