Category Archives: algorithm

Top coder

Top coder


The programmer, like the poet, works only slightly removed from pure though-stuff. He builds his castles int he air, from air, creating by exertion of the imagination.

— Frederick P. Brooks.


Play with fibonacci function

Tonight, I write some code in LISP for my homework. One of these was working with function definition, and fibonacci function was chosen as my example on this stuff.

In LISP, I wrote something like :

(defun fibo ( N )
( if ( or ( = 0 N ) ( = 1 N)) 1
(+ (fibo ( 1- N)) (fibo (1- ( 1- N)))
)))

Wow, with n = 5000, my laptop  was freezing LOL.

So, I find some smarter way to solve this problem.

This time, I choose Python (my favourite ) as my ‘weapon’.

Let’s dig into this problem:

Fibonacci problem is defined on a non-negative integer number N:

if n is equal to 1 or 0 :

return 1

else

return fibonacci(N -1 ) + fibonacci( N-2)

I’m gonna make this clearer with  following  expanding:

if N = 0 or N = 1 : reuturn 1 ( clear, nothing to say)

if N = 2 : return f(0 )  + f(1)

if N = 3 : return  f(2 ) + f(1) = [f(0 ) + f(1)] + f(1)

if N =4 : return f(3) + f(2) = {[f(0 ) + f(1)] + f(1)} + [f(0) + f(1)]

……… etc..

OK, that’s enough expanding, from this point , we are able to form a line ( or a pattern ) of this kind of recursive rule.

For computing the n-th fibonacci number, we don’t have to make any recursive call. Instead, we could sum up a series of numbers – each of them was computed by adding cumulatively numbers – until we meet the basic cases ( o and 1).

And each call in this series need to know 2 previous values ( f(N-1 ) and f(N-2)) , so we save these 2 values for present call.

That’s the idea, and here is the code (in Python – I’m sure it’s very clear, very ‘natural’ to your mind):


# fibo problem in a smart way
def fibo (n):
fn1 = 1 # f(n-1 )
fn2 = 1 # f(n-2 )
S = 0
count = 2;
if n == 0 or n ==1 :
return 1;
else:
while(count < n +1): # count = 2
S = fn1 + fn2
fn1 = fn2
fn2 = S
count = count + 1
return S

And there it is ! See ya !