高效地计算第n个斐波那契代码,Java代码库,德仔网

代码语言

代码分类

【Java】高效地计算第n个斐波那契

作者:Dezai.CN / 发布于2011/11/22/ 428

<div>(ns redraiment.math.fibonacci
 "Some utils for generate fibonacci number.")</div>
<div>(def ^{:private true :dynamic true} *base*
 "Base number for composite number.
As you know, it's complex when *base* = -1."
 5)</div>
<div>(defn- multiply
 "Returns the product of composite nums. Supports arbitrary precision.
(multiply) returns [1 0]."
 [& args]
 (reduce
 #(let [a1 (first %1)
 b1 (second %1)
 a2 (first %2)
 b2 (second %2)]
 [(+ (* a1 a2) (* b1 b2 *base*))
 (+ (* a1 b2) (* a2 b1))])
 (cons [1 0] args)))</div>
<div>(defn- pow
 "Returns a composite num whose value is c^n."
 [c n]
 (cond
 (== n 0) [1 0]
 (== n 1) c
 (> n 1) (let [sub (pow c (quot n 2))]
 (multiply sub sub (if (odd? n) c [1 0])))
 :else (throw (IllegalArgumentException.
 "n MUST be a natural number"))))</div>
<div>(defn fibonacci-nth
 "Returns the n-th fibonacci in high performance.
The algorithm is: fib(n) = (a^n - b^n) / (a - b)
where a = (1 + sqrt(5)) / 2 and b = -1 / a.
See <a href="http://en.wikipedia.org/wiki/Fibonacci_number">http://en.wikipedia.org/wiki/Fibonacci_number</a>."
 [n]
 (* (second (pow [1/2 1/2] n)) 2))
</div>

试试其它关键字

　第n个斐波那契　

同语言下

可能有用的

Dezai.CN贡献的其它代码(4037)