diff options
| -rw-r--r-- | sicp/scratch.rkt | 305 | ||||
| -rw-r--r-- | sicp/sicp.pdf | bin | 0 -> 7416886 bytes |
2 files changed, 305 insertions, 0 deletions
diff --git a/sicp/scratch.rkt b/sicp/scratch.rkt new file mode 100644 index 0000000..298d42d --- /dev/null +++ b/sicp/scratch.rkt @@ -0,0 +1,305 @@ +#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 (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))))) diff --git a/sicp/sicp.pdf b/sicp/sicp.pdf new file mode 100644 index 0000000..b82e4ac --- /dev/null +++ b/sicp/sicp.pdf Binary files differ |