#lang racket
;; 1.11
(define (recursive-f n)
(cond [(< n 3) n]
[else (+ (recursive-f (- n 1))
(* 2 (recursive-f (- n 2)))
(* 3 (recursive-f (- n 3))))]))
(recursive-f 1)
;; 1
(recursive-f 2)
;; 2
(recursive-f 3)
;; 4
(recursive-f 4)
;; 11
(recursive-f 5)
;; 25
(recursive-f 6)
;; 59
(define (iterative-f n)
(define (f-iter a b c cnt)
(cond [(zero? cnt) a]
[else (f-iter (+ a (* 2 b) (* 3 c))
a
b
(sub1 cnt))]))
(cond [(< n 2) n]
[else (f-iter 2 1 0 (- n 2))]))
(iterative-f 1)
;; 1
(iterative-f 2)
;; 2
(iterative-f 3)
;; 4
(iterative-f 4)
;; 11
(iterative-f 5)
;; 25
(iterative-f 6)
;; 59
;; 1.12
(define (pascal row col)
(cond [(or (= col 1) ; start of row
(= row col)) ; end of row
1]
[else (+ (pascal (sub1 row) (sub1 col)) ; sum of two elements above
(pascal (sub1 row) col))]))
(pascal 5 1)
;; 1
(pascal 5 2)
;; 4
(pascal 5 3)
;; 6
(pascal 5 4)
;; 4
(pascal 5 5)
;; 1
;; 1.13
;; Note that phi ^ 2 = phi + 1 and psi ^ 2 = psi + 1 because phi and psi are roots
;; of x ^ 2 - x - 1 = 0.
;; claim: Fib(n) = (phi ^ n - psi ^ n) / sqrt(5)
;; Go by induction. The base cases n = 0 and n = 1 are true.
;; The induction step is
;; [phi ^ (n + 1) - psi ^ (n + 1)] / sqrt(5)
;; = [phi ^ 2 * phi ^ (n - 1) - psi ^ 2 * psi ^ (n - 1)] / sqrt(5)
;; = [(phi + 1) * phi ^ (n - 1) - (psi + 1) * psi ^ (n - 1)] / sqrt(5)
;; = [phi ^ n + phi ^ (n - 1) - psi ^ n - psi ^ (n - 1)] / sqrt(5)
;; = (phi ^ n - psi ^ n) / sqrt(5) + (phi ^ (n - 1) - psi ^ (n - 1)) / sqrt(5)
;; = Fib(n) + Fib(n - 1) by induction
;; = Fib(n + 1)
;; That Fib(n) is the closest integer to phi ^ n / sqrt(5) follows from the above
;; claim combined with the fact that abs(psi ^ n / sqrt(5)) < 0.5.
;; In particular Fib(n) = O(phi ^ n) is exponential.
Comments