domingo, junho 04, 2006

[Python] Meu segundo e terceiro programa

Fatorial
def fat(n):
  if n == 0:
     return 1
  else:
 return n*fat(n-1)
Fibonacci
def fibo(n):
   if n <= 0:         
      return 0     
   elif n == 1:         
      return 1     
   else:  
      return fibo(n-1)+fibo(n-2) 
Classicos !

3 Comments:

Anonymous Anônimo said...

Claro que a solução recursiva pra Fatorial é ruim... que tal uma iterativa? Com for ou while? :)

6/07/2006 01:24:00 AM  
Blogger Miguel Galves said...

Aqui esta:

def fat(n):
f = 1
while n > 1:
f *= n
n -= 1
return f

6/07/2006 09:27:00 AM  
Blogger Miguel Galves said...

A solução recursiva pro fatorial é ruim por causa do custo de chamada de função. Mas em termos assintóticos, ambas são equivalentes.

Problemas mesmo é a solução recursiva para fibonacci. É bem fácil de implementar, mas a complexidade vira exponencial.

Portanto, ai vai uma versao iterativa:

def fibo(n):
###if n < 2:
######return 1
###fm1 = 1
###fm2 = 1
###for i in range(2,n+1):
######fibo = fm1+fm2
######fm2=fm1
######fm1=fibo
###return fibo

if __name__ == "__main__":
###for i in range(10):
######print fibo(i),

Os # são para indicar indentação...

6/09/2006 11:37:00 AM  

Postar um comentário

Links to this post:

Criar um link

<< Home