연습문제 2.66

(define (look-up given-key set-of-records)
  (cons ((null? set-of-records?) #f)
        (else
         (let ((cur-entry (entry set-of-records))
           (let ((cur-key (key cur-entry)))
             (cond ((= cur-key given-key) cur-entry)
                   ((< cur-key given-key)
                    (look-up given-key
                             (left-branch set-of-records)))
                   ((> cur-key given-key)
                    (look-up given-key
                             (right-branch set-of-records))))))))))

연습문제 2.65

(define (union-set set1 set2)
  (let ((list1 (tree->list-1 set1)) (list2 (tree->list-1 set2)))
    (let ((list-union (union-list list1 list2)))
      (let ((union (list->tree list-union)))
        union))))

(define (intersection-set set1 set2)
  (let ((list1 (tree->list-1 set1)) (list2 (tree->list-1 set2)))
    (let ((list-intersection (intersection-list list1 list2)))
      (let ((intersection (list->tree list-intersection)))
        intersection))))

연습문제 2.64

a. partial-tree는 주어진 크기 n의 elts를 두개의 그룹으로 나눈다. 해당하는 크기는 n/2이다. 이를 재귀적으로 반복해서 우측 트리와 좌측 트리로 나누어 넣는다.
완성된 리스트는..
      5
    /  \
 1        9
  \     /\
   3     7  11

이다.

b. 개별 요소당 한번의 partial-tree를 거치므로, O(n)이 된다.

연습문제 2.63

a. 모두 동일한 결과를 낸다.
b. 자람 차수는 동일하다.

연습문제 2.62

(define (union-set set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          (else
             (let ((x1 (car set1)) (x2 (car set2)))
               (cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2))))
                     ((< x1 x2) (cons x1 (union-set (cdr set1) set2)))
                     (else (cons x2 (union-set set1 (cdr x2)))))))))

연습문제 2.61

(define (adjoin-set x set)
  (cond ((null? set) (cons x '()))
        ((< x (car set)) (cons x set))
        ((element-of-set? x set) set)
        (else
         (cons (car set) (adjoin-set x (cdr set))))))

연습문제 2.60

element-of-set? 은 변함이 없다.

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

adjoin-set의 경우 x가 set안에 있는지 더이상 검사하지 않아도 된다.

(define (adjoin-set x set)
  (cons x set))

union-set 역시 마찬가지로 두 set을 그냥 합치면 된다.

(define (union-set set1 set2)
  (append set1 set2))

intersection-set은 기존의 버전과 동일하다.

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

이를 보면 adjoin-set은 O(1)을 따르며 union-set은 O(n)을 따르게된다.
따라서 adjoin-set과 union-set을 많이 사용하는 프로그램에서 더 효율이 높아질 수 있게된다.

연습문제 2.59

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

연습문제 2.58

일단 패스~

연습문제 2.57

여러 마디의 덧셈식과 곱셈식을 표현하려면 일단 make-sum과 make-product를 변형해야한다.

(define (make-sum . a)
  (append (list '+) a))

(define (make-product . s)
  (append (list '*) s))

이제 준식에 맞춰서 sum?, product?는 이전과 동일하다.

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

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

이제 고르개를 바꾼다.

(define (length lst)
  (+ 0
     (cond ((null? lst) 0)
           ((pair? lst) (+ 1 (length (cdr lst))))
           (else 1))))

(define (augend s) (cadr s))

(define (addend s)
  (let ((sub_s (cddr s)))
    (cond ((> (length sub_s) 1) (cons '+ sub_s))
          (else (car sub_s)))))

(define (multiplicand p) (cadr p))

(define (multiplier p)
  (let ((sub_p (cddr p)))
    (cond ((> (length sub_p) 1) (cons '* sub_p))
          (else (car sub_p)))))

처럼 하면 된다.
이전 버전과는 달리.. 합치기 기능이 없어져서 답은 조금 산만하게 나온다.

> (deriv '(* x y (+ x 3)) 'x)
(+ (* (* y (+ x 3)) 1) (* (+ (* (+ x 3) 0) (* (+ 0 1) y)) x))

연습문제 2.56

(define (make-exponentiation base exponent)
  (cond ((=number? base 0) 0)
        ((=number? base 1) 0)
        ((=number? exponent 0) 1)
        ((=number? exponent 1) base)
        (else (list '** base exponent))))

(define (exponentiation? exp)
  (and (pair? exp) (eq? '** (car exp))))

(define (base exp)
  (cadr exp))

(define (exponent exp)
  (caddr exp))



(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))))
        ((exponentiation? exp)
         (make-product (make-product (exponent exp)
                                     (make-exponentiation (base exp)
                                                          (- (exponent exp) 1)))
                       (deriv (base exp) var)))
        (else
         error "UNKNOWN expression type -- DERIV" exp)))

연습문제 2.54

(define (equal? a b)
  (cond ((eq? a b) #t)
        ((eq? (car a) (car b))
         (equal? (cdr a) (cdr b)))
        (else #f)))

연습문제 2.55

''ab (간단하게 표현했다)는 다음과 같다

(quote (quote ab))

따라서 (car ''ab) 는

(car (quote (quote ab))) -> quote

가 된다.

연습문제 2.53

실제 실행기에서 실행해보자..

연습문제 2.52

이 문제는 건너뜀

연습문제 2.51

beside 유사버전

(define (below painter1 painter2)
  (let* ( (split-point (make-vect 0.0 0.5))
          (paint-up
            (transform-painter
              painter2
              (make-vect 0.0 0.0)
              (make-vect 1.0 0.0)
              split-point))
          (paint-down
            (transform-painter
              painter1
              split-point
              (make-vect 1.0 0.5)
              (make-vect 0.0 1.0))))
    (lambda (frame)
      (paint-up frame)
      (paint-down frame))))

돌리는 연산을 사용한 버전

<blockquote>(define (below-rot painter1 painter2)
  (rotate90 (beside
              (rotate270 painter1) (rotate270 painter2))))</blockquote>

연습문제 2.50

(define (flip-horiz painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)
                     (make-vect 1.0 1.0)
                     (make-vect 1.0 0.0)))

(define (rotate180 painter)
  (transform-painter painter
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 1.0)
                     (make-vect 0.0 0.0)))

(define (rotate270 painter)
  (transform-painter painter
                     (make-vect 0.0 1.0)
                     (make-vect 0.0 0.0)
                     (make-vect 1.0 0.0)))

연습문제 2.49

a와 b만 푼다.. (나머지는 너무 많다. )

A. 그림틀의 테두리..

(define outline-segments
  (list
    (make-segment
      (make-vect 0.0 0.0)
      (make-vect 0.0 1.0))
    (make-segment
      (make-vect 0.0 0.0)
      (make-vect 1.0 0.0))
    (make-segment
      (make-vect 1.0 0.0)
      (make-vect 1.0 1.0))
    (make-segment
      (make-vect 0.0 1.0)
      (make-vect 1.0 1.0))))

(define outline-painter (segments->painter outline-segments))

B. X표시

<blockquote> (define x-segments<br />   (list<br /><pre>    (make-segment<br />      (make-vect 1.0 0.0)<br />      (make-vect 0.0 1.0))<br />    (make-segment<br />      (make-vect 0.0 0.0)<br />      (make-vect 1.0 1.0))))<br /><br />(define x-painter (segments->painter x-segments))

연습문제 2.48

(define (make-segment vect1 vect2)
  (cons vect1 vect2))

(define (start-segment seg)
  (car seg))

(define (end-segment seg)
  (cdr seg))

연습문제 2.47

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

인 경우

(define (origin frame)
  (car frame))

(define (edge1 frame)
  (car (cdr frame)))

(define (edge2 frame)
  (car (cdr (cdr frame))))

이며

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

인 경우

(define (origin frame)
  (car frame))

(define (edge1 frame)
  (car (cdr frame)))

(define (edge2 frame)
  (car (cdr (cdr frame))))

연습문제 2.46

(define (make-vect x y)
  (cons x y))

(define (xcor-vect vect)
  (car vect))

(define (ycor-vect vect)
  (cdr vect))

(define (add-vect v1 v2)
  (make-vect (+ (xcor-vect v1) (xcor-vect v2))
             (+ (ycor-vect v1) (ycor-vect v2))))

(define (sub-vect v1 v2)
  (make-vect (- (xcor-vect v1) (xcor-vect v2))
             (- (ycor-vect v1) (ycor-vect v2))))

(define (scale-vect v n)
  (make-vect (* (xcor-vect v) n)
             (* (ycor-vect v) n)))

연습문제 2.45

(define (split pos1 pos2)
  (lambda (painter n)
    (if (= n 0)
        painter
        (let ((smaller ((split pos1 pos2 ) painter (- n 1))))
          (pos1 painter (pos2 smaller smaller))))))

연습문제 2.44

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (- n 1))))
        (below painter (beside smaller smaller)))))
 

연습문제 2.43

속도가 그렇게 느려지지는 않음...
워낙에 요즘 컴퓨터가 좋아서 그럴지도...

연습문제 2.42

기본적인 퀸의 위치는 row와 col으로 결정된다고 하자.

이를 pos라고 하고 이를 생성하는 함수를 구성한다.

(define (make-pos row col)
  (cons row col))

(define (position-row pos)
  (car pos))

(define (position-col pos)
  (cdr pos))

(define (position-equal? pos1 pos)
  (equal? pos1 pos2))

이제 empty-board, adjoin-position 을 정의한다.

(define (empty-board) '())

(define (adjoin-position row col positions)
  (append positions (make-pos row col)))

다음으로 safe?를 만든다. k번째 퀸이 나머지 다른 퀸에서 안전하려면 이전에 위치가 안전하다는 가정하에서 시작한다.
따라서 safe? k 는 safe? k-1 번째 놓여진 position에 비해 안전하면 된다. 즉 row, col 값이 모두 다르고 대각선상에 있지않아야한다.

... 이하는 다음에 계속