; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/28/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.23
;; 定义next函数，改动find-divisor定义
(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)))))
(define (next n)
(if (= n 2) 3 (+ n 2)))
;; Test-it:
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (search-for-primes 1000 3)
;;
;; 1001
;; 1003
;; 1005
;; 1007
;; 1009 *** 0.027099609375
;; 1011
;; 1013 *** 0.02685546875
;; 1015
;; 1017
;; 1019 *** 0.026123046875
;; finish
;;
;; > (search-for-primes 10000 3)
;;
;; 10001
;; 10003
;; 10005
;; 10007 *** 0.071044921875
;; 10009 *** 0.072021484375
;; 10011
;; 10013
;; 10015
;; 10017
;; 10019
;; 10021
;; 10023
;; 10025
;; 10027
;; 10029
;; 10031
;; 10033
;; 10035
;; 10037 *** 0.071044921875
;; finish
;;
;; > (search-for-primes 100000 3)
;;
;; 100001
;; 100003 *** 0.222900390625
;; 100005
;; 100007
;; 100009
;; 100011
;; 100013
;; 100015
;; 100017
;; 100019 *** 0.218017578125
;; 100021
;; 100023
;; 100025
;; 100027
;; 100029
;; 100031
;; 100033
;; 100035
;; 100037
;; 100039
;; 100041
;; 100043 *** 0.2177734375
;; finish
;;
;; 根据两次测试数据
;; 1000 10000 100000
;; 1 0.039 0.115 0.363
;; 2 0.026 0.071 0.219
;; 我们可见第2种算法用时并非达到第一种的50%左右，而是60%-65%之间
;; 这是因为，尽管第二种算法的递归次数减小一半，但每次递归的成本增加了，
;; next函数每次都要进行函数调用，并进行条件判断，这增加了一定的成本。
;;
;; 如果需要测试：在不考虑next的成本的前提下，是否真的可以将时间缩短一半
;; 我们可以进行如下改动: 将text-divisor直接每次(+ 2)不再使用next函数，
;; 而初始测试数改为3，这样的改动在程序逻辑上是错误的，因为某些仅可以被2
;; 整除的书将被判断为质数，我们仅对3,5,7,9..进行判断。但是，对于那些本
;; 身就是质数的数，其执行过程是不变的，而且判断的数字正好减少一半，其他
;; 什么都不变。而我们要观测的正是那些质数的判断时间。改动如下
;; (define (find-divisor n test-divisor)
;; (cond ((> (square test-divisor) n) n)
;; ((divides? test-divisor n) test-divisor)
;; (else (find-divisor n (+ 2 test-divisor)))))
;; (define (smallest-divisor n)
;; (find-divisor n 3))
;; 经过测试t(1000)=0.21, t(10000)=0.59 t(100000)=0.181，差不多正好
;; 是第一次测试中的一半时间。
|
本类阅读TOP10