Re:Can you solve it? The Greplin programming challenge
by btilly on Friday October 08, 2010 @09:30PM
(#1774080)
Elegant, but inefficient if you want to get exact values for large n. You're much better off using doubling operations. If you forget those, you can remember them from the matrix version. If fib(0) = 0. fib(1) = 1. etc. Then
n
[0 1] = [fib(n) fib(n+1)]
[1 1] [fib(n+1) fib(n+2)]
With repeated squarings, you can efficiently generate any Fibonacci number you want.
Re:Can you solve it? The Greplin programming challenge
by kasterma on Sunday October 10, 2010 @10:08AM
(#1777102)
Here (where you have to search through Fibonacci numbers) I suspect memoization is rather the way to go:
# memoized fibonacci function
fibtable = {1:1, 0:1}
def fib (n):
global fibtable
if n in fibtable.keys():
return fibtable [n]
val = fib (n-1) + fib (n-2)
fibtable [n] = val
return val
int((1/math.sqrt(5))*(math.pow(((1+math.sqrt(5))/2),fibonacci)-math.pow(((1-math.sqrt(5))/2),fibonacci)))
Reference here: http://mathproofs.blogspot.com/2005/04/nth-term-of-fibonacci...