395 lines
12 KiB
Racket
395 lines
12 KiB
Racket
#lang sicp
|
|
(define (square x) (* x x))
|
|
(define (sum-of-square x y) (+ (square x) (square y)))
|
|
(define (abs x)
|
|
(if (> x 0) x
|
|
(- x)))
|
|
(define (>= x y) (not (< x y)))
|
|
|
|
(define (ex-1-3 a b c)
|
|
(cond ((and (< a b) (< a c)) (sum-of-square b c))
|
|
((and (< b a) (< b c)) (sum-of-square a c))
|
|
(else (sum-of-square a b))))
|
|
|
|
(define (good-enough? guess x)
|
|
(< (abs (* (- guess x) 1000)) x))
|
|
(define (average x y) (/ (+ x y) 2))
|
|
(define (sqrt x)
|
|
(define (sqrt-improve guess x) (average guess (/ x guess)))
|
|
(define (sqrt-iter guess x)
|
|
(if (good-enough? (square guess) x)
|
|
guess
|
|
(sqrt-iter (sqrt-improve guess x) x)))
|
|
(sqrt-iter 1.0 x))
|
|
|
|
(define (cube x) (* x x x))
|
|
(define (cbrt x) ; Exercise 1.8
|
|
(define (cbrt-iter guess x)
|
|
(if (good-enough? (cube guess) x)
|
|
guess
|
|
(cbrt-iter (/ (+ (/ x (square guess)) (* 2 guess)) 3) x)))
|
|
(cbrt-iter 1.0 x))
|
|
|
|
(define (dec x) (- x 1))
|
|
(define (inc x) (+ x 1))
|
|
(define (factorial n)
|
|
(if (= n 1) 1 (* n (factorial (dec n)))))
|
|
|
|
; Exercise 1.10
|
|
(define (A x y)
|
|
(cond ((= y 0) 0)
|
|
((= x 0) (* 2 y))
|
|
((= y 1) 2)
|
|
(else (A (dec x) (A x (dec y))))))
|
|
(define (f n) (A 0 n)) ; return 2n
|
|
(define (g n) (A 1 n)) ; return n logical-and 2^n
|
|
(define (h n) (A 2 n)) ; return n logical-and (2 up-arrow up-arrow 2)
|
|
|
|
(define (fibonacci n)
|
|
(define (fibonacci-iter a b m)
|
|
(if (= m n) b (fibonacci-iter b (+ a b) (inc m))))
|
|
(if (= n 0) 0 (fibonacci-iter 0 1 1)))
|
|
|
|
(define (count-change amount)
|
|
(define (first-denomination kinds-of-coins)
|
|
(cond ((= kinds-of-coins 1) 1)
|
|
((= kinds-of-coins 2) 5)
|
|
((= kinds-of-coins 3) 10)
|
|
((= kinds-of-coins 4) 25)
|
|
((= kinds-of-coins 5) 50)))
|
|
(define (cc amount kinds-of-coins)
|
|
(cond ((= amount 0) 1) ; this means the coin change is valid
|
|
((or (< amount 0) (= kinds-of-coins 0)) 0)
|
|
(else (+ (cc amount (dec kinds-of-coins))
|
|
(cc (- amount (first-denomination kinds-of-coins))
|
|
kinds-of-coins)))))
|
|
(cc amount 5))
|
|
|
|
; Exercise 1.11
|
|
(define (f-recursive n)
|
|
(if (< n 3)
|
|
n
|
|
(+ (f-recursive (dec n)) (* (f-recursive (- n 2)) 2)
|
|
(* (f-recursive (- n 3)) 3))))
|
|
(define (f-iterative n)
|
|
(define (f-iter a b c count)
|
|
(if (= count 0) c (f-iter b c (+ c (* b 2) (* a 3)) (dec count))))
|
|
(if (< n 3) n (f-iter 1 2 4 (- n 3))))
|
|
|
|
; Exercise 1.12
|
|
(define (combination-pascal n r)
|
|
(if (or (= n 1) (= r 1))
|
|
1
|
|
(+ (combination-pascal (dec n) (dec r)) (combination-pascal (dec n) r))))
|
|
(define (combination n r) ; well, factorial is recursive :-)
|
|
(/ (factorial n) (factorial r) (factorial (- n r))))
|
|
|
|
(define (even? n) (= (remainder n 2) 0))
|
|
(define (expt-recursive b n)
|
|
(cond ((= n 0) 1)
|
|
((even? n) (square (expt-recursive b (/ n 2))))
|
|
(else (* (expt-recursive b (dec n)) b))))
|
|
; Exercise 1.16
|
|
(define (expt-iterative b n)
|
|
(define (expt-iter b n a)
|
|
(cond ((= n 0) a)
|
|
((even? n) (expt-iter (square b) (/ n 2) a))
|
|
(else (expt-iter b (dec n) (* a b)))))
|
|
(expt-iter b n 1))
|
|
|
|
; Exercise 1.17
|
|
(define (double n) (+ n n))
|
|
(define (halve n) (/ n 2))
|
|
(define (mul-recursive a b)
|
|
(cond ((= b 0) 0)
|
|
((< b 0) (mul-recursive (- a) (- b)))
|
|
; halve only works on even intergers, thus even? must also be included
|
|
((even? b) (double (mul-recursive a (halve b))))
|
|
(else (+ (mul-recursive a (dec b)) a))))
|
|
; Exercise 1.18
|
|
(define (mul-iterative a b)
|
|
(define (mul-iter a b c)
|
|
(cond ((= b 0) c)
|
|
((even? b) (mul-iter (double a) (halve b) c))
|
|
(else (mul-iter a (dec b) (+ c a)))))
|
|
(if (< b 0) (mul-iter (- a) (- b) 0) (mul-iter a b 0)))
|
|
|
|
(define (fib n)
|
|
(define (fib-iter a b p q count)
|
|
; Tpq(a, b) = (bq + aq + ap, bp + aq)
|
|
; Tpq(Tpq(a, b)) = (..., (bp + aq)p + (bq + aq + ap)q)
|
|
; = (..., b(pp + qq) + a(2pq + qq))
|
|
; => p' = pp + qq, q' = 2pq + qq
|
|
(cond ((= count 0) b)
|
|
((even? count)
|
|
(fib-iter a
|
|
b
|
|
(sum-of-square p q)
|
|
(+ (* 2 p q) (square q))
|
|
(/ count 2)))
|
|
(else (fib-iter (+ (* b q) (* a q) (* a p))
|
|
(+ (* b p) (* a q))
|
|
p
|
|
q
|
|
(dec count)))))
|
|
(fib-iter 1 0 0 1 n))
|
|
|
|
; Exercise 1.23
|
|
(define (smallest-divisor n)
|
|
(define (find-divisor test-divisor)
|
|
(cond ((> (square test-divisor) n) n)
|
|
((= (remainder n test-divisor) 0) test-divisor)
|
|
(else (find-divisor (+ test-divisor 2)))))
|
|
(if (even? n) 2 (find-divisor 3)))
|
|
(define (prime? n) (and (> n 1) (= (smallest-divisor n) n)))
|
|
|
|
(define (expmod x y z)
|
|
(cond ((= y 0) 1)
|
|
((even? y) (remainder (square (expmod x (/ y 2) z)) z))
|
|
(else (remainder (* (expmod x (dec y) z) x) z))))
|
|
(define (fermat-prime-trial n a) (= (expmod a n n) a))
|
|
(define (fermat-prime? n times)
|
|
(define (fermat-test n)
|
|
(fermat-prime-trial (inc (random (dec n)))))
|
|
(cond ((= times 0) true)
|
|
((fermat-test n) (fermat-prime? n (dec times)))
|
|
(else false)))
|
|
|
|
; Exercise 1.22
|
|
(define (timed-prime-test n)
|
|
(define (report-prime elapsed-time)
|
|
(display " *** ")
|
|
(display elapsed-time))
|
|
(define (start-prime-test n start-time)
|
|
(if (prime? n) (report-prime (- (runtime) start-time)) false))
|
|
(newline)
|
|
(display n)
|
|
(start-prime-test n (runtime)))
|
|
(define (search-for-primes start n)
|
|
(cond ((< n 0)) ; wow this is valid
|
|
((even? start) (search-for-primes (inc start) n))
|
|
((timed-prime-test start) (search-for-primes (+ start 2) (dec n)))
|
|
(else (search-for-primes (+ start 2) n))))
|
|
|
|
; Exercise 1.25
|
|
(define (expmod-lousy x y z) (remainder (expt-recursive x y) z))
|
|
(define (expmod-effeciency-test func x y z)
|
|
(define (display-elapsed start-time)
|
|
(func x y z)
|
|
(display (- (runtime) start-time))
|
|
(newline))
|
|
(display-elapsed (runtime)))
|
|
|
|
; Exercise 1.27
|
|
(define (slow-fermat-prime? n)
|
|
(define (slow-iter count)
|
|
(cond ((= count 1) true)
|
|
((fermat-prime-trial n count) (slow-iter (dec count)))
|
|
(else false)))
|
|
(slow-iter (dec n)))
|
|
|
|
; Exercise 1.28
|
|
(define (miller-rabin n)
|
|
(define (nontrivial-sqrt-1-mod? m)
|
|
(let ((r (remainder (square m) n)))
|
|
(if (or (not (= r 1)) (= m 1) (= m (dec n))) r 0)))
|
|
(define (expmod-1 x y)
|
|
(cond ((= y 0) 1)
|
|
((odd? y) (remainder (* (expmod-1 x (dec y)) x) n))
|
|
(else (nontrivial-sqrt-1-mod? (expmod-1 x (/ y 2))))))
|
|
(define (miller-rabin-trail a) (= (expmod-1 a (dec n)) 1))
|
|
(define (miller-rabin-iter count)
|
|
(cond ((= count 0))
|
|
((miller-rabin-trail (inc (random (dec n))))
|
|
(miller-rabin-iter (dec count)))
|
|
(else false)))
|
|
(cond ((= n 2) true)
|
|
((or (< n 2) (even? n)) false)
|
|
(else (miller-rabin-iter (/ (dec n) 2)))))
|
|
|
|
(define (sum term a next b)
|
|
(if (> a b) 0 (+ (term a) (sum term (next a) next b))))
|
|
(define (identity x) x)
|
|
(define (sum-integers a b) (sum identity a inc b))
|
|
(define (sum-cubes a b) (sum cube a inc b))
|
|
(define (pi-sum a b)
|
|
(sum (lambda (x) (/ 1.0 x (+ x 2))) a (lambda (x) (+ x 4)) b))
|
|
(define dx 0.00001)
|
|
(define (integral f a b dx)
|
|
(* (sum f (+ a (/ dx 2.0)) (lambda (x) (+ x dx)) b) dx))
|
|
|
|
; Exercise 1.29
|
|
(define (simpson-integral f a b n)
|
|
(define h (/ (- b a) n)) ; sorry!
|
|
(define (fk k) (f (+ a (* k h))))
|
|
(define (y k)
|
|
(cond ((= (remainder k n) 0) (fk k))
|
|
((even? k) (* (fk k) 2))
|
|
(else (* (fk k) 4))))
|
|
(define (simpson-iter k)
|
|
(if (= k 0)
|
|
(y 0)
|
|
(+ (y k) (simpson-iter (dec k)))))
|
|
(* (simpson-iter n) h 1/3))
|
|
|
|
; Exercise 1.30
|
|
(define (sum-iter term a next b)
|
|
(define (iter a result)
|
|
(if (> a b)
|
|
result
|
|
(iter (next a) (+ (term a) result))))
|
|
(iter a 0))
|
|
|
|
; Exercise 1.31
|
|
(define (product-recursive term a next b)
|
|
(if (> a b)
|
|
1
|
|
(* (term a) (product-recursive term (next a) next b))))
|
|
(define (pi-fourth precision)
|
|
(define (john-wallis-term n)
|
|
(* (if (even? n) (/ n (inc n)) (/ (inc n) n)) 1.0))
|
|
(product-recursive john-wallis-term 2 inc (+ (* (abs precision) 2) 2)))
|
|
(define (product-iterative term a next b)
|
|
(define (iter a result)
|
|
(if (> a b)
|
|
result
|
|
(iter (next a) (* (term a) result))))
|
|
(iter a 1))
|
|
|
|
; Exercise 1.32
|
|
(define (accumulate combiner null-value term a next b)
|
|
(if (> a b)
|
|
null-value
|
|
(combiner (term a)
|
|
(accumulate combiner null-value term (next a) next b))))
|
|
(define (sum-recursive term a next b) (accumulate + 0 term a next b))
|
|
(define (accumulate-iter combiner null-value term a next b)
|
|
(define (iter a result)
|
|
(if (> a b)
|
|
result
|
|
(iter (next a) (combiner (term a) result))))
|
|
(iter a null-value))
|
|
|
|
; Exercise 1.33
|
|
(define (filtered-accumulate filter combiner null-value term a next b)
|
|
(if (> a b)
|
|
null-value
|
|
(combiner (if (filter a) (term a) null-value)
|
|
(filtered-accumulate filter
|
|
combiner
|
|
null-value
|
|
term
|
|
(next a)
|
|
next
|
|
b))))
|
|
(define (sum-square-primes a b)
|
|
(filtered-accumulate prime? + 0 square a inc b))
|
|
(define (product-relative-primes n)
|
|
(filtered-accumulate (lambda (i) (= (gcd i n) 1)) * 1 identity 1 inc (dec n)))
|
|
|
|
(define (search f neg-point pos-point)
|
|
(let ((midpoint (average neg-point pos-point)))
|
|
(if (good-enough? neg-point pos-point)
|
|
midpoint
|
|
(let ((test-value (f midpoint)))
|
|
(cond ((positive? test-value) (search f neg-point midpoint))
|
|
((negative? test-value) (search f midpoint pos-point))
|
|
(else midpoint))))))
|
|
|
|
(define (half-interval-method f a b)
|
|
(let ((a-value (f a))
|
|
(b-value (f b)))
|
|
(cond ((and (negative? a-value) (positive? b-value))
|
|
(search f a b))
|
|
((and (negative? b-value) (positive? a-value))
|
|
(search f b a))
|
|
(else (error "Values are not of opposite sign" a b)))))
|
|
|
|
(define (fixed-point f first-guess)
|
|
(define (try guess)
|
|
(let ((next (f guess)))
|
|
(if (good-enough? guess next) next (try next))))
|
|
(try first-guess))
|
|
|
|
(define (sqrt-fixed x)
|
|
(fixed-point (lambda (y) (average y (/ x y))) 1.0))
|
|
|
|
; Exercise 1.35
|
|
(define golden-ratio (fixed-point (lambda (x) (inc (/ x))) 1.0))
|
|
|
|
; Exercise 1.37
|
|
(define (cont-frac-recursive n d k)
|
|
(define (cont-frac n d k root)
|
|
(if (= k 0)
|
|
root
|
|
(cont-frac n d (dec k) (/ (n k) (+ (d k) root)))))
|
|
(if (> k 0)
|
|
(cont-frac n d (dec k) (/ (n k) (d k)))
|
|
(error "You weirdo!")))
|
|
(define (cont-frac-iterative n d k)
|
|
(define (cont-frac n d k c)
|
|
(if (< c k)
|
|
(/ (n c) (+ (d c) (cont-frac n d k (inc c))))
|
|
(/ (n k) (d k)))) ; UB if k is not a positive integer
|
|
(cont-frac n d k 1))
|
|
|
|
; Exercise 1.38
|
|
(define (e-2 precision)
|
|
(cont-frac-iterative
|
|
(lambda (i) 1.0)
|
|
(lambda (i) (if (= (remainder i 3) 2) (* (inc i) 2/3) 1.0))
|
|
precision))
|
|
|
|
; Exercise 1.39
|
|
(define (tan-cf x k)
|
|
(cont-frac-iterative
|
|
(lambda (i) (if (= i 1) x (square x)))
|
|
(lambda (i) ((if (even? i) - +) (dec (* i 2))))
|
|
k))
|
|
|
|
(define (average-damp f) (lambda (x) (average x (f x))))
|
|
(define (newton-method g guess)
|
|
(define (deriv g)
|
|
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
|
|
(let ((f (lambda (x) (- x (/ (g x) ((deriv g) x))))))
|
|
(fixed-point f guess)))
|
|
|
|
(define (fixed-point-of-transform g transform guess)
|
|
(fixed-point (transform g) guess))
|
|
|
|
; Exercise 1.40
|
|
(define (cubic a b c)
|
|
(lambda (x) (+ (cube x) (* (square x) a) (* x b) c)))
|
|
|
|
; Exercise 1.41
|
|
(define (duplicate f) (lambda (x) (f (f x))))
|
|
|
|
; Exercise 1.42
|
|
(define (compose f g) (lambda (x) (f (g x))))
|
|
|
|
; Exercise 1.43
|
|
(define (repeated f times)
|
|
(cond ((< times 1) identity)
|
|
((= times 1) f)
|
|
(else (compose f (repeated f (dec times))))))
|
|
|
|
; Exercise 1.44
|
|
(define (smooth f)
|
|
(lambda (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))
|
|
(define (repeated-smooth f times) (repeated smooth times))
|
|
|
|
; Exercise 1.45
|
|
(define (root n x)
|
|
(fixed-point-of-transform
|
|
(lambda (y) (/ x (expt y (dec n))))
|
|
(repeated average-damp (log n 2))
|
|
1.0))
|
|
|
|
; Exercise 1.46
|
|
(define (iter-improve good-enough improve)
|
|
(lambda (x)
|
|
(let ((xim (improve x)))
|
|
(if (good-enough x xim)
|
|
xim
|
|
((iter-improve good-enough improve) xim)))))
|