[Back]

1.2 过程与产生它们的计算

1.9

(define (+ a b)
   (if (= a 0)
       b
      (inc (+ (dec a) b))))
(define (+ a b)
    (if (= a 0)
        b
        (+ (dec a) (inc b))))

1.10

; Ackermann

(define (A x y)
    (cond ((= y 0) 0)
               ((= x 0) (* 2 y))
               ((= y 1) 2)
               (else (A (- x 1)
                             (A x (- y 1))))))

; (A 1 10) = 2^10
; (A 2 4) = 65536
; (A 3 3) = 65536

(define (f n) (A 0 n)) = 2*n
(define (g n) (A 1 n)) = 2^n
(define (h n) (A 2 n)) = 2^2^2^…2(n个2)

1.11

(define (f n)
(cond ((< n 3) n)
(else (+ (f (- n 1))
(* 2 (f (- n 2)))
(* 3 (f (- n 3)))))))

(define (f-iter a b c n)
(cond ((= n 0) c)
((= n 1) b)
((= n 2) a)
(else (f-iter (+ a
(* 2 b)
(* 3 c)
) a b (- n 1)))))
(define (f n)
(f-iter 2 1 0 n))

1.12

(define (pascal row col)
	(cond ((or (= row col) (= col 1)) 1)
		  (else (+ (pascal (- row 1) (- col 1))
				  (pascal (- row 1) col)))))

1.13

1.14

空间 , 时间

1.15

A) 调用了5次

B)空间和时间复杂度都是

1.16

(define (square a) (* a a))
(define (even? n) (= (remainder n 2) 0))
(define (pow-iter a b n)
	(cond ((= n 0) a)
		  ((even? n) (pow-iter a
		  			(square b) (/ n 2)))
		  (else (pow-iter (* b a) b (- n 1)))))
(define (pow b n) (pow-iter 1 b n))

1.17

(define (double a) (+ a a))
(define (halve a) (/ a 2))
(define (even? n) (= (remainder n 2) 0))
(define (fast-multi a b)
    (cond ((= b 0) 0)
          ((even? b) (double (fast-multi a (halve b))))
          (else (+ a (fast-multi a (- b 1))))))

1.18

(define (double a) (+ a a))
(define (halve a) (/ a 2))
(define (even? n) (= (remainder n 2) 0))
(define (multi-iter a b n)
    (cond ((= b 0) n)
          ((even? b) (multi-iter (double a) (halve b) n))
          (else (multi-iter a (- b 1) (+ a n)))))
(define (multi a b) (multi-iter a b 0))

1.19

For some calculation,

1.20

正则序的调用remainder次数非常多,由于递归深度加深,每次判断if语句都要调用递归深度的remainder,因此造成了极大的浪费。而应用序则只需要递归深度的remainder调用。

1.21

(smallest-divisior 199) = 199

(smallest-divisior 1999) = 19999

(Smallest-divisior 19999) = 7

1.22

(define (search-for-primes n number)
    (cond ((= number 0) (display " end "))
          ((prime? n) (newline) (display n) (search-for-primes (+ n 2) (- number 1)))
          (else (search-for-primes (+ n 2) number))))
(define (timed-search n number start-time)
    (search-for-primes n number)
        (- (current-milliseconds) start-time))

1.23

欧拉筛

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

1.24

(define (fermat-test n)
(define (try-it a)
    (= (expmod a n n) a))
        (try-it (+ 1 (random (- n 1)))))
(define (prime? n times)
    (cond ((= times 0) true)
          ((fermat-test n) (prime? n (- times 1)))
          (else false)))

费马检查次数设定32, 将Fermat检查替换原来的筛法。进行运行

分别是1ms 2ms 1ms 0ms

对于复杂度给一个总结:增长阶仅仅给了我们一个粗略的估计算法优劣和复杂度的工具,实际情况还受编译器,系统资源以及数值计算的规模等因素的印象。

我们的测试样例都比较小,实际上,在更大的规模时候,我们会发现复杂度更低的算法一定会体现出优势的。

我的理解:增长阶是复杂度的一个有效抽象

1.25

不可以,经过fast-expt计算出的数字十分之大,这是在增加复杂度,甚至会使得数字太大造成溢出。

1.26

我们发现乘法的两项都调用了递归,这就相当于计算了一个树形递归,它的复杂度就变成了普通乘幂的复杂度,也就是

了。

1.27

(prime? 561 128)

(prime? 6601 128)

(prime? 1729 128)

即使次数128都会被骗过,这个概率是1-1/2^128了。

1.28

(define (expmod base exp m)
    (cond ((= exp 0) 1)
          ((miller-rabin? base n) 0)
          ((even? exp) (remainder (square (expmod base (/ exp 2) m)) m))
          (else (remainder (* base (expmod base (- exp 1) m)) m))))
(define (miller-rabin? a n)
    (cond ((= a 1) 0)
          ((= a (- n 1) 0))
          ((= (remainder (square a) n) 1) 1)
          (else 0)))
(define (fermat-test n)
(define (try-it a)
    (= (expmod a (- n 1) n) a))
        (try-it (+ 1 (random (- n 1)))))
(define (prime? n times)
    (cond ((= times 0) true)
          ((fermat-test n) (prime? n (- times 1)))
          (else false)))

再次检测Carmichael数,都死了(然而Miller-Rabin素性判定也需要至少n/2次才能保证正确性。