-
Notifications
You must be signed in to change notification settings - Fork 0
/
fibonacci.clj
55 lines (40 loc) · 1.18 KB
/
fibonacci.clj
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
(ns func-proc.fibonacci)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; FIBONACCI NUMBERS
;; https://www.hackerrank.com/challenges/functional-programming-warmups-in-recursion---fibonacci-numbers
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(comment
;; Non-tail recursive fibonacci sequence.
(defn fibonacci [n]
{:pre [(> n 0)]}
(cond (= n 1) 0
(= n 2) 1
:otherwise (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
)
(comment
;; Tail recursive fibonacci sequence.
(defn fibonacci [n]
{:pre [(> n 0)]}
(if (= n 1) 0
(loop [fibs [0 1] i 2]
(if-not (= n i)
(let [[a b] fibs c a a b b (+ b c)]
(recur [a b] (inc i)))
(last fibs)))))
)
;; Fibonacci O(1).
(defn fibonacci [n]
{:pre [(> n 0)]}
(if (zero? n) 1
(let [n (dec n)
sqrt5 (Math/sqrt 5.0)
fi (/ (+ 1.0 sqrt5) 2.0)
psi (/ (- 1.0 sqrt5) 2.0)
fib (/ (- (Math/pow fi n) (Math/pow psi n)) sqrt5)]
(int fib))))
(comment
;; Reads HackerRank input data and solves the problem
(let [n (Integer/parseInt (read-line))]
(println (fibonacci n))))