1.22

练习 1.22: 大部分 Lisp 实现都包含一个 runtime 基本过程,调用它将返回一个整数,表示系统已经允许的时间(例如,以微秒计)。在对整数 n 调用下面的 timed-prime-test 过程时,将打印出 n 并检查 n 是否是素数。如果 n 是素数,过程将打印出三个星号,随后是执行这一检查所用的时间量。

(define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time))

请利用这一过程写一个 search-for-primes 过程,它检查给定范围内连续的各个奇数的素性。请用你的过程找出大于 1 000、大于 10 000、大于 100 000 和大于 1 000 000 的三个最小素数。请注意其中检查每个素数所需要的时间。因为这一检查算法具有 Θ(n)\Theta(\sqrt n) 的增长阶,你可以期望在 10 000 附近的素数检查的耗时大约是在 1 000 附近的素数检查的 10\sqrt{10} 倍。你得到的数据确实如此吗?对于 100 000 和 1 000 000 得到的数据,对这一 n\sqrt n 预测的支持情况如何?有人说程序在你的机器上运行的时间正比于计算所需的步数,你得到的结果符合这种说法吗?

先看下 timed-prime-test 执行的效果:

(define (timed-prime-test n) (newline) (display n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (runtime) start-time)) (display " 不是素数!"))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) (define (prime? n) (= n (smallest-divisor n))) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0)) (define (square x) (* x x)) (timed-prime-test 7) (timed-prime-test 14)

分别找出大于 1 000、 10 000、 100 000、 1 000 000 的三个最小素数

(define (timed-prime-test n) (start-prime-test n (runtime))) (define (start-prime-test n start-time) (if (prime? n) (report-prime n (- (runtime) start-time)) #f)) (define (sqrt-iter lastGuess guess x) (if (good-enough? lastGuess guess) guess (sqrt-iter guess (improve guess x) x) ) ) (define (good-enough? lastGuess guess) (< (abs (- lastGuess guess)) 0.001) ) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (report-prime n elapsed-time) (newline) (display n) (display " *** ") (display elapsed-time) (display ", 它的 \\sqrt{n} 倍时间是 ") (display (* elapsed-time (sqrt-iter 1 10 elapsed-time))) ) (define (prime? n) (= n (smallest-divisor n))) (define (smallest-divisor n) (find-divisor n 2)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0)) (define (square x) (* x x)) (define (timed-prime-test-between n1 n2 found) (if (timed-prime-test n1) (if (or (> found 1) (> n1 n2)) (display " 测试结束! ") (timed-prime-test-between (+ n1 1) n2 (+ found 1)) ) (if (> n1 n2) (display " 测试结束! ") (timed-prime-test-between (+ n1 1) n2 found) ) ) ) (newline) (display "大于 1000 的三个最小素数:") (timed-prime-test-between 1001 9999 0) (newline) (newline) (display "大于 10 000 的三个最小素数:") (timed-prime-test-between 10001 99999 0) (newline) (newline) (display "大于 100 000 的三个最小素数:") (timed-prime-test-between 100001 999999 0) (newline) (newline) (display "大于 1 000 000 的三个最小素数:") (timed-prime-test-between 1000001 9999999 0) (newline)

从这样的结果来看,还是非常符合 n \sqrt n 的预测的。运行的时间正比于执行所需步骤的判断也是正确的。

results matching ""

    No results matching ""