Learn faster and stay on-track by joining this free class with other self-learners.
Register for Structure and Interpretation of Computer Programs now.
|
Structure and Interpretation of Computer ProgramsClass length: 13 weeks. Start anytime. Creator: kday Status: Established |
Join this class! |
|
Lesson 3: Assignment 1Section 1.3, Selected ExercisesDo exercises 1.29, 1.30, 1.31, 1.35, 1.37, 1.39, 1.41, 1.42, 1.43 in Section 1.3 Homework Submissions6 total
;Exercise 1.29
;The procedure based on Simpsons's Rule gives as said better results
(define (integral f a b n)
(define h (/ (- b a) n))
(define (y k) (+ a (* k h)))
(define (term k)
(if (= (remainder k 2) 0)
(* 2.0 (f (y k)))
(* 4.0 (f (y k)))))
(define (inc x) (+ x 1))
(* (/ h 3) (+ (f (y 0))
(sum term 1 inc (- n 1))
(f (y n)))))
(integral cube 0 1 100)
0.24999999999999992
(integral cube 0 1 1000)
0.2500000000000002
;Exercise 1.30
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))
;Exercise 1.31
;Recursive process
(define (product factor a next b)
(if (> a b)
1
(* (factor a)
(product factor (next a) next b))))
;Iterative process
(define (product2 factor a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* result (factor a)))))
(iter a 1))
(define (factorial n)
(define (self x) x)
(define (inc x) (+ x 1))
(product2 self 1 inc n))
(define (pi-prod n)
(define (sq x) (* x x))
(define (next x) (+ x 2))
(define last (* 2 n))
(* 4 ( / ( / (product2 sq 2 next last) 2.0 last)
(product2 sq 3 next last))))
(factorial 10)
3628800
(pi-prod 50)
3.157339689217565
;Exercise 1.35
(define golden-ratio (fixed-point
(lambda (x) (+ 1.0 (/ 1.0 x)))
1.0))
golden-ratio
1.6180327868852458
;Exercise 1.37
;k must be 11 to get an approximation that is accurate to 4 decimal places
(define (cont-frac n d k)
(define (helper i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i)
(helper (+ i 1))))))
(helper 1))
;Iterative process
;it computes the fraction bottom-up, starting with Nk/Dk
(define (cont-frac1 n d k)
(define (helper i result)
(if (= i 1)
(/ (n 1) (+ (d 1) result))
(helper (- i 1) (/ (n i) (+ (d i) result)))))
(helper k 0))
;Exercise 1.39
(define (tan-cf x k)
(cont-frac (lambda (i) (if (= i 1)
x
(- (square x))))
(lambda (i) (+ 1 (* 2 (- i 1))))
k))
;Exercise 1.41
(define (double f)
(lambda (x) (f (f x))))
;Exercise 1.42
(define (compose f g)
(lambda (x) (f (g x))))
;Exercise 1.43
(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))
#lang planet neil/sicp
;; A few helper procedures
(define (show x) (display x) (newline))
(define (inc n) (+ n 1))
(define (identity x) x)
(define (square x) (* x x))
;; Ex 1.29
;;;
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (integral f a b dx)
(define (add-dx x) (+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
; Simpson's rule
; (h/3)[Y0 + 4y1 + 2Y2 + 4Y3 + ... + 4Yn-1 + Yn]
; h = (b-a)/n
; Yk = f(a+kh)
(define (simpson-integral f a b n)
(define (y-term k h)
(let ((y (f (+ a (* k h)))))
(cond ((or (zero? k)
(= k n)) y)
((even? k) (* 2 y))
(else (* 4 y)))))
(let ((h (/ (- b a) n)))
(* (/ h 3)
(sum (lambda (k) (y-term k h)) 0 inc n))))
;(integral cube 0 1 0.01)
; 0.24998750000000042
;(simpson-integral cube 0 1 100)
; 1/4
;(integral cube 0 1 0.001)
; 0.249999875000001
;(simpson-integral cube 0 1 1000)
; 1/4
;;; Ex 1.30
;;;
(define (sum-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))
(define (simpson-integral-iter f a b n)
(define (y-term k h)
(let ((y (f (+ a (* k h)))))
(cond ((or (zero? k)
(= k n)) y)
((even? k) (* 2 y))
(else (* 4 y)))))
(let ((h (/ (- b a) n)))
(* (/ h 3)
(sum-iter (lambda (k) (y-term k h)) 0 inc n))))
;;; Ex 1.31 a)
;;
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
(define (factorial n)
(cond ((zero? n) 1)
(else (product identity 1 inc n))))
(define PI-LIMIT 1000)
(define (almost-pi)
(define (pi-term k)
(let* ((numer1 (* 2 k))
(denom (+ numer1 1))
(numer2 (+ denom 1)))
(/ (* numer1 numer2)
(square denom))))
(* 4.0 (product pi-term 1 inc PI-LIMIT)))
;;; Ex 1.31 b)
;;
(define (product-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* result (term a)))))
(iter a 1))
(define (almost-pi-iter)
(define (pi-term k)
(let* ((numer1 (* 2 k))
(denom (+ numer1 1))
(numer2 (+ denom 1)))
(/ (* numer1 numer2)
(square denom))))
(* 4.0 (product-iter pi-term 1 inc PI-LIMIT)))
(define (factorial-iter n)
(cond ((zero? n) 1)
(else (product-iter identity 1 inc n))))
;;; Ex 1.35
; f(x)=1+ 1/x
; Fixed point f =>
; 1+1/x = x
; x+1=x^2
;x^2-x-1=0
; ax^2+bx+c=0 => a=1 b=-1 c=-1
; solving for reals
; [ -b+sqrt(b^2-4ac) ] / 2a => (1+r5)/2
; = phi
;
;;
(define phi-tolerance 0.00001)
(define (close-enough? v1 v2 tolerance)
(< (abs (- v1 v2)) tolerance))
(define (fixed-point f first-guess)
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next phi-tolerance)
next
(try next))))
(try first-guess))
(define (phi)
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
;;; Ex 1.37 a
;;
(define (cont-frac n d k)
(cond ((zero? k) 0)
(else (/ (n k)
(+ (d k) (cont-frac n d (- k 1)))))))
(define 1/phi-tolerance 0.00005)
(define (1/phi)
(define (try target k)
(let ((1/phi-k (cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k)))
(cond ((close-enough? target 1/phi-k 1/phi-tolerance)
(show k)
1/phi-k)
(else (try target (+ k 1))))))
(try (/ 1 (phi)) 1))
;;; Ex 1.37 b
;;
(define (cont-frac-iter n d k)
(define (iter k result)
(cond ((zero? k) result)
(else (iter (- k 1)
(/ (n k)
(+ (d k) result))))))
(iter k 0))
(define (1/phi-iter)
(define (try target k)
(let ((1/phi-k (cont-frac-iter (lambda (i) 1.0)
(lambda (i) 1.0)
k)))
(cond ((close-enough? target 1/phi-k 1/phi-tolerance)
(show k)
1/phi-k)
(else (try target (+ k 1))))))
(try (/ 1 (phi)) 1))
;(/ 1 (phi))
;0.6180344478216819
;(1/phi)
;11
;0.6180555555555556
; k = 11
;(1/phi-iter)
;11
;0.6180555555555556
; k = 11
;;; Ex 1.39
;;
(define (tan-cf x k)
(cont-frac-iter (lambda (i)
(if (= i 1) x (- (square x))))
(lambda (i)
(- (* 2 i) 1))
k))
;;; Ex 1.41
;;
(define (double f)
(lambda (x)
(f (f x))))
;(((double (double double)) inc) 5)
;21
;;; Ex 1.42
;;
(define (compose f g)
(lambda (x)
(f (g x))))
;;; Ex 1.43
;;
(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))
(define (repeated-iter f n)
(define (iter k result)
(cond ((= k 1) result)
(else (compose f (repeated f (- k 1))))))
(iter n f))
No comments. Sign up or log in to comment 
;; Exercise 1-35 The equation x = 1 + 1/x has fixed point solutions: phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5)/2) To show this we solve for x in the above equation. (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) ;Value: 1.6180327868852458 ;; Exercise 1-29
(define (cube x) (* x x x))
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (integral f a b dx)
(define (add-dx x) (+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
(define (even? n)
(= (remainder n 2) 0))
(define (simpsons-rule f a b n)
(define even_n (if (even? n) n (+ n 1)))
(define h (/ (- b a) even_n))
(define (add-h x) (+ x h))
(define (add-2h x) (+ x h h))
(* (+ (f a)
(* 2.0 (sum f (+ a h) add-h (- b h)))
(* 2.0 (sum f (+ a h) add-2h (- b h)))
(f b))
(/ h 3.0)))
(simpsons-rule cube 0 1 1000)
;; Exercise 1-30
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))
;; Exercise 1-31
(define (square x) (* x x))
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
(define (fact n)
(define (identity x) x)
(define (inc n) (+ n 1))
(product identity 1 inc n))
(define (wallis-pi n)
(define (wallis-term x)
(square (/ (+ x 1) x)))
(define (wallis-next x) (+ x 2))
(/ (* 2.0 (product wallis-term 3 wallis-next n)) n))
;; Exercise 1-37
(define (cont-frac n d k)
(define (try-it i)
(if (> i k)
0
(/ (n i) (+ (d i) (try-it (+ i 1))))))
(try-it 1))
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
10)
(define phi (/ 2 (+ 1 (sqrt 5))))
(- .6179775280898876 phi)
;Value: -5.6460659971224736e-5
(define (cont-frac n d k)
(define (iter i denominator)
(if (= i 0)
denominator
(iter (- i 1) (/ (n i) (+ (d i) denominator)))))
(iter k 0))
;; Example 1-41
(define (inc n) (+ n 1))
(define (double f)
(lambda (x) (f (f x))))
((double inc) 1) ; Value 3
; let double = d
; let (d d) = g = 4 times
; let (d g) = h = (g g) = ((d d) (d d))
= (4 times (4 times))
= 16 times
(((double (double double)) inc) 5) ; Value 21
;; Example 1-42
(define (compose f g)
(lambda (x) (f (g x))))
((compose square inc) 6) ; Value 49
;; Example 1-43
(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))
((repeated square 2) 5) ; Value 625
No comments. Sign up or log in to comment 
;; ====================================
;; exercise 1.29
(define (simpson-int f a b n)
(define h (/ (- b a) n))
(define (term k)
(* (f (+ a (* k h)))
(cond
((or (= k 0) (= k n)) 1)
((even? k) 2.0)
(else 4.0))))
(* (/ h 3.0)
(sum term 0 inc n)))
;; (simpson-int cube 0 1 100)
;; > .24999999999999992
;;
;; This has the same order that
;; (integral cube 0 1 0.01)
;; > .24998750000000042
;; Which has larger error
;;
;;
;; (simpson-int cube 0 1 1000)
;; > .2500000000000002
;;
;; (integral cube 0 1 0.001)
;; > .249999875000001
;; ====================================
;; exercise 1.30
(define (sum-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))
;; ====================================
;; exercise 1.31 a
;;
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
(define (factorial n)
(product identity 1 inc n))
(define (pi n)
(define (inc2 x)
(inc (inc x)))
(define (term n)
(/ (* n (inc2 n)) (* (inc n) (inc n))))
(* 4.0 (product term 2 inc2 n)))
;; ====================================
;; exercise 1.31 b
;;
(define (product-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* result (term a)))))
(iter a 1))
;; ====================================
;; exercise 1.35
;;
;; x = 1 + 1/x
;; x^2 - x - 1 = 0
;; (1 +- sqrt(5)) / 2
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
;; ====================================
;; exercise 1.37 a
(define (cont-frac n d k)
(define (recur i)
(if (= i k)
(/ (n k) (d k))
(/ (n i) (+ (d i) (recur (inc i))))))
(recur 1))
(define (golden-inverse k)
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
k))
;; (golden-inverse 1) => 1
;; (golden-inverse 2) => 0.5
;; (golden-inverse 3) => 0.6666666666666666
;; (golden-inverse 8) => 0.6176470588235294
;; (golden-inverse 100) => 0.6180339887498948
;; approx-order will calculate the needed order to get
;; 4 decimals precission
(define approx-order
(let ((real-golden-inverse (/ 2 (+ 1 (sqrt 5)))))
(define (recur k)
(let ((error (abs (- (golden-inverse k) real-golden-inverse))))
(if (< error 0.0001)
k
(recur (inc k)))))
(recur 1)))
;; approx-order = 10
;; ====================================
;; exercise 1.37 b
(define (cont-frac-iter n d k)
(define (dec i) (- i 1))
(define (iter i summand)
(if (= i 1)
(/ (n 1) (+ (d 1) summand))
(iter (dec i) (/ (n i) (+ (d i) summand)))))
(iter k 0))
;; ====================================
;; exercise 1.39
(define (tan-cf x k)
(- (cont-frac
(lambda (_) (- (* x x)))
(lambda (i) (- (* 2.0 i) 1))
k)))
;; ====================================
;; exercise 1.41
(define (double f)
(lambda (x) (f (f x))))
;; (((double (double double)) inc) 5) => 21
;; ====================================
;; exercise 1.42
(define (compose f g)
(lambda (x) (f (g x))))
;; ====================================
;; exercise 1.43
(define (repeated f n)
(if (= n 1)
f
(repeated (compose f f) (- n 1))))
No comments. Sign up or log in to comment 
;A little late, but here is what I got.
;I'm not sure what is wrong with my tan function though:
;1.3 Homework
;Problems: 1.29, 1.30, 1.31, 1.35, 1.39, 1.41, 1.42, 1.43
;1.29
(define (simposon-integral2 f a b n)
(define h
(/ (- b a) n))
(define (next x) (+ x (* 2 h)))
(* (/ h 3.0) (+ (f a)
(f b)
(* 4 (sum f (+ a h) next (- b h)))
(* 2 (sum f (+ a (* h 2)) next (- b (* h 2)))))))
(simposon-integral2 cube 0 1 100)
(simposon-integral2 cube 0 1 1000)
0.25
0.25
;1.30
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
;1.31
(define (product-rec term a next b)
(if (> a b)
1
(* (term a)
(product-rec term (next a) next b))))
(define (prodcut-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
; Factorial 1 to 10
(define (nothing x) (+ x 0))
(define (inc x) (+ x 1))
(product-rec nothing 1 inc 10)
(prodcut-iter nothing 1 inc 10)
; pi/4
(define (piBy4 n)
(define (nextPi x) (+ x 2))
(define (square x) (* x x))
;((product-rec square 3 nextPi (- n 1)))))
;(product-rec square 4 nextPi n))
;(* 2 (product-rec square 4 nextPi (- n 2)) n))
(/ (* 2 (product-rec square 4.0 nextPi (- n 2)) n)
(product-rec square 3.0 nextPi (- n 1))))
(piBy4 50)
> 3628800
> 3628800
> 0.7932910175598827
;1.35
; x^2 = X + 1
; x = 1 + 1/x
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
(fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0)
> 1.6180327868852458
;1.39
(define (cont-frac N D k)
(define (iter count currentValue)
(if (= 1 count)
(/ (N 1) currentValue)
(iter (- count 1)
(+ (D (- count 1)) (/ (N count) currentValue)))))
(iter k (/ (N k) (D k))))
(define (tan-cf x k)
(define (xsqaured k)
(if (= k 1.0)
x
(* x x)))
(cont-frac xsqaured (lambda (i) (+ 1 (* (- i 1) 2.0))) k))
(tan 1.0)
(tan-cf 3.14 10000)
(define (test k)
(+ 1 (* (- k 1) 2.0)))
> 1.5574077
> 0.9962602
; Something isn't right here....
;1.41
(define (inc x)
(+ x 1))
(define (double f)
(lambda (x) (f (f x))))
(((double (double double)) inc) 5)
> 21
;1.42
(define (square x) (* x x))
(define (inc x) (+ x 1))
(define (compose f g)
(lambda (i) (f (g i))))
((compose square inc) 6)
> 49
;1.43
(define (square x)
(* x x))
(define (repeated f n)
(define (repeated-rec count)
(if (= n count)
(lambda (i) (f i))
(lambda (i) (f ((repeated-rec (+ count 1)) i)))))
(repeated-rec 1))
((repeated square 2) 5)
> 625
Comments:
In 1.43, what is the point of repeated-rec? Why don't you just call repeated recursively? Also, I think you could replace (lambda (i) (f i)) by f
Really there isn't much reason for repated-rec other then I could assume n, it just made it a little easier for me to think about this way. Also you are just using "f" works. I'm clearly still getting use to Scheme's, syntax :) Thanks.
1-39 is almost there. You have simply got some signs mixed up. The (numerator, denominator) pairs should be (x, 1) (-x^2, 3) (-x^2, 5) .... You have made them (x, -1) (x^2, -3) (x^2, -5) .... Notice that the first term is the opposite sign to the others. In my solution I didn't bother trying to calculate the first term, just added it in at the end. (define (tan-cf x k)
(/ x
(+ 1
(cont-frac (lambda (i) (- 0 (* x x)))
(lambda (i) (+ (* 2 i) 1))
(- k 1)))))
;; x 1 x^2 -3 x^2 -5
Exercise 1.29
0.24999999999999992
0.2500000000000002 Exercise 1.35 (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0) 1.6180327868852458 Exercise 1.37 k needs to be 12 to be approx to 4 decimal places. Exercise 1.41 value returned is 21 ;; Exercise 1.29
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (cube n)
(* n n n))
(define (inc n)
(+ n 1))
(define (integral f a b n)
(define h
(/ (- b a) n))
(define (y f a k h)
(f (+ a (* k h))))
(define (term count)
(* (check count) (y f a count h)))
(define (check count)
(cond ((or (= count 0) (= count n)) 1)
((even? count) 2.0)
(else 4.0)))
(* (/ h 3.0) (sum term 0 inc n)))
;; Exercise 1.30
(define (sum term a next b)
(define (iter a result)
(if (> a b) 0
(+ result (iter (next a) (term (next a))))))
(iter a (term a)))
;; Exercise 1.31
;; a)
(define (product term a next b)
(if (> a b) 1
(* (term a) (product term (next a) next b))))
(define (inc n)
(+ n 1))
(define (prod-pi a b)
(define (pi-term a)
(define (numerator n)
(if (odd? n) (+ n 1.0)
(+ n 2.0)))
(define (denominator n)
(if (odd? n) (+ n 2.0)
(+ n 1.0)))
(/ (numerator a) (denominator a)))
(product pi-term a inc b))
;; b)
(define (product2 term a next b)
(define (iter a result)
(if (> a b ) result
(iter (next a) (* result (term a)))))
(iter a (term a)))
;;Exercise 1.37
;;a)
(define (cont-frac n d k)
(define (recur count)
(if (= count k)
(/ (n k) (d k))
(/ (n k) (+ (d k) (recur (+ 1 count))))))
(recur 1))
;;b)
(define (cont-frac n d k)
(define (iter count result)
(if (= count 1)
result
(iter (- count 1) (/ (n k) (+ (d k) result)))))
(iter k (/ (n k) (d k))))
;; Exercise 1.39
(define (tan-cf x k)
(cont-frac (lambda (i)
(if (= 1 i) x
(* x x)))
(lambda (i) (- (* 2 i) 1))
k))
;; Exercise 1.41
(define (double f)
(lambda (n) (f (f n))))
;; Exercise 1.42
(define (compose f1 f2)
(lambda (n)
(f1 (f2 n))))
(define (square n)
(* n n))
;; Exercise 1.43
(define (compose f1 f2)
(lambda (n)
(f1 (f2 n))))
(define (repeated f n)
(define (iter result count)
(if (= count 1) result
(iter (compose f result) (- n 1))))
(iter f n))
(define (square n)
(* n n))
Comments:
Did you check 1.31 b ? I think it has an error, I explain in the code: (iter a (term a))) ; probably should be (iter a 1) ; maybe the error was hidden by the fact that (term a) = 1 for factorial
In 1.43, what is the point of recurring over iter instead of over repeated? I think both ways generate an iterative process, and the later is a bit simpler. But maybe I'm missing something here. |
No comments. Sign up or log in to comment