This is my Clojure solution to Chapter 1, Exercise 13:
(ns sicp.ch1.ex13)
(defn fib
[n]
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(def phi (/ (+ 1 (Math/sqrt 5)) 2))
(def psi (/ (- 1 (Math/sqrt 5)) 2))
(defn fib-exact
[n]
(Math/round (/ (- (Math/pow phi n) (Math/pow psi n))
(Math/sqrt 5))))
(every? #(= (fib %) (fib-exact %)) (range 10)) ; => true
;; assume f(n) = (phi^n - psi^n)/5^-2
;; assume f(n + 1) = (phi^(n + 1) - psi^(n + 1)/5^-2
;; prove that f(n + 2) = (phi^(n + 2) - psi^(n + 2)/5^-2 where
;; f(n + 2) = f(n + 1) + f(n)
(ns sicp.ch1.ex13)
(defn fib
[n]
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
(def phi (/ (+ 1 (Math/sqrt 5)) 2))
(def psi (/ (- 1 (Math/sqrt 5)) 2))
(defn fib-exact
[n]
(Math/round (/ (- (Math/pow phi n) (Math/pow psi n))
(Math/sqrt 5))))
(every? #(= (fib %) (fib-exact %)) (range 10)) ; => true
;; assume f(n) = (phi^n - psi^n)/5^-2
;; assume f(n + 1) = (phi^(n + 1) - psi^(n + 1)/5^-2
;; prove that f(n + 2) = (phi^(n + 2) - psi^(n + 2)/5^-2 where
;; f(n + 2) = f(n + 1) + f(n)
No comments:
Post a Comment