;; file: 1_01.rkt

10
;;=> 10
 
(+ 5 3 4)
;;=> 12
 
(- 9 1)
;;=> 8
 
(/ 6 2)
;;=> 3
 
(+ (* 2 4) (- 4 6))
;;=> 6


;; ===========================================

(define a 3)
(define b (+ a 1))

(+ a b (* a b))
;;=> 19
 
(= a b)
;;=> #f
 
(if (and (> b a) (< b (* a b)))
    b
    a)
;;=> 4
 

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
;;=> 16

(+ 2 (if (> b a)
         b
         a))
;;=> 6

(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1))
;;=> 16

1_02

$$\frac{5 + 4 + (2 - (3 - (6 + 4/5)))}{3(6 - 2)(2 - 7)}$$

;; file: 1_02.rkt

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7)))
;;=> -37/150

1_03

;; file: 1_03.rkt

(#%require rackunit)
(#%require threading)
(#%require "../allcode/helper/my-util.rkt")

;; a, b, c 를 인자로 받고 가장 큰 두 수의 제곱의 합
;; 1.1.4에 나온 sum-of-squares 사용.

(define (square x)
  (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (ex1-03 a b c)
  (cond ((and (< a b) (< a c))
         (sum-of-squares b c))
        ((< b c)
         (sum-of-squares a c))
        (else
         (sum-of-squares a b))))
  
(check-equal? (ex1-03 2 10 3) 109)


;; ======================================================================================
;; 번외. sequcne(list)와 고차함수를(filter/sort/take)  이용한 방법.

(define (filter pred? sequence)
  (cond ((null? sequence) '())
        ((pred? (first sequence))
         (cons (first sequence) (filter pred? (rest sequence))))
        (else
         (filter pred? (rest sequence)))))

(define (sort less-than? lst)
  (if (or (null? lst) (null? (rest lst)))
      lst
      (let* ((pivot (first lst))
             (rest (rest lst))
             (smaller (filter (lambda (x) (less-than? x pivot)) rest))
             (greater-equal (filter (lambda (x) (not (less-than? x pivot))) rest)))
        (append (sort less-than? smaller)
                (cons pivot (sort less-than? greater-equal))))))

(define (take n sequence)
  (cond ((<= n 0) '())
        ((null? sequence) '())
        (else (cons (first sequence)
                    (take (- n 1) (rest sequence))))))

(define (largest-squares n xs)
  (~>> xs
       (sort >)
       (take n)
       (map (lambda (x) (* x x)))
       (apply +)))


(check-equal? (largest-squares 2 '(2 10 3)) 109)

1_04

;; file: 1_04.rkt

(define (a-plus-abs-b a b)
  ((if (> b 0)
       +
       -)
   a b))


(a-plus-abs-b 2 7)
;;=> 9

(a-plus-abs-b 2 -7)
;;=> 9


(a-plus-abs-b -2 7)
;;=> 5

(a-plus-abs-b -2 -7)
;;=> 5

1_05

;; file: 1_05.rkt

(define (p)
  (p))
(define (test x y)
  (if (= x 0)
      0
      y))

(test 0 (p))
;;=> 0

;; #lang sicp 라면 y로 들어온 (p)가 무한히 호출됨.
;; #lang lazy 라면 y를 평가하지 않아 0이 반환.
;; #lang lazy는 엄밀히 말하면 Lazy Evaluation인데 normal-order evaluation에 캐쉬를 단거라 생각하면됨.

1_06

;; file: 1_06.rkt
(#%require threading)

;; 1.1.7 연습: 뉴튼 법으로 제곱근 찾기

(define (square x)
  (* x x))

#;(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)
  (~> (square guess)
      (- x)
      (abs)
      (< 0.001)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

;; ref: https://docs.racket-lang.org/reference/if.html#%28form._%28%28quote._~23~25kernel%29._if%29%29
;;
;; (if test-expr
;;     then-expr
;;     else-expr)
;; 
;; if는 Special form으로 predicate를 수행후 then이나 else를 수행한다.
;;
;; 하지만 new-if는 함수인데, Applicative-Order evaluation에서의 함수는 인자를 다 평가시켜버려서,
;; (sqrt-iter (improve guess x) x) 도 계속 실행시켜버려 메모리가 부족해져버린다.

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

;; #lang sicp에서는 Applicative-Order Evaluation이기에
(sqrt 9)
;;!> . Interactions disabled; out of memory

;; #lang lazy에서는 Lazy Evaluation이기에
(sqrt 9)
;;=> 3.00009155413138

1_07

;; file: 1_07.rkt
(#%require threading)
(#%require (prefix racket: racket))
(#%require rackunit)

;; 1.1.7 연습: 뉴튼 법으로 제곱근 찾기

(define (square x)
  (* x x))

#;(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)
    (~> (square guess)
        (- x)
        (abs)
        (< 0.001)))

(define (sqrt x)
  (sqrt-iter 1.0 x))


;; ========================================
;; 중요한거. 번역판을 읽으면 이 문제를 풀기 어려워진다.
;; 원문을 읽어야 이 문제를 보다 풀기가 쉬워진다.
;;
;; An alternative strategy for implementing good-enough? is to watch how guess changes from one iteration to the next
;; and to stop when the change is a very small fraction of the guess.
;; 반복할 때마다 `guess`의 **변화량**를 살펴보고,
;; `guess`에 **변화량**이 **아주 작은** 비율이 되었을 때 멈추는 것이다.
(define DECIMAL-EPSILON
  (let loop ([e 1.0])
    (if (= (+ 1.0 e) 1.0)
        (* 2 e)
        (loop (/ e 2)))))

(define VERY-SMALL-RADIO DECIMAL-EPSILON)
;; (define VERY-SMALL-RADIO 0.00000000001)

VERY-SMALL-RADIO
;;=> 2.220446049250313e-16

(define (good-enough? guess next-guess)
  (let ((diff (- guess next-guess)))
    (~> (/ diff next-guess)
        (abs)
        (< VERY-SMALL-RADIO))))

(define (sqrt-iter guess x)
  (let ((next-guess (improve guess x)))
    (if (good-enough? guess next-guess)
        guess
        (sqrt-iter next-guess x))))

;; 아주 큰 수의 제곱근을 잘 구하는가?
;; 아주 작은 수 의 제곱근을 잘 구하는가?
(define COMPARE-EPSILON 0.00000001)
(check-= (sqrt 0.00000000123456) (racket:sqrt 0.00000000123456) COMPARE-EPSILON)
(check-= (sqrt 123456789012345) (racket:sqrt 123456789012345) COMPARE-EPSILON)


;; ref: https://sicp-solutions.net/post/sicp-solution-exercise-1-7/

1_08

$$ \text{목표: } y = \sqrt[3]{x} $$

$$ \text{⇒ 양변을 세제곱: } y^3 = x $$

$$ \text{⇒ 함수로 표현: } f(y) = y^3 - x $$

$$ \text{⇒ 도함수: } f'(y) = 3y^2 $$

$$ \text{⇒ 뉴튼 방법 일반식: } y_{n+1} = y_n - \frac{f(y_n)}{f'(y_n)} $$

$$ \text{⇒ 대입: } y_{n+1} = y_n - \frac{y_n^3 - x}{3y_n^2} $$

$$ = y_n - \frac{1}{3} \left( y_n - \frac{x}{y_n^2} \right) $$

$$ = \frac{2y_n + \frac{x}{y_n^2}}{3} $$

$$ \therefore \boxed{ y_{n+1} = \frac{x/y_n^2 + 2y_n}{3} } $$

;; file: 1_08.rkt
(#%require threading)
(#%require rackunit)

;; imporve 가 바뀌고 나머지는sqrt를 구할때와 거의 비슷한 흐름으로 흘러간다.
(define (improve guess x)
  "( x/y^2 + 2y ) / 3"
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

(define VERY-SMALL-RADIO 0.00000000001)

(define (good-enough? guess next-guess)
  (let ((diff (- guess next-guess)))
    (~> (/ diff next-guess)
        (abs)
        (< VERY-SMALL-RADIO))))


(define (cube-root-iter guess x)
  (let ((next-guess (improve guess x)))
    (if (good-enough? guess next-guess)
        guess
        (cube-root-iter next-guess x))))

(define (cube-root x)
  (cube-root-iter 1.0 x))

(define (cube x)
  (* x x x))

(define COMPARE-EPSILON 0.00000001)
(check-= 12345 (cube (cube-root 12345)) COMPARE-EPSILON)

1_09

;; file: 1_09.rkt
(#%require (prefix trace: racket/trace))

(define (x+ a b)
  (if (= a 0)
      b
      (inc (x+ (dec a) b))))

;; (x+ 2 1)
;; (inc (x+ 1 1))
;; (inc (inc (x+ 0 1)))
;; (inc (inc 1))
;; (inc 2)
;;=> 3

(define (y+ a b)
  (if (= a 0)
      b
      (y+ (dec a) (inc b))))

;; (y+ 2 1)
;; (y+ 1 2))
;; (y+ 0 3)
;;=> 3

(trace:trace x+)
(trace:trace y+)

(display "x+ ==============================\n")
(x+ 2 1)
;;>> >{x+ 2 1}
;;>> > {x+ 1 1}
;;>> > >{x+ 0 1}
;;>> < <1
;;>> < 2
;;>> <3
;;=> 3
(display "y+ ==============================\n")
(y+ 2 1)
;;>> >{y+ 2 1}
;;>> >{y+ 1 2}
;;>> >{y+ 0 3}
;;>> <3
;;=> 3

1_10

;; file: 1_10.rkt
(#%require (prefix trace: racket/trace))

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

(A 1 10)
;;=> 1024
(A 2 4)
;;=> 65536
(A 3 3)
;;=> 65536
(A 4 2)
;;=> 4


(define (f n) (A 0 n))
;; A(0, y) = 2y
;; f(n) = 2n

(define (g n) (A 1 n))
;; A(1, n-0)
;; = 2 * A(1, n-1)
;; = 2 * 2 * A(1, n-2)
;; = 2 * 2 * ... * A(1, n-(n- 1))
;; = 2 * 2 * ... * 2
;; g(n) = 2^n

(define (h n) (A 2 n))
;; 2^2^2 or 2^h(n-1)
;; A(2, n - 0)
;; = A(1, A(2, n-1))
;; = A(1, A(1, A(2, n-2))
;; = A(1, A(1, A(1, ... A(1, A(2, n-(n-1))))
;; h(n) = 2^2^2....2 (2의 갯수는 n개)
;; h(n) = pow(2, h(n-1))

(define (k n) (* 5 n n))
;; k(n) = 5n^2


;; Primitive Recursive Function = 반복 횟수가 미리 정해져 있어서 for문 같은 단순 반복으로 구현 가능 (factorial같은거)
;; Ackermann은 'for' 문 같은 구조로는 표현할 수 없는 함수도 있다는걸 보여주기 위해 Ackermann함수를 만듬.
;; 재귀 깊이가 입력값에 따라 아주 빠르게 늘어나서, 고정된 반복 횟수로 미리 제한하는 'for'문으로는 표현하기 힘듬.
;;
;; ref:
;;   - https://en.wikipedia.org/wiki/Ackermann_function
;;   - https://plato.stanford.edu/Entries/recursive-functions/ackermann-peter.html
;;   - https://sites.google.com/site/pointlesslargenumberstuff/home/2/ackermann

;; Ackermann original function
(define (φ x y z)
  ;; φ(x, y, 0) = x + y
  ;; φ(x, 0, z) = α(x, z-1)
  ;; φ(x, y, z) = φ(x, φ(x, y-1, z) z-1)
  (cond ((= z 0) (+ x y))
        ((= y 0) (α x (- z 1)))
        (else    (φ x (φ x (- y 1) z) (- z 1)))))

(define (α x y)
  ;; α(x, 0) = 0
  ;; α(x, 1) = 1
  ;; α(x, y) = x
  (cond ((= y 0) 0)
        ((= y 1) 1)
        (else    x)))

;; Ackermann-Peter function
(define (C m n)
  ;; C(0, n) = n+1
  ;; C(m, 0) = C(m-1, 1)
  ;; C(m, n) = C(m-1, C(m, n-1))
  (cond ((= m 0) (+ n 1))
        ((= n 0) (C (- m 1) 1))
        (else    (C (- m 1) (C m (- n 1))))))

(trace:trace φ)
(trace:trace C)
(φ 1 2 3)
(C 2 1)

1_11

;; file: 1_11.rkt
(#%require (prefix racket: racket))
(#%require rackunit)

;; n <  3 : f(n) = n                        
;; n >= 3 : f(n) = f(n-1) + 2f(n-2) + 3f(n-3)   

(define (f-recur n)
  (cond ((< n 3) n)
        (else    (+ (f-recur (- n 1))
                    (* 2 (f-recur (- n 2)))
                    (* 3 (f-recur (- n 3)))))))



;;      |  p1    |   p2    |   p3   |
;; f(n) = f(n-1) + 2f(n-2) + 3f(n-3)
;; ...
;; f(4) = f(3) + 2f(2) + 3f(1) = (2 + 2*1 + 3*0) + 2*2 + 3*1 = 11
;; f(3) = f(2) + 2f(1) + 3f(0) =  2              + 2*1 + 3*0 = 4
;; f(2) = 2
;; f(1) = 1
;; f(0) = 0

(define (iter curr-n target-n fn-1 fn-2 fn-3)
  (let ((next-fn-1 (+ fn-1 (* 2 fn-2) (* 3 fn-3)))
        (next-fn-2 fn-1)
        (next-fn-3 fn-2))
    (if (= curr-n target-n)
        next-fn-1
        (iter (inc curr-n) target-n next-fn-1 next-fn-2 next-fn-3))))

(define (f-iter n)
  (if (< n 3)
      n
      (iter 3 n 2 1 0)))

(racket:for ([i 20])
            (check-eq? (f-recur i)(f-iter i)))

1_12

;; file: 1_12.rkt
(#%require (prefix racket: racket))

;; 파스칼 삼각형

(define (P x y)
  (cond ((zero? x) 1)
        ((= x y)   1)
        (else      (+ (P (- x 1) y)
                      (P (- x 1) (- y 1))))))


(racket:for ([y (racket:in-inclusive-range 0 5)])
            (display y)
            (display ": ")
            (racket:for ([x (racket:in-inclusive-range 0 y)])
                        (display (P x y))
                        (display " "))
            (newline))
;;>> 0: 1 
;;>> 1: 1 1 
;;>> 2: 1 2 1 
;;>> 3: 1 2 4 1 
;;>> 4: 1 2 4 8 1 
;;>> 5: 1 2 4 8 16 1

1_13

;; file: 1_13.rkt

(#%require (prefix racket: racket))
(#%require threading)
(#%require rackunit)

;; ==============================================================
;; - 특성방정식(Characteristic equation)
;;   - https://en.wikipedia.org/wiki/Characteristic_equation_(calculus)
;;   - 선형 점화식의 일반해를 구하기 위해 도입하는 보조적인 다항방정식
;;     - 즉, 쉽게 구할 수 있는걸로 바꿔 계산하자임.
;;   - 제약조건
;;     - 선형(linear)
;;       - 곱하기, 더하기만 있음.(항들 사이에 곱하거나 제곱하지 않음)
;;       - 안되는 경우: F(n)=F(n−1)*F(n−2) (항 들 사이에 곱했음)
;;     - 상수 계수(with constant coefficients)
;;       - 계수들이 모두 상수여야 함 (즉, n에 따라 변하면 안 됨)
;;       - 안되는 경우: F(n)=n*F(n−1)+F(n−2) (n에 따라 변함)
;;     - 동차(homogeneous)
;;       - 오른쪽에 독립적인 항이 없음
;;       - 안되는 경우: F(n)=F(n−1)+F(n−2)+1 (오른쪽에 상수, n, 2^n, +5 같은 추가적인 항이 붙어 있으면 비동차)
;; - 근의 공식(quadratic equation)
;;   - https://en.wikipedia.org/wiki/Quadratic_equation
;; - (1+√5)/2
;;   - 황금비(golden ratio): https://en.wikipedia.org/wiki/Golden_ratio
;; - 비넷공식(binet formula)
;;   - https://en.wikipedia.org/wiki/Fibonacci_sequence#Binet's_formula
;; - 귀납법(induction)
;;   - https://en.wikipedia.org/wiki/Mathematical_induction
;;   - 歸納(돌아갈 귀, 들일 납)
;;   - 개별적인 사실들로부터 일반적인 결론을 이끌어내는  
;;   - 기저 사례(Base Case): 증명하고자 하는 명제가 특정 초기 값에 대해 참임을 보이는 단계
;;   - 귀납 단계(Induction Step): 특정 수 n에 대해 명제가 참이라고 가정하고 (귀납 가설), 이를 이용하여 n+1에 대해서도 명제가 참임을 증명.


;; ==============================================================
;; 1. Fib(n)이 (φ^n)/√5에 가까운 정수임을 증명해라. (φ = (1+√5)/2, ψ = (1−√5)/2)
;;
;; # 1.1: 일반적인 접근법
;;
;; ## Fib는 특성방정식을 만족함.(선형/상수계수/동차를 만족함)
;; F(n) = F(n−1) + F(n−2)
;;
;; Fib(n) = x^n 이라 바꿔 계산하면.
;; x^n           = x^(n-1)         + x^(n-2)
;; x^n / x^(n-2) = x^(n-1)/x^(n-2) + x^(n-2)/x^(n-2)
;;
;; x^2         = x + 1
;; x^2 - x - 1 = 0
;;
;; 근의 공식으로 풀면
;; x = (1+√5)/2 = φ
;; x = (1-√5)/2 = ψ
;;
;;
;; ## Binet공식: F(n)= (φ^n - ψ^n)/√5
;; 앞서구한 해 φ와 ψ로 F(n)을 나타내면
;; F(n)     = Aφ^n + Bψ^n
;; F(0) = 0 = A + B       | 즉, A = -B
;; F(1) = 1 = Aφ + Bψ
;;          = Aφ - Aψ
;;          = A(φ - ψ)
;;
;; A =  1/(φ - ψ)
;; B = -1/(φ - ψ)
;;
;; φ - ψ = (1+√5)/2 - (1-√5)/2
;;       = 2√5/2
;;       = √5
;;
;; A =  1/√5
;; B = -1/√5
;;
;; F(n) = Aφ^n     + Bψ^n
;;      = 1/√5*φ^n - 1/√5*ψ^n
;;      = (φ^n - ψ^n)/√5
;;
;;
;; # 1.2: G(n)을 도입한 다른 접근법
;;
;; φ + ψ = 1
;; φ - ψ = √5
;; φ * ψ = -1
;; 
;; F(n+2)            = (φ+ψ)*F(n+1) - (φ*ψ)*F(n)
;; F(n+2) - φ*F(n+1) = ψ*(F(n+1) - φ*F(n))
;;
;;
;; ## G(n) 정의
;;
;; G(n  ) = F(n+1) - φ*F(n)
;; G(n+1) = ψ*G(n)
;; G(0)   = F(1)   - φ*F(0)
;;        = 1      - φ*0
;;        = 1
;;        = ψ^0
;; G(1)   = ψ*G(0)
;;        = ψ^1
;; G(n)   = ψ^n
;;        = F(n+1) - φ*F(n)
;;
;; ## 역전개하여 F(n+1) 유도
;; F(n+1) - φ*F(n) = ψ^n
;;
;; F(n+1) = φ*F(n)                             + ψ^n
;;        = φ(φ*F(n-1)             + ψ^(n-1))  + ψ^n
;;        = φ^2*F(n-1)                         + ψ^n + φ*ψ^(n-1)
;;        = φ^3*F(n-2)                         + ψ^n + φ*ψ^(n-1) + φ*ψ^(n-2)
;;        = ...
;;        = φ^(n+1)*F(0)                       + sum(k=0~n, φ^(n-k)*ψ^k)
;;        = φ^(n+1)*0                          + sum(k=0~n, φ^(n-k)*ψ^k)
;;        = sum(k=0~n, φ^(n-k)*ψ^k)
;;        = φ^n * sum(k=0~n, (ψ/φ)^k)                                |  sum(k=0~n, r^k) = (1-r^(n+1)) / (1-r)
;;        = φ^n * (1-(ψ/φ)^(n+1))            / (1-(ψ/φ))
;;        = φ^n * (1-(ψ/φ)^(n+1)) * φ^(n+1)  / (1-(ψ/φ)) * φ^(n+1)
;;        = φ^n * (φ^(n+1) - ψ^(n+1))        / (φ^(n+1) - (ψ * φ^n))
;;        = (φ^(n+1) - ψ^(n+1)) / (φ - ψ)
;;        = (φ^(n+1) - ψ^(n+1)) / √5
;;
;; 따라서
;; F(n)   = (φ^n - ψ^n) / √5
;;
;;
;; ## 1.3: Fib(n)이 (φ^n)/√5에 가까운 정수임을 증명.
;;
;; ψ = (1-√5)/2
;;   = −0.6180339887...
;; |ψ^0|/√5 = 0.447....  | 1/2 보다 작음.
;; |ψ^1|/√5 = 0.276....
;; ...
;; |ψ^n|/√5 = 0.000....  | 0으로 수렴
;; |ψ^n|/√5 = 1/2보다 작고 0으로 수렴.
;;
;; F(n)  = (φ^n     -  ψ^n)/√5
;;       = (φ^n)/√5 - (ψ^n)/√5
;;      ~= (φ^n)/√5            | (ψ^n)/√5 은 0으로 수렴함으로.
;;      ~= (φ^n)/√5            | 따라서 F(n)은 (φ^n)/√5에 가까운 정수.
;;
;; 더 나가자면 |ψ^n|/√5 는 항상 1/2보다 작고 0으로 수렴하므로,
;; 오차는 round 함수의 오차 허용 한계인 0.5보다 항상 작다.
;; 따라서
;;
;; F(n) = round((φ^n)/√5)
;;

;; ==============================================================
;; 2. Fib의 정의로 Fib(n) = (φ^n – ψ^n)/√5 임을 induction으로 밝혀라
;;
;; ## 기저 사례(Base case)
;;
;; n = 0 일때 성립
;; (φ^0 – ψ^0)/√5 = (1 - 1)/√5
;;                = 0
;;
;; n = 1 일때 성립
;; (φ^1 – ψ^1)/√5 = (φ – ψ)/√5
;;                = ((1+√5)/2) - (1-√5)/2) /√5
;;                = (√5/2 + √5/2)/√5
;;                = 1
;;
;; ## 귀납단계(Induction Step)
;;
;; Fib(n  ) = (φ^(n-0) – ψ^(n-0))/√5
;; Fib(n-1) = (φ^(n-1) – ψ^(n-1))/√5
;; Fib(n+1) = Fib(n)         + Fib(n-1)
;;          = (φ^n – ψ^n)/√5 + (φ^(n-1) – ψ^(n-1))/√5
;;          = (φ^n + φ^(n-1)) – (ψ^n + ψ^(n-1)) /√5
;;
;; φ   =  (1+√5)/2
;; φ^2 =  (1 + 2√5 + 5)/4
;;     =  (6 + 2√5)/4
;;     = 2(3 + √5)/4
;;     =  (3 + √5)/2
;;     = (1+√5)/2 + 1
;;     = φ + 1
;;
;; (φ^n + φ^(n-1)) = φ^(n-1) * (φ + 1)
;;                 = φ^(n-1) * φ^2
;;                 = φ^(n+1)
;; (ψ^n + ψ^(n-1)) = ψ^(n+1)
;;
;; 따라서 Fib(n+1) = (φ^(n+1) - ψ^(n+1)) /√5
;;
;; ## 결론.
;; 기저 사례와 귀납 단계를 통해 Fib(n) = (φ^n – ψ^n)/√5 이다.





(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 (fib-binet n)
  (let* ((root-5 (sqrt 5))
         (φ (/ (+ 1 root-5) 2))
         (ψ (/ (- 1 root-5) 2)))
    (~> (- (expt φ n) (expt ψ n))
        (/ root-5)
        (round-half-up))))

(define (round-half-up x)
  ;; racket:exact-floor는 IEEE-754 방식(일명 "round half to even" 또는 bankers' rounding)을 사용
  ;; Round half up은 0.5이상 일때 무조건 올림.
  (cond ((zero? x) 0)
        ((positive? x) (racket:exact-floor (+ x 0.5)))
        (else          (racket:exact-floor (- x 0.5)))))

(racket:for ([x (racket:in-inclusive-range 1 75)])
            ;; 부동소수점 정밀도의 한계로 에러가 발생.
            (check-eq? (fib x) (fib-binet x) (racket:~a x)))

1_14

1.2.2에서 나온 count-change 함수가 11 센트(cent)에 맞게 잔돈을 만들어내는 트리를 그려보아라.

%%{init: {'flowchart' : {'curve' : 'monotoneX'}}}%%
graph TD
  cc_11_05_a["(cc 11 5)"] --> cc_11_04_a["(cc 11 4)"]
  cc_11_04_a --> cc_11_03_a["(cc 11 3)"]
  cc_11_03_a --> cc_11_02_a["(cc 11 2)"]
  cc_11_02_a --> cc_11_01_a["(cc 11 1)"]
  cc_11_01_a --> cc_11_00_a["(cc 11 0)"]
  cc_11_01_a --> cc_10_01_a["(cc 10 1)"]
  cc_10_01_a --> cc_10_00_a["(cc 10 0)"]
  cc_10_01_a --> cc_09_01_a["(cc 9 1)"]
  cc_09_01_a --> cc_09_00_a["(cc 9 0)"]
  cc_09_01_a --> cc_08_01_a["(cc 8 1)"]
  cc_08_01_a --> cc_08_00_a["(cc 8 0)"]
  cc_08_01_a --> cc_07_01_a["(cc 7 1)"]
  cc_07_01_a --> cc_07_00_a["(cc 7 0)"]
  cc_07_01_a --> cc_06_01_a["(cc 6 1)"]
  cc_06_01_a --> cc_06_00_a["(cc 6 0)"]
  cc_06_01_a --> cc_05_01_a["(cc 5 1)"]
  cc_05_01_a --> cc_05_00_a["(cc 5 0)"]
  cc_05_01_a --> cc_04_01_a["(cc 4 1)"]
  cc_04_01_a --> cc_04_00_a["(cc 4 0)"]
  cc_04_01_a --> cc_03_01_a["(cc 3 1)"]
  cc_03_01_a --> cc_03_00_a["(cc 3 0)"]
  cc_03_01_a --> cc_02_01_a["(cc 2 1)"]
  cc_02_01_a --> cc_02_00_a["(cc 2 0)"]
  cc_02_01_a --> cc_01_01_a["(cc 1 1)"]
  cc_01_01_a --> cc_01_00_a["(cc 1 0)"]
  cc_01_01_a --> cc_00_01_a["(cc 0 1)"]

  cc_11_02_a --> cc_06_02_a["(cc 6 2)"]
  cc_06_02_a --> cc_06_01_b["(cc 6 1)"]
  cc_06_01_b --> cc_06_00_b["(cc 6 0)"]
  cc_06_01_b --> cc_05_01_b["(cc 5 1)"]
  cc_05_01_b --> cc_05_00_b["(cc 5 0)"]
  cc_05_01_b --> cc_04_01_b["(cc 4 1)"]
  cc_04_01_b --> cc_04_00_b["(cc 4 0)"]
  cc_04_01_b --> cc_03_01_b["(cc 3 1)"]
  cc_03_01_b --> cc_03_00_b["(cc 3 0)"]
  cc_03_01_b --> cc_02_01_b["(cc 2 1)"]
  cc_02_01_b --> cc_02_00_b["(cc 2 0)"]
  cc_02_01_b --> cc_01_01_b["(cc 1 1)"]
  cc_01_01_b --> cc_01_00_b["(cc 1 0)"]
  cc_01_01_b --> cc_00_01_b["(cc 0 1)"]

  cc_06_02_a --> cc_01_02_a["(cc 1 2)"]
  cc_01_02_a --> cc_01_01_c["(cc 1 1)"]
  cc_01_01_c --> cc_01_00_c["(cc 1 0)"]
  cc_01_01_c --> cc_00_01_c["(cc 0 1)"]
  cc_01_02_a --> cc_m4_02["(cc -4 2)"]

  cc_11_03_a --> cc_01_03_a["(cc 1 3)"]
  cc_01_03_a --> cc_01_02_b["(cc 1 2)"]
  cc_01_02_b --> cc_01_01_d["(cc 1 1)"]
  cc_01_01_d --> cc_01_00_d["(cc 1 0)"]
  cc_01_01_d --> cc_00_01_d["(cc 0 1)"]
  cc_01_02_b --> cc_m4_02_b["(cc -4 2)"]

  cc_01_03_a --> cc_m9_03["(cc -9 3)"]

  cc_11_04_a --> cc_m14_04["(cc -14 4)"]

  cc_11_05_a --> cc_m39_05["(cc -39 5)"]

  classDef highlightNode fill:#ffcccc,stroke:#cc0000,stroke-width:2px;
  class cc_00_01_a highlightNode;
  class cc_00_01_b highlightNode;
  class cc_00_01_c highlightNode;
  class cc_00_01_d highlightNode;

;; file: 1_14.rkt
(#%require (prefix trace: racket/trace))

;; 1.2.2: count-change
(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0)
         1)
        ((or (< amount 0) (= kinds-of-coins 0))
         0)
        (else
         (+ (cc amount (- kinds-of-coins 1))
            (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))

(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)))

(count-change 100)
;;=> 292

(trace:trace cc)
(count-change 11)
;;=> 4
;;
;; 1. 10x 1 +  1x 1
;; 2.  5x 1 +  1x 6
;; 3.  5x 2 +  1x 1
;; 4.  1x11

;; amount가 증가함에 따라 사용되는 공간과 수행 단계의 증가 차수는?
;;
;; 1. 수행 단계 수 (시간 복잡도)
;; - https://en.wikipedia.org/wiki/Time_complexity
;;
;; - 얼핏보면: O(2^n)
;;   - cc안에서 cc가 두번 호출. 호출 트리가 이진 트리처럼 보임
;; - 사실은: O(n^5)
;;   - amount뿐만 아니라 동전 종류도 고려되야함.
;;   - 그리고 cc를 보면 중복호출하는데 이 중복 계산도 포함하게 되면 - O(n^k)
;;   - 메모이제이션이나 동적 계획법으로 풀면 O(n*k) 복잡도는 줄어들 수 있음.
;;
;; 2. 공간 사용량 (공간 복잡도)
;; - https://en.wikipedia.org/wiki/Space_complexity
;;
;; - 선형 O(n)
;;   - amount가 지속적 감소 ( 최대 호출 스택 깊이 )

1_15

;; file: 1_15.rkt
(#%require (prefix trace: racket/trace))

(define (cube x)
  (* x x x))

(define (p x)
  (- (* 3 x)
     (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

(trace:trace p)
(trace:trace sine)

;; 1. (sine 12.15)가 호출되면 p가 몇번 호출되나?
;; sine에서 angle을 3.0으로 계속 나누고 탈출조건은 |angle| < 0.1이니
;;
;; |12.15/3^(x - 1)} < 0.1
;; |3^(x - 1)|       < 121.5
;; 3^4=81
;; 3^5=243
;; 따라서 x = 5

;; (/ 12.15 3)               4.05
;; (/ 4.05 3)                1.3499999999999999
;; (/ 1.3499999999999999 3)  0.44999999999999996
;; (/ 0.44999999999999996 3) 0.15
;; (/ 0.15 3)                0.049999999999999996

(sine 12.15)
;;>> >{sine 12.15}
;;>> > {sine 4.05}
;;>> > >{sine 1.3499999999999999}
;;>> > > {sine 0.44999999999999996}
;;>> > > >{sine 0.15}
;;>> > > > {sine 0.049999999999999996}
;;>> < < < 0.049999999999999996
;;>> > > >{p 0.049999999999999996}        --- 1
;;>> < < <0.1495
;;>> > > {p 0.1495}                       --- 2
;;>> < < 0.4351345505
;;>> > >{p 0.4351345505}                  --- 3
;;>> < <0.9758465331678772
;;>> > {p 0.9758465331678772}             --- 4
;;>> < -0.7895631144708228
;;>> >{p -0.7895631144708228}             --- 5
;;>> <-0.39980345741334
;;=> -0.39980345741334


;; 2. (sine a)를 계산시 시간 복접도와 공간 복잡도를 a로 표현.
;;
;; 깊이 - 여기선 시간복잡도, 공간사용량도 깊이랑 같음.
;; a/3^n < 0.1
;; 3^n   > 10a
;; n     > log3(10a)
;;
;; - 수행 단계 수 (시간 복잡도): O(log(a))
;; - 공간 사용량  (공간 복잡도): O(log(a))

1_16

;; file: 1_16.rkt
;; 1_16 / 1_17 / 1_18
(#%require threading)
(#%require rackunit)
(#%require profile)

;; fast-expt를 iterate하게 바꿔라


(define (square x)
  (* x x))

(define (fast-expt b n)
  (cond (( = n 0)
         1)
        ((even? n)
         (square (fast-expt b (/ n 2))))
        (else
         (* b (fast-expt b (- n 1))))))

(define (fast-expt-iter b n)
  (define (iter acc b n)
    (cond (( = n 0)
           acc)
          ((even? n)
           (iter acc (square b) (/ n 2)))
          (else
           (iter (* acc b) b (- n 1)))))
  (iter 1 b n))

(~> (fast-expt 2 0)
    (check-equal? 1))
(~> (fast-expt 2 1)
    (check-equal? 2))
(~> (fast-expt 2 5)
    (check-equal? 32))
(~> (fast-expt 2 10)
    (check-equal? 1024))


(~> (fast-expt-iter 2 0)
    (check-equal? 1))
(~> (fast-expt-iter 2 1)
    (check-equal? 2))
(~> (fast-expt-iter 2 5)
    (check-equal? 32))
(~> (fast-expt-iter 2 10)
    (check-equal? 1024))

1_17

;; file: 1_17.rkt
;; 1_16 / 1_17 / 1_18

(#%require rackunit)

;; Mul구현. fast-expt처럼 계산단계가 로그로 자라도록 짜라.

(define (double x)
  (* 2 x))

(define (halve x)
  (/ x 2))

(define (mul a b)
  (if (= b 0)
      0
      (+ a (mul a (- b 1)))))

(define (fast-mul a b)
  (cond ((= b 0)
         0)
        ((even? b)
         (double (fast-mul a (halve b))))
        (else
         (+ a (fast-mul a (- b 1))))))


(check-equal? (mul 2 0)  0)
(check-equal? (mul 2 1)  2)
(check-equal? (mul 2 2)  4)
(check-equal? (mul 2 10) 20)
(check-equal? (mul 2 11) 22)

(check-equal? (fast-mul 2 0)  0)
(check-equal? (fast-mul 2 1)  2)
(check-equal? (fast-mul 2 2)  4)
(check-equal? (fast-mul 2 10) 20)
(check-equal? (fast-mul 2 11) 22)

1_18

;; file: 1_18.rkt
;; 1_16 / 1_17 / 1_18

(#%require rackunit)

;; Mul구현. 1.16와 1.17를 합쳐 계산 단계가 로그로 자라되 iterative형태로 짜라.

(define (double x)
  (* 2 x))

(define (halve x)
  (/ x 2))


(define (fast-mul-iter a b)
  (define (iter acc a b)
    (cond ((= b 0)
           acc)
          ((even? b)
           (iter acc (double a) (halve b)))
          (else
           (iter (+ acc a) a (- b 1)))))
  (iter 0 a b))


(check-equal? (fast-mul-iter 2 0)  0)
(check-equal? (fast-mul-iter 2 1)  2)
(check-equal? (fast-mul-iter 2 2)  4)
(check-equal? (fast-mul-iter 2 10) 20)
(check-equal? (fast-mul-iter 2 11) 22)

1_19

;; file: 1_19.rkt
(#%require racket/trace)

;; 빈칸체우기
#|
T(a, b) - p/q에 대해서
a' = bq + aq + ap
b' = bp + aq

T(T(a, b)) - p/q에 대해서
a'' =         b'q +             a'q +             a'p
    = ((bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
    =  bpq + aq^2 + bq^2 + aq^2 + aqp + bqp + aqp + ap^2
    = b(2qp + q^2)+    a(q^2 + p^2) +    a(2qp + q^2)
b'' =          b'p +             a'q
    =   (bp + aq)p + (bq + aq + ap)q
    =   bp^2 + aqp + bq^2 + aq^2 + aqp
    = b(p^2 + q^2) +    a(2qp + q^2)

p' = p^2 + q^2
q' = 2qp + q^2

|#


(define (fib-recur n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib-recur (- n 1))
                 (fib-recur (- n 2))))))

(define (fast-fib-iter 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
                   (+ (* p p) (* q q))   ; p' = p^2 + q^2
                   (+ (* 2 p q) (* q q)) ; q' = 2qp + q^2
                   (/ count 2)))
        (else 
         (fib-iter (+ (* b q) (* a q) (* a p)) ; a = bq + aq + ap
                   (+ (* b p) (* a q))         ; b = bp + aq
                   p
                   q
                   (- count 1)))))
#|

| fib | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10|
|-----|---|---|---|---|---|---|---|---|---|---|---|
| res | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13| 21| 34| 55|

|#

(fib-recur 10)

(fast-fib-iter 10)

#|
(trace fib-iter)

>{fib-iter 1 0 0 1 10}
>{fib-iter 1 0 1 1 5}
>{fib-iter 2 1 1 1 4}
>{fib-iter 2 1 2 3 2}
>{fib-iter 2 1 13 21 1}
>{fib-iter 89 55 13 21 0}
<55
|#