Fibonacci: returning a selection of the series
geremy condra
debatem1 at gmail.com
Sun Aug 29 20:55:17 CEST 2010
On Sun, Aug 29, 2010 at 10:36 AM, Baba <raoulbia at gmail.com> wrote:
> level: beginner
>
> i would like to return a selection of the Fibonacci series.
> example:
> start = 5 ; end = 55
> the function should then return [5, 8, 13, 21, 34, 55]
>
> it seems that this is best resolved using an iterative approach to
> generate the series. In another post (http://groups.google.ie/group/
> comp.lang.python/browse_thread/thread/aa85ac893fd89c4a/
> d3803a93baf1bdd0#d3803a93baf1bdd0) i looked at the recursive approach
> which seems best to compute the nth number but it seems to me that the
> recursive code is not suited for generating the actual list.
>
> my questios:
> - would you agree that recursive is not ideal for generating a list?
> (in this particular case and in general)
> - can my code below be optimised?
> - how to deal with 'start' and 'end' values that are not in the list
> e.g. 4,76 ?
>
> def i_fib(n):
> a = 0
> b = 1
> list = []
> counter = 0
> while counter < n:
> a, b = b, a+b
> counter += 1
> list = list + [b,]
> return list
>
> def fib_range(start,end):
> list = i_fib(12)
> if start in list and end in list:
> start = list.index(start)
> end = list.index(end)
> print list[start:end+1]
> else: print 'not in list'
>
> fib_range(5,55)
>
> thanks
> Baba
Get the index of the start, use that to generate the second, and
iterate until you hit the end.
from math import sqrt, log, floor
phi = (1 + sqrt(5))/2
def fibonacci_index(n):
return floor(log(n * sqrt(5))/log(phi) + .5)
def ith_fibonacci(i):
return floor(phi**i/sqrt(5) + .5)
def next_fibonacci(a, b):
return a + b
def fibonacci_between(start, stop):
# find the index of the first
i = fibonacci_index(start)
# find the second value given the first
second_fib = ith_fibonacci(i+1)
# build the list from there
fibs = [start, second_fib]
while fibs[-1] != stop:
fibs.append(next_fibonacci(fibs[-1], fibs[-2]))
# and we're done
return fibs
Now try to understand *why* the above works, rather than just copy-pasting it.
Geremy Condra
More information about the Python-list
mailing list