当前位置: 代码迷 >> 综合 >> SICP 1.22
  详细解决方案

SICP 1.22

热度:58   发布时间:2023-09-29 12:38:29.0

search-for-primes 函数接受参数 n ,找出大于等于 n 的三个素数,并且返回运行时间。
可以将不同的函数放置在不同的文件中方便调用
例如在文件one.rkt中有

#lang racket
(provide square)(define (square x)(* x x))

之后可以在two.rkt中调用该函数接口

#lang racket
(require "one.rkt")

首先定义函数 next-odd 接受一个参数 n ,生成跟随在 n 之后的第一个奇数:

(define (next-odd n)(if (odd? n)(+ 2 n)(+ 1 n)))

改写书本 33 页的 prime? 函数用于检测给定数是否为素数:

(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)))))

对于原来的find-divisor函数,第一个判断用于停止该函数的运行:

(= n (smallest-divisor n)))

第2个判断是否为因子
(remainder b a)用于返回b除以a的余数。

(define (divides? a b)(= (remainder b a) 0))

如果2不是n的因子,那么在后面都不需要对2的倍数进行判断。通过定义next函数对prime? 函数进行优化:

(define (next n)(if (= n 2)3(+ n 2)))

(find-divisor n (+ test-divisor 1))

改为

(find-divisor n (next test-divisor))

此时引入覆盖的概念:当一个环境中存在两个同名的绑定时,新的绑定会覆盖旧的绑定。例如文件 f.scm ,里面有 a 、 b 、 c 、 d 四个函数,如果我们需要修改函数 b ,而且还要重用函数 a 、 c 和 d ,那么新建f1.scm ,先载入 func.scm ,然后进行新的函数 b 的定义。
(虽然在此题中被覆盖的函数显得更慢,但是在别的情况下可能需要保存原函数以解决不同的情况)

(define (prime? n)(= n (smallest-divisor n)))
(define (smallest-divisor n)(find-divisor n 2))

利用前面2个函数定义生成连续素数的 continue-primes 函数。

(define (continue-primes n count)(cond ((= count 0)(display "are primes."))((prime? n)(display n)(newline)(continue-primes (next-odd n) (- count 1)))(else(continue-primes (next-odd n) count))))

首先使用 next-odd 生成一个奇数,然后使用 prime? 检查给定的奇数是否素数,一直这样计算下去,直到满足参数 count 指定的数量为止。

最终根据

(define (test-foo)(let ((start-time (real-time-clock)))(foo)(- (real-time-clock) start-time)))

写出search-for-primes函数:

(define (search-for-primes n)(let ((start-time (real-time-clock)))(continue-primes n 3)(- (real-time-clock) start-time)))

由于书本给出的 timed-primes-test会使程序过于复杂。但是编译器显示real-time-clock未定义。
该函数也体现了将过程(函数)作为参数。