WTF is Fibonnacci
Sean Ross
sross at connectmail.carleton.ca
Thu Jun 19 21:21:22 CEST 2003
"Mike" <ss3canon at earthlink.net> wrote in message
news:7inIa.55233$Io.5225846 at newsread2.prod.itd.earthlink.net...
> I'm readin through the Non-Programers Tutorial for Python and I'm on the
> examples of section Count to 10. And I can't figure out how the example
got
> the output, can anyone help break it down for me?
>
>
# From Non-Programmers Tutorial for Python
# http://honors.montana.edu/~jjc/easytut/easytut/node6.html
# Fibonnacci.py
#This program calulates the fibonnacci sequence
a = 0
b = 1
count = 0
max_count = 20
while count < max_count:
count = count + 1
#we need to keep track of a since we change it
old_a = a
old_b = b
a = old_b
b = old_a + old_b
#Notice that the , at the end of a print statement keeps it
# from switching to a new line
print old_a,
print
Output:
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
You can find a *very* detailed discussion of what the fibonacci numbers are
here:
http://mathworld.wolfram.com/FibonacciNumber.html
But, here's a quick version:
A fibonacci number f_n is a number whose value is defined by the recursive
relation f_n = f_n-2 + f_n-1, for n= 3, 4, ...
where f_0 = 0, f_1 = 1, and f_2 = 1.
What does that mean? Let's state it as a function:
Let f_n be represented by f(n). Then f(n) = f(n-2) + f(n-1), by the relation
expressed above when n >= 3.
And we say that
f(0) = 0,
f(1) = f(2) = 1
Here's a concrete example:
f(3) = f(3-2) + f(3-1) = f(1) + f(2) = f(1) + [f(2-2) + f(2-1)]
= 1+[f(0) + f(1)] = 1 + [0 + 1] = 1 + 1 = 2
so f(3) = 2
or the 3rd fibonacci number (f_3) is 2.
Here's the first 99 fibonacci numbers represented as f(n), 0 <= n <= 99
http://math.holycross.edu/~davids/fibonacci/fib0-99.html
Hope this helps,
Sean
More information about the Python-list
mailing list