; ======================================================================
;
; 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
;; >
;;
本文地址：http://com.8s8s.com/it/it23140.htm