sicp exercise ch1 - andstudy/forge GitHub Wiki
parkpd
1 장
연습문제 1.3
(define (square x) (* x x))
(define (square-sum x y) (+ (square x) (square y)))
(define (prac1-3 a b c) (cond
((and (< a b) (< a c)) (square-sum b c))
((< b c) (square-sum a c))
(true (square-sum a b))))
(square-sum 3 4)
(prac1-3 3 2 1)
연습문제 1.7
여러가지 이유로 실행이 안 됨. 왜?
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (sqrt guess) x)) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 x))
(sqrt 9)
연습문제 1.29
작동하지 않음. 김명관님 답이 정확해 보이네요 :)
(define (simp-rule f a b)
(define (next-head-y i n)
(if (or (= i 0) (= i n))
1
(if (even? i)
2
4)))
(define (simp-rule-imp f a b i n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(if (> i n)
0
(+ (* (/ h 3) (* (next-head-y i n) (y i))))))
(simp-rule-imp f a b 0 100))
(define (cube x) (* x x x))
(simp-rule cube 0 1)
;1/75000000
연습문제 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))
연습문제 1.31
(define (trunc-x x) (quotient x 2))
(define (sum-a a)
(/ (* (trunc-x (+ a 2)) 2) (+ 1 (* (trunc-x (+ a 1)) 2))))
(define (mul-sum term a next b)
(if (> a b)
1
(* (term a)
(mul-sum term (next a) next b))))
(define (inc n) (+ n 1))
(define (prod a b)
(mul-sum sum-a a inc b))
(define (get-pi n)
(* 4 (prod 1 n)))
연습문제 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 term a next b)
(accumulate + 0 term 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 (cube x) (* x x x))
(integral cube 0 1 0.01)
#### 연습문제 1.33
(define (filtered-accumulate combiner predicate null-value term a next b)
(if (> a b)
null-value
(if (predicate a)
(combiner (term a)
(filtered-accumulate combiner predicate null-value term (next a) next b))
null-value)))
(define (sum term a next b)
(define (filter x) true)
(filtered-accumulate + filter 0 term 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 (cube x) (* x x x))
(integral cube 0 1 0.01)
(define (prime-sum a b)
(define (next x) (+ x 1))
(filtered-accumulate + prime? 0 square a next b))
(prime-sum 1 5)
연습문제 1.34
(define (f g)
(g 2))
(f square)
(f (lambda (z) (* z (+ z 1))))
(f f) -> (f 2) -> (2 2) 가 되어 해석을 하지 못한다
연습문제 1.37
(define (cont-frac n d k)
(define (cont-frac-imp n d i k)
(if (> i k)
0
(/ (n i) (+ (d i) (cont-frac-imp n d (+ i 1) k)))))
(cont-frac-imp n d 1 k))
(cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
100)
연습문제 1.38
(define (cont-frac n d k)
(define (cont-frac-imp n d i k)
(if (> i k)
0
(/ (n i) (+ (d i) (cont-frac-imp n d (+ i 1) k)))))
(cont-frac-imp n d 1 k))
(define (find-k pred)
(define (find i)
(if (pred i) i (find (+ i 1))))
(find 1))
(define (d i)
(cond ((= i 2) 2.0)
((= (remainder (- i 2) 3) 0)
(+ 2.0 (* (quotient (- i 2) 3) 2)))
(else 1.0)))
(define (base-of-natural-log? k)
(> 0.00001
(abs (- 2.718281828459
(+ 2
(cont-frac (lambda (i) 1.0) d k))))))
(find-k base-of-natural-log?)
;8
(+ 2 (cont-frac (lambda (i) 1.0) d 8))
;2.718279569892473
연습문제 1.39
(define (cont-frac n d k)
(define (cont-frac-imp n d i k)
(if (> i k)
0
(/ (n i) (+ (d i) (cont-frac-imp n d (+ i 1) k)))))
(cont-frac-imp n d 1 k))
(define (tan-cf x k)
(define (n i)
(if (= i 1)
x
(- (* x x))))
(cont-frac n (lambda (k) (- (* k 2.0) 1)) k))
(define (tan-cf1 x k)
(define (n i)
(if (= i 1)
x
(- (* x x))))
(define (d i)
(- (* i 2.0) 1))
(cont-frac n d k))
(tan 1)
;1.5574077246549023
(tan-cf 1 20)
;1.557407724654902
(tan-cf1 1 20)
;1.557407724654902
(tan 3.14)
;-0.001592654936407223
(tan-cf 3.14 20)
;-0.0015926549364072742
(tan-cf1 3.14 20)
;-0.0015926549364072742
연습문제 1.40
(define (cubic a b c)
(lambda (x)
(+ (* x x x) (* a x x) (* b x) c)))
연습문제 1.41
(define (double g)
(lambda (x) (g (g x))))
(define (inc x)
(+ x 1))
((double inc) 4)
(((double (double double)) inc) 5)
연습문제 1.42
(define (compose1 a b)
(lambda (x) (a (b x))))
연습문제 1.43
(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))
((repeated square 2) 5)
;625
(define (repeated-iter f n)
(define (iter result n)
(if (= n 1)
result
(iter (compose f result) (- n 1))))
(iter f n))
김명관
문제 1.11
-
번역본 1쇄에 오탈자가 있었네요.
-
원래 문제는
-
f(n)=f(n-1)+2f(n-2)+3f(n-3) 인데
-
f(n)=(n-1)+2f(n-2)+3f(n-3) 을 풀었습니다.
; recursive (define (prac1-11-recur n) (if (< n 3) n (+ (- n 1) (* 2 (prac1-11-recur (- n 2))) (* 3 (prac1-11-recur (- n 3)))))) ; iterative (define (prac1-11-iter n) (define (iter fn-1 fn-2 fn-3 n-1) (if (= n n-1) fn-1 (iter (+ n-1 (* 2 fn-2) (* 3 fn-3)) fn-1 fn-2 (+ n-1 1)))) (if (< n 3) n (iter 2 1 0 2)))
문제 1.12
(define (prac1-12 n m)
(if (or (= m n) (= m 1))
1
( + (prac1-12 (- n 1) (- m 1))
(prac1-12 (- n 1) m))))
문제 1.29
(define (inc n) (+ n 1))
(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 (prac1-29 f a b n)
(define h (/ (- b a) n))
(define (yk k)
(f (+ a (* k h))))
(define (num k)
(if (or (= 0 k) (= n k))
1
(if (= 0 (remainder k 2)) 2 4)))
(define (simpson-term k)
(* (num k) (yk k)))
(* (/ h 3)
(sum simpson-term 0 inc n)))
(integral cube 0 1 0.01)
(integral cube 0 1 0.001)
(prac1-29 cube 0 1 100)
(prac1-29 cube 0 1 1000)
ogmj
문제 1.11
;recursive
(define (pr1-11 n)
(cond ((< n 3) n)
(else (+ (pr1-11 (- n 1))
(* 2 (pr1-11 (- n 2)))
(* 3 (pr1-11 (- n 3))))
)
)
)
결과
> (pr1-11 3)
4
> (pr1-11 4)
11
> (pr1-11 10)
1892
;iterative
(define (pi1-11 n)
(cond ((< n 3) n)
(else(pi1-11-iter 2 1 0 (- n 2)))))
(define (pi1-11-iter x y z count)
(cond ((= count 0) x)
(else (pi1-11-iter (+ x (* 2 y)(* 3 z ) ) x y (- count 1)))
)
)
결과
> (pi1-11 3)
4
> (pi1-11 4)
11
> (pi1-11 10)
1892
이기영
1 장
연습문제 1.9
(define (plus a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(define (plus a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
(define (plus a b)
(+ a b))
(define (dec x)
(- x 1))
(define (inc x)
(+ x 1))
연습문제 1.10 (Ackermann funcion)
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
연습문제 1.11
;;되도는 프로시저
(define (sum n)
(if (< n 3)
n
(+ (sum(- n 1)) (* 2 (sum(- n 2))) (* 3 (sum(- n 3))))))
;;반복 프로시저
(define (sum n)
(if (< n 3)
n
(sum-iter 2 1 0 3 n)))
(define (sum-iter f1 f2 f3 cnt n)
(if (> cnt n)
f1
(sum-iter (+ f1 (* 2 f2) (* 3 f3))
f1
f2
(+ 1 cnt)
n)))
연습문제 1.12
(define (pas-tri row col)
(cond ((= col 1) 1)
((= col row) 1)
(else
(+ (pas-tri (- row 1) (- col 1))
(pas-tri (- row 1) col)))))
연습문제 1.16
(define (fast-expt b n)
(fast-expt-iter 1 b n))
(define (fast-expt-iter a b n)
(cond ((= n 0) a)
((even? n) (fast-expt-iter a (square b) (/ n 2)))
(else (fast-expt-iter (* a b) b (- n 1)))))
(define (square x)
(* x x))
연습문제 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
(+ (square p) (square q))
(+ (* 2 p q) (square q))
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(define (square x)
(* x x))
연습문제 1.22
(define (smallest-divisor n)
(find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (square x)
(* x x))
(define (divides? a b)
(= (remainder b a) 0))
(define (prime? n)
(= (smallest-divisor n) n))
(define (timed-prime-test n)
(start-prime-test n (current-milliseconds)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime n (- (current-milliseconds) start-time))
false))
(define (report-prime n elapsed-time)
(newline)
(display n)
(display " *** ")
(display elapsed-time))
(define (search-for-primes start-from)
(search-for-primes-iter start-from 3 ))
(define (search-for-primes-iter start-from count )
(if (> count 0)
(if (even? start-from)
(search-for-primes-iter (+ start-from 1) count )
(if (timed-prime-test start-from )
(search-for-primes-iter (+ start-from 2) (- count 1))
(search-for-primes-iter (+ start-from 2) count )))))
송정석
1 장
연습문제 1.3
(define (square x) (* x x))
(define (sum-square a b) (+ (square a) (square b)))
(define (ex1_3 v1 v2 v3)
(if (> v1 v2)
(sum-square v1 (if (> v2 v3) v2 v3))
(sum-square v2 (if (> v1 v3) v1 v3))
)
)
bt22d
1 장
연습문제 1.10
(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)
(A 2 4)
(A 3 3)
(define (f n) (A 0 n)) ; 2n
(define (g n) (A 1 n)) ; 2^n
(define (h n) (A 2 n)) ; ((2^2)^2)^2
(define (k n) (* 5 n n)) ; 5n^2
mastojun
1 장
연습문제 1.5
- 문제에서 의도한 데로 실행되기 위해선 DrScheme의 Language를 R5RS로 바꾸고 해야 합니다. Lazy Scheme으로 하면 아무런 문제 없이 실행되네요.
- 코드 생략 ^^
연습문제 1.7
(define (square x) (* x x))
(define (cube x) (* x x x))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
; on book
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (sqrt2 x) (sqrt-iter 1.0 x))
; 1.7
(define (sqrt-iter2 guess x)
(if (good-enough2? guess x)
guess
(sqrt-iter2 (improve guess x) x)))
; 이전의 guess와 수정된 guess를 비교
; sqrt-iter2에서 한번더 improve guess x를 호출 -> 효율 저하
; 여기서 값을 변경하고 sqrt-iter2에 그 값을 반영시키는 방법은 없을까?
(define (good-enough2? guess x)
(< (abs (- (improve guess x) guess)) 0.001))
(define (sqrt22 x) (sqrt-iter2 1.0 x))
(sqrt2 9)
(sqrt22 9) ; 같음
(sqrt2 0.0001)
(sqrt22 0.0001) ; 더 정확해짐
(sqrt2 1000000000000000000)
(sqrt22 1000000000000000000) ; 더 부정확
연습문제 1.10
-
노가다 노가다. (A 2 n)에 대한 결과는 Sequences알아내기를 참고 :$
-
(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) ; (A 0 (A 1 9)) ; (A 0 (A 0 (A 1 8)) ; (A 0 (A 0 (A 0 (A 1 7))) ; (A 0 (A 0 (A 0 (A 0 ... (A 0 ( A 0 1 ))... )))) ; (A 0 (A 0 (A 0 (A 0 ... (A 0 2) ... )))) ; (A 0 (A 0 (A 0 (A 0 2^6)))) ; (A 0 (A 0 (A 0 2^7))) ; (A 0 (A 0 2^8)) ; (A 0 2^9) ; 2^10 (A 2 4) ; (A 1 (A 2 3)) ; (A 1 (A 1 (A 2 2))) ; (A 1 (A 1 (A 1 (A 2 1)))) ; (A 1 (A 1 (A 1 2))) ; (A 1 (A 1 2^2)) ; (A 1 2^(2^2)) ; 2^(2^(2^2)) (A 3 3) ; (A 2 (A 3 2)) ; (A 2 (A 2 (A 3 1))) ; (A 2 (A 2 2)) ; (A 2 2^2) ; (A 2 4) ; 2^(2^(2^2)) (define (f n) (A 0 n)) ; 2n (define (g n) (A 1 n)) ; 2^n (define (h n) (A 2 n)) ; h(1) = 2, if n >= 2 : h(n) = 2^h(n-1) (define (k n) (* 5 n n)); 5n^2
연습문제 1.16
(define (square n) (* n n))
(define (fast-expt-iter b n)
(define (fast-expt-func b n product )
(cond ((<= n 0) product)
((even? n) (fast-expt-func b (- n 2) (* (square b) product)))
(else (fast-expt-func b (- n 1) (* b product)))))
(fast-expt-func b n 1 ))
연습문제 1.17
(define (double x) (* 2 x))
(define (halve x) (/ x 2))
(define (time-fast a b)
(cond ((= a 0 ) 0)
((even? a) (double (time-fast (halve a) b)))
(else (+ b (time-fast (- a 1) b)))))
연습문제 1.19
T = (a, b)
Tpq = (bq + aq + ap, bp + aq)
(Tpq)^2 = Tp'q' = ((bp + aq)q + (bq + aq + ap)(q+p), (bp+aq)p + (bq+aq+ap)q)
= (bpq + aq^2 + bq^2 + bqp + aq^2 + aqp + apq + ap^2,
bp^2 + aqp + bq^2 + aq^2 + apq )
= (b(2pq + q^2) + a(2pq+q^2) + a(q^2+p^2),
b(q^2+p^2) + a(2qp+q^2))
= (bq' + aq' + ap', bp' + aq')
∴ q' = 2pq + q^2
p' = q^2 + p^2
연습문제 1.22
-
Root(10)배 정도로 증가하나, 그냥 Run하면 실행 속도를 보장받지 못한다 =_=
-
Language를 Module로 수정하고 아래와 같이 코드를 작성한후 Debug로 실행 하면 약 3배씩 증가되는 모습을 확인할 수 있다.
-
실행속도를 좀더 느리게 하기 위해서 Choose Language에서 Show Details을 클릭 후 Dynamic Properties에서 Debugging and profiling을 선택.
#lang scheme ;69p (define (timed-prime-test n) (newline) (display n) (start-prime-test n (current-milliseconds))) (define (start-prime-test n start-time) (if (prime? n) (report-prime (- (current-milliseconds) start-time)) (newline))) (define (report-prime elapsed-time) (display " *** ") (display elapsed-time)) ; 64p (define (smallest-divisor n) (find-divisor n 2)) (define (square x) (* x x)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (divides? a b) (= (remainder b a) 0)) (define (prime? n) (= n (smallest-divisor n))) ; search-for-primes (define (search-for-primes n a) (define (search-for-primes-func n a count) (cond ((= a count) (newline)) ((prime? n) (and (timed-prime-test n) (search-for-primes-func (+ n 1) a (+ count 1)))) (else (search-for-primes-func (+ n 1) a count)))) (search-for-primes-func n a 0)) (search-for-primes 1000000 3) (search-for-primes 10000000 3) (search-for-primes 100000000 3) -
실행결과
Welcome to DrScheme, version 4.1.4 [3m]. Language: Module custom; memory limit: 128 megabytes. 1000003 *** 31 1000033 *** 32 1000037 *** 16 10000019 *** 94 10000079 *** 94 10000103 *** 93 100000007 *** 266 100000037 *** 282 100000039 *** 281
연습문제 1.31
#lang scheme
(define (product term a next b)
(cond ((> a b) 1)
(else (* (term a) (product term (next a) next b)))))
(define (term x)
(cond ((even? x) (/ x (+ x 1)))
(else (/ (+ x 1) x))))
(define (next x) (+ x 1))
(define (product-iter term a next b)
(define (iter a result)
(cond ((> a b) result)
(else (iter (next a) (* result (term a))))))
(iter a 1))
(define (pi x)
(* 4 (product term 2 next (+ 1 x))))
(define (pi-iter x)
(* 4 (product-iter term 2 next (+ 1 x))))
연습문제 1.35
#lang scheme
; Φ² = Φ + 1
; Φ = 1 + 1/Φ
; Φ -> x
; 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 (y) (+ 1 (/ 1 y))) 1.0)
연습문제 1.36
-
average damping을 한것이 더 빠르게 값을 구한다.
#lang scheme (define tolerance 0.00001) (define (average x y ) (/ (+ x y) 2)) (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 (and (display next) (newline) (try next))))) (try first-guess)) (fixed-point (lambda (y) (/ (log 1000) (log y))) 2.0) (newline) (fixed-point (lambda (y) (average y (/ (log 1000) (log y)))) 2.0) -
실행결과
Welcome to DrScheme, version 4.1.4 [3m]. Language: Module; memory limit: 128 megabytes. 9.965784284662087 3.004472209841214 6.279195757507157 3.759850702401539 5.215843784925895 4.182207192401397 4.8277650983445906 4.387593384662677 4.671250085763899 4.481403616895052 4.6053657460929 4.5230849678718865 4.577114682047341 4.541382480151454 4.564903245230833 4.549372679303342 4.559606491913287 4.552853875788271 4.557305529748263 4.554369064436181 4.556305311532999 4.555028263573554 4.555870396702851 4.555315001192079 4.5556812635433275 4.555439715736846 4.555599009998291 4.555493957531389 4.555563237292884 4.555517548417651 4.555547679306398 4.555527808516254 4.555540912917957 4.555532270803653 5.9828921423310435 4.922168721308343 4.628224318195455 4.568346513136242 4.5577305909237005 4.555909809045131 4.555599411610624 4.5555465521473675 4.555537551999825
연습문제 1.37
#lang scheme
; 되도는 프로세스
(define (cont-frac Ni Di k)
(define (func i)
(cond ((>= i k) (/ (Ni i) (Di i)))
(else (/ (Ni i) (+ (Di i) (func (+ i 1)))))))
(func 1))
; 반복하는 프로세스
(define (cont-frac-iter Ni Di k)
(define (func result k)
(cond ((= k 0) result)
(else (func (/ (Ni k) (+ (Di k) result)) (- k 1)))))
(func 0 k))
연습문제 1.38
#lang scheme
(define (cont-frac-iter Ni Di k)
(define (func result k)
(cond ((= k 0) result)
(else (func (/ (Ni k) (+ (Di k) result)) (- k 1)))))
(func 0 k))
(define (find-e k)
(+ 2 (cont-frac-iter (lambda (i) 1.0)
(lambda (i)
(cond ((= (remainder (+ i 1) 3) 0)
(* (/ (+ i 1) 3) 2))
(else 1))) k)))
연습문제 1.44
#lang scheme
(define (compose fun1 fun2)
(lambda (x) (fun1 (fun2 x))))
(define (repeated infunc k)
(if (= 1 k) infunc
(compose infunc (repeated infunc (- k 1)))))
(define dx 0.00001)
(define (smoothing fun)
(lambda (x)
(/ (+ (fun (- x dx)) (fun x) (fun (+ x dx))) 3)))
(define (smoothing-repeat fun n)
(repeated (smoothing fun) n))