1.2 过程与它们所产生的计算

Exercise 1.9

(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9


(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9


Exercise 1.10

1024, 65536, 65536


$f(n)=2n$
$g(n)=2^n$
$h(n)=2^{2^{2^{\cdot^{\cdot^\cdot}}}}(\text{共有}\,n\,\text{个}\,2)$

Exercise 1.11

(define (f n)
(if (< n 3)
n
(+ (f (- n 1))
(f (- n 2))
(f (- n 3)))))


(define (f-iter n)
(define (f-impl n a b c)
(if (= n 0)
a
(f-impl (- n 1) b c (+ a b c))))
(f-impl n 0 1 2))


Exercise 1.12

(define (pascal row col)
(if (or (= col 0) (= row col))
1
(+ (pascal (- row 1) (- col 1))
(pascal (- row 1) col))))


Exercise 1.13

$${\rm Fib}(n)={\rm Fib}(n-1)+{\rm Fib}(n-2)$$

\begin{aligned}\frac{\phi^n-\psi^n}{\sqrt5}=\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt5}+\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt5}\\\phi^n-\psi^n=\phi^n\left(\frac1\phi+\frac1{\phi^2}\right)-\psi^n\left(\frac1\psi+\frac1{\psi^2}\right)\end{aligned}

$$\frac1\phi+\frac1{\phi^2}=1,\;\frac1\psi+\frac1{\psi^2}=1$$

\begin{aligned}{\rm Fib}(n)=\frac{\phi^n-\psi^n}{\sqrt5}=\frac{\phi^n}{\sqrt5}-\frac{\psi^n}{\sqrt5}\\\frac{\phi^n}{\sqrt5}={\rm Fib}(n)+\frac{\psi^n}{\sqrt5}\end{aligned}

Exercise 1.14

(cc amount kinds) 节点包含着种类数不变而零钱量减少某个常数的节点，其以下部分的最大深度显然与 amount 成正比，所以空间为 $\Theta(n)$ 。

Exercise 1.15

a. p 被调用了 $5$ 次。
b. 空间增长为 $\Theta(\log n)$ 阶，时间增长也为 $\Theta(\log n)$ 阶。

Exercide 1.16

(define (fast-expt b n)
(define (fast-expt-impl ans tmp m)
(if (= m 0)
ans
(if (even? m)
(fast-expt-impl ans (square tmp) (/ m 2))
(fast-expt-impl (* ans tmp) tmp (- m 1)))))
(fast-expt-impl 1 b n))


Exercise 1.17

(define (double x) (+ x x))
(define (halve x) (/ x 2))

(define (mul a b)
(if (= b 0)
0
(if (even? b)
(mul (double a) (halve b))
(+ a (mul a (- b 1))))))


Exercise 1.18

(define (double x) (+ x x))
(define (halve x) (/ x 2))

(define (mul a b)
(define (mul-impl ans tmp m)
(if (= m 0)
ans
(if (even? m)
(mul-impl ans (double tmp) (halve m))
(mul-impl (+ ans tmp) tmp (- m 1)))))
(mul-impl 0 a b))


Exercise 1.19

(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(+ (* p p) (* q q))
(+ (* q q) (* p q 2))
(/ count 2)))
(else
(fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))


Exercise 1.20

(gcd 206 40)
(gcd 40 (remainder 206 40))
(gcd 6 (remainder 40 6))
(gcd 4 (remainder 6 4))
(gcd 2 (remainder 4 2))
(gcd 2 0)
2


remainder 一共被调用了 $4$ 次。

(gcd 206 40)
(if (= 40 0) ...)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0) ...)
(if (= 6 0) ...)
(gcd (remainder 206 40) (remainder 40 (remainder 206 40)))
(if (= (remainder 40 (remainder 206 40)) 0) ...)
(if (= 4 0) ...)
(gcd (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) ...)
(if (= 2 0) ...)
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
(if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) ...)
(if (= 0 0) ...)
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
2


remainder 一共被调用了 $18$ 次：$14$ 次用在条件判断中，$4$ 次用在最后的计算中。

\begin{aligned}f(0)&=0,\;f(1)=1\\f(n)&=f(n-1)+f(n-2)+1\end{aligned}

\begin{aligned}f(n)-f(n-1)&={\rm Fib}(n)\\f(n)&=\sum_{i=0}^n{\rm Fib}(i)\\f(n)&={\rm Fib}(n+2)-1\end{aligned}

remainder 在应用序求值中的总调用次数为 $n$，在正则序求值中的总调用次数为 ${\rm R}(n)$，可以得出

\begin{aligned}{\rm R}(n)&=n+\sum_{i=0}^nf(i)\\{\rm R}(n)&={\rm Fib}(n+4)-3\end{aligned}

Exercise 1.21

199, 1999, 7


Exercise 1.22

(define (report-time start-time)
(display (- (runtime) start-time))
(newline))
(define (conditional-time-report pred-proc p1)
(define (timer start-time)
(cond ((pred-proc p1) (report-time start-time) #t)
(else #f)))
(timer (runtime)))
(define (search-for-primes num cnt)
(if (> cnt 0)
(if (conditional-time-report prime? num)
(search-for-primes (+ num 2) (- cnt 1))
(search-for-primes (+ num 2) cnt))))
(search-for-primes <an odd number to start with> <how many prime numbers before stop>)


$n$ 每增加 $4$ 倍，运行时间大约增加 $2$ 倍，这可以粗略地验证该算法的增长阶为 $\Theta(\sqrt n)$ 。

Exercise 1.27

(define (full-fermat-test n)
(define (test-it a)
(= (expmod a n n) a))
(define (test-impl m)
(cond ((= m n) #t)
((test-it m) (test-impl (+ m 1)))
(else #f)))
(test-impl 1))
(full-fermat-test 561)
(full-fermat-test 1105)
(full-fermat-test 1729)
...
(prime? 561)
(prime? 1105)
(prime? 1729)
...


prime? 确定它们都不是素数，但 “骗过” 了所有费马测试。

Exercise 1.28

\begin{aligned}\begin{aligned}x^2&\equiv1\;({\rm mod}\;n)\\x^2-1&\equiv0\;({\rm mod}\;n)\\(x-1)(x+1)&\equiv0\;({\rm mod}\;n)\end{aligned}\\\begin{aligned}&\therefore n\mid(x-1)\;\text{或}\;n\mid(x+1)\\&\because n\;\text{是素数}\;\therefore(x-1)\;\text{或}\;(x+1)\;\text{是}\;n\;\text{的倍数}\\&\therefore x_1=1,x_2=n-1\end{aligned}\end{aligned}

(define (square x) (* x x))

(define (miller-rabin-expmod base ex n)
(define (squaremod-with-check x)
(define (check squaremod-x)
(if (and (= squaremod-x 1)
(not (= x 1))
(not (= x (- n 1))))
0
squaremod-x))
(check (remainder (* x x) n)))
(cond ((= ex 0) 1)
((even? ex)
(squaremod-with-check (miller-rabin-expmod base (/ ex 2) n)))
(else
(remainder (* base (miller-rabin-expmod base (- ex 1) n)) n))))

(define (miller-rabin-test n rounds)
(define (test-it a)
(define (test-impl expmod-a)
(= expmod-a 1))
(test-impl (miller-rabin-expmod a (- n 1) n)))
(cond ((= rounds 0) #t)
((test-it (+ 1 (random (- n 1))))
(miller-rabin-test n (- rounds 1)))
(else #f)))