sicp 2.59

#lang racket
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)      
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))


;; 2.59
(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((element-of-set? (car set1) set2)      
         (cons (car set1)
               (union-set (cdr set1) (cdr set2))))
        (else (cons (car set1) (union-set (cdr set1) set2)))))

(union-set '(1 2 3 4) '(2 3 4))

sicp 2.58

#lang racket
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list a1 '+ a2))))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list m1 '* m2))))

(define (sum? x)
  (and (pair? x) (eq? (cadr x) '+)))

(define (addend s)
  (cond ((equal? (cddr s) '()) 0)
        (else (car s))))

(define (augend s)
  (cond ((equal? (length  (cddr s)) 1) (caddr s))
        (else (cddr s))))

(define (product? x)
  (and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p)
   (car p))

(define (multiplicand p)
  (cond ((equal? (length  (cddr p)) 1) (caddr p))
        (else (cddr p))))

(deriv ' (x + 3 * (x + y + 2)) 'x)
;;(deriv ' (x * (x * y)) 'x)
(deriv ' (x + x) 'x)
(deriv ' (x + x + y + 2) 'x)

(deriv (deriv (deriv ' (x * x * x) 'x) 'x) 'x)

sicp 2.57

#lang racket
(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp)
         (if (same-variable? exp var) 1 0))
        ((sum? exp)
         (make-sum (deriv (addend exp) var)
                   (deriv (augend exp) var)))
        ((product? exp)
         (make-sum
           (make-product (multiplier exp)
                         (deriv (multiplicand exp) var))
           (make-product (deriv (multiplier exp) var)
                         (multiplicand exp))))
        (else
         (error "unknown expression type -- DERIV" exp))))

(define (variable? x) (symbol? x))

(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (make-sum a1 a2)
  (cond ((=number? a1 0) a2)
        ((=number? a2 0) a1)
        ((and (number? a1) (number? a2)) (+ a1 a2))
        (else (list '+ a1 a2))))

(define (=number? exp num)
  (and (number? exp) (= exp num)))

(define (make-product m1 m2)
  (cond ((or (=number? m1 0) (=number? m2 0)) 0)
        ((=number? m1 1) m2)
        ((=number? m2 1) m1)
        ((and (number? m1) (number? m2)) (* m1 m2))
        (else (list '* m1 m2))))

(define (sum? x)
  (and (pair? x) (eq? (car x) '+)))

(define (addend s)
  (cond ((equal? (cdr s) '()) 0)
        (else (cadr s))))

(define (augend s)
  (cond ((equal? (cdr s) '()) 0)
        (else (cons (car s) (cddr s)))))

(define (product? x)
  (and (pair? x) (eq? (car x) '*)))

(define (multiplier p)
  (cond ((equal? (cdr p) '()) 1)
        (else  (cadr p))))

(define (multiplicand p)
  (cond ((equal? (length  (cddr p)) 1) (caddr p))
        (else (cons (car p) (cddr p)))))

(deriv '(+ (+ x 3) x) 'x)
(deriv '(+  (+ x x) (+ x x)) 'x)
(deriv '(+  (+ (+ x x) x) x) 'x)
(deriv '(+  x x x) 'x)
;;(deriv '(+  x x x (+ x 3)) 'x)
(deriv '(*  x x ) 'x)
(deriv '(*  x x x) 'x)
(deriv '(*  (* x y) x) 'x)
(deriv '(*  x y x) 'x)

(deriv '(* (* x y) (+ x 3)) 'x)
;;'(+ (* x y) (* y (+ x 3)))

(equal? (deriv '(* x y (+ x 3)) 'x) (deriv '(* (* x y) (+ x 3)) 'x))

[sicp] 1.17, 1.18

#lang scheme
(define (even? n)
  (= (remainder n 2) 0))

(define (double a )
   (double-iter a 2 0))

(define (double-iter a counter product)
  (if (= counter 0)
      product
      (double-iter a (- counter 1) (+ a product))))

(define (mod a div)
  (- (/ a div) (/ 1 div)))

;; 1.18
(define (fast-multi-iter a counter product result )
  (cond ((= counter 1) (+ product  result ) )
        (( even? counter) (fast-multi-iter a (/ counter 2)  (double product) result ))
        (else (fast-multi-iter a (mod counter 2) (double product) (+ result product ) ) )))
 
(define (* a b)
  (fast-multi-iter a b a 0 )
  )

 

 

 

;; 1.17
(define (fast-multi b n)
  (cond ((= n 0) 0)
        ((even? n) (double (fast-multi b (/ n 2))))
        (else (+ b (fast-multi b (- n 1))))))

 

ps. 1.18 을 답을 보니 나만 틀렸네 ㅡㅡ

잘못된 방법으로 풀었음 .

역시 난 ㅠㅠ

영어 어려워서 책 질렀음

[sicp] 1.16

;;; sicp 1.16
#lang scheme
(define (square x) (* x x))

(define (even? n)
  (= (remainder n 2) 0))

(define (fast-expt-iter b counter product)
  (if (= counter 0)
      product
     (if (even? counter)
         (fast-expt-iter b
                (/ counter 2)
                (* b  product product))
         (fast-expt-iter b
                (- counter 1)
                (* b product))
          )
         ))
(define (fast-expt b n)
 (fast-expt-iter b n 1))

(fast-expt 2 16)

 

이것도 들렸다 ㅠㅠ

[sicp] 1.13

Exercise 1.13.  Prove that Fib(n) is the closest integer to ⁿ/5, where = (1 + 5)/2. Hint: Let = (1 - 5)/2. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that Fib(n) = (ⁿ - ⁿ)/5.
0 1 1 2 3 5 8
fin n = 1  ((1+ 5)/2 - (1-5)/2 )/5 => 5/5 => 1
fin n = 2  (((1+ 5)/2)^2 - ((1-5)/2 )^2)/5
=> ( (1+ 5)/2 - (1-5)/2 )( (1+ 5)/2 + (1-5)/2 ) ) /5
=> 5/5 => 1

#lang scheme
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

(define A
 (/   (+ 1 (expt 5 0.5))
     2))

(define B
 (/   (- 1 (expt 5 0.5))
     2))

(define (fib2 n)
 (/ (- (expt A n)
    (expt B n))
   (expt 5 0.5)))

(fib2 1) = 1.0
(fib 1) = 1
(fib2 2) = 1.0
(fib 2) = 1
(fib2 3) = 2.0
(fib 3) = 2
...
(fib2 40) = 102334155.00000013
(fib 40) = 102334155
(fib2 50) = 12586269025.00002
(fib 50) = 12586269025
...
(fib2 60) = 1548008755920.003
(fib 60) =1548008755920
(fib2 70) = 190392490709135.44
(fib 70) = 190392490709135

(fib2 80) = 23416728348467744.0
(fib 80) = 23416728348467685

70까지는 거의 근접하고 1~ 3까지는 확실히 똑같다. 3 이후부터는 소수점이 많이 늘어난다.

[sicp] 1.12

Exercise 1.12.  The following pattern of numbers is called Pascal's triangle.

The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.³⁵ Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

#lang scheme
(define (pascal_triangle a b )
  (cond
       ((= a b) 1)
        ((= a 2) 1)
         ((= b 1) 1)
       (else (+ (pascal_triangle (- a 1) (- b 2))
               (pascal_triangle (- a 1) (- b 1))))))

--------------------------------------------------------------------------------

;;; sicp 1.12
#lang scheme
(define (pascal_triangle a b )
  (cond
       ((< a b) '틀렸음)
       ((= a b) 1)
         ((= b 1) 1)
       (else (+ (pascal_triangle (- a 1) (- b 1))
               (pascal_triangle (- a 1) b)))))

 

수정함

[sicp] 1.11

Exercise 1.11.  A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

- recursive process
#lang scheme

(define (f n)
  (cond ((= n 0) 0)
       ((= n 1) 1)
       ((= n 2) 2)
       (else (+ (f (- n 1))
               (* 2 (f (- n 2)))
               (* 3 (f (- n 3)))) ) ) )

- iterative process
#lang scheme

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

1.10

Exercise 1.10.  The following procedure computes a mathematical function called Ackermann's function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n. For example, (k n) computes 5n².

(A 1 10 ) 풀이

( A 1 10 )  = > 1024

( A 1 ( A 1 9) )  = 512

( A 1 ( A 1 (A 1 8 ) )  = 256

( A  1 ( A 1 ( A 1 (A 1 7 ) ) ) = 128

( A  1 ( A  1 ( A 1 ( A 1 (A 1 6 ) ) ) ) )

....

( A 1 .... ( * 2 1 ) )

(A 2 4 ) 풀이

( A 2 1 )  = > 1

( A 2 2 ) = >  4 -> 2^2

( A 2 3 ) = >  16 -> 2^(2^2)

( A 2 4 ) = >  65536 -> (2^(2^(2^2)))

1. f => 2n

(define (f n) (A 0 n)) 일때 A 함수를 따르면

x = 0 이므로 ( * 2 y )  이다.

답은 f(n) = 2n

2. g => 2^n

3. h => if n = 0 :  f(x) = 0

            if n = 1 :  f(x) = 2^1

            if n >= 2 : f(x) = 2^f(x-1)

 나오는 순서도는 생략 ㅡㅡ 너무 쓰기 힘듬 ...

[sicp] 1.9

1.9

첫번째 : iterative

a : counter

b : product

a가 1 감소할때마다 b는 1씩 증가해서 a가 0이 되면 b는 결과 출력

[code] #lang scheme (define ( inc a ) (- a -1)) (define (dec a) (- a 1)) (define (+ a b) (if (= a 0) b (+ (dec a) (inc b)))) (+ 4 5) [/code]
erlang 버젼
[code] -module(iterative). -export([inc/1,dec/1,plus/2]). inc(A)->A+1. dec(A)->A-1. plus(0,B) -> B; plus(A,B)-> plus(dec(A),inc(B)). [/code]
두번째 : recursive

전형적인 재귀
a가 1씩 감소할떄마다 재귀호출를 1번씩 해서 총 a가 감소만 만큼 재귀호출한 후에
a만큼 다시 더하는 방식

[code] #lang scheme (define ( inc a ) (- a -1)) (define (dec a) (- a 1)) (define (+ a b) (if (= a 0) b (inc (+ (dec a) b)))) (+ 4 5) [/code]