Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Considerando apenas interesse acadêmico, quais são as implementações computacionais possíveis da sequência de Fibonacci?

0 votos
76 visitas
perguntada Abr 17, 2015 em Ciência da Computação por danielcajueiro (5,171 pontos)  

Você pode também apresentar o custo computacional associado?

Compartilhe

3 Respostas

+2 votos
respondida Abr 22, 2015 por danielcajueiro (5,171 pontos)  

Para começar, veja abaixo três implementações da sequência de fibonacci.

def fibonacci_smart_recursive(n,x1=0,x2=1):
    if(n==1):
        return x1
    else:
        if(n==2):
            return x2
        else:
            return fibonacci_smart_recursive(n-1,x2,x1+x2)

def fibonacci_recursive(n):
    if(n>2):
        return fibonacci_recursive(n-1)+fibonacci_recursive(n-2)
    else:
        if(n==2):
            return 1    
        else:
            return 0 

def fibonacci(n):
    fm2=0
    fm1=1
    for i in range(2,n):
        f=fm1+fm2
        fm2=fm1
        fm1=f
    return f        

if __name__ == '__main__':

    print fibonacci(12)

    print fibonacci_recursive(12)

    print fibonacci_smart_recursive(12)

A função "fibonacci" é a implementação mais simples dessa sequência. A implementação recursiva "fibonacci_recursiva" é provavelmente a mais convencional, mas ela é muito ineficiente. Finalmente, a implementação "fibonacci_smart_recursive" é uma forma recursive que possui a mesma complexidade computacional da implementação "fibonacci".

comentou Mar 21, 2016 por Caue (226 pontos)  
editado Abr 15, 2016 por Caue
Uma forma mais direta de escrever a fibonacci_smart_recursive:

def fibonacci_smart_recursive(n, x1=0, x2=1):
    return x1 if (n == 1) else fibonacci_smart_recursive(n-1, x2, x1+x2)

Outra implementação interessante da sequência de fibonacci é usando generator:

def fibonacci_generator(x1=0, x2=1):
    a, b = x1, x2
    while True:
        yield a
        a, b = b, a+b

Essa implementação é útil quando não sabemos até onde precisamos avançar na sequência.
comentou Mar 21, 2016 por danielcajueiro (5,171 pontos)  
Sim! Bem legal! A primeira é no estilo de programação funcional e a segunda você está usando um iterador. Vc não gostaria de colocar como resposta adicional? As pessoas não olham os comentários.
0 votos
respondida Abr 7, 2016 por danielcajueiro (5,171 pontos)  

Essas implementações em R foram feitas por um estudante (se não me engano foi o Carlos Cinelli em uma versão preliminar do curso de Métodos Computacionais em Economia da UNB) em R:

##### Fibonacci ####
# recursivo e vetorizado
fib1 <- function(n){
  ifelse(n<2, n, fib1(n-1)+fib1(n-2))
}

# loop
fib2 <- function(n){
  if(n<2) return(n)
  fibm1 <- 1
  fibm2 <- 1
  for(i in 3:n){
    fib <- fibm1 + fibm2
    fibm2 <- fibm1
    fibm1 <- fib
  }
  return(fib)
}

# recursivo 2
fib3 <- function(n){
  fib <- function(n, fibm1, fibm2){
    if(n==1){return(fibm2)}
    if(n==2){return(fibm1)}
    if(n >2){
      fib(n-1, fibm1+fibm2, fibm1)  
    }
  }
  fib(n, 1, 1)  
}

## recursivo e vetorizado com custo linear
fib4 <- function(n){
  fib <- function(n, fibm1, fibm2){
    ifelse(n<=1, fibm2,
           ifelse(n==2, fibm1,
                  fib(n-1, fibm1+fibm2, fibm1)  
           ))
  }
  fib(n, 1, 0)  
}


# linear e com memorização (não é preciso recalcular)
fibonacci <- local({
  memo <- c(1, 1)
  f <- function(x) {
    if(x == 0) return(0)
    if(x < 0) return(NA)
    if(!is.na(memo[x])) return(memo[x])
    ans <- f(x-2) + f(x-1)
    memo[x] <<- ans
    ans
  }
})

# testando
fib1(10)
fib1(1:10)
fib2(10)
fib3(10)
fib4(10)
fib4(1:10)
fibonacci(10)
get("memo", envir=environment(fibonacci)) ## memória de cálculo
0 votos
respondida Mai 18, 2016 por danielcajueiro (5,171 pontos)  

Considerando a abordagem de Programação Dinâmica, nós podemos adicionar duas outras implementações como re-implementação da abordagem da forma recursiva e ineficiente: memoization e botton-up.

def fibonacci_recursive(n):
    if(n>2):
        return fibonacci_recursive(n-1)+fibonacci_recursive(n-2)
    else:
        if(n==2):
            return 1    
        else:
            return 0 

def fibonacci_recursive_with_memoization(n,sequence={}):
    if(n>2):
        if(n-1 in sequence):
            fib1=sequence[n-1]    
        else:
            fib1=fibonacci_recursive_with_memoization(n-1,sequence)
            sequence[n-1]=fib1
        if(n-2 in sequence):
            fib2=sequence[n-2]    
        else:
            fib2=fibonacci_recursive_with_memoization(n-2,sequence)      
            sequence[n-2]=fib2
        sequence[n]=fib1+fib2    
        return sequence[n]
    else:
        if(n==2):
            return 1    
        else:
            return 0 


def fibonacci_bottom_up(n):
    if(n==1):
        return 0
    elif(n==2):
        return 1
    else:
        sequence=[]
        sequence.append(0)
        sequence.append(1)
        for i in range(2,n):
            sequence.append(sequence[i-1]+sequence[i-2])
        return sequence[n-1]



if __name__ == '__main__':


    print fibonacci_recursive(12)

    print fibonacci_recursive_with_memoization(12)

    print fibonacci_bottom_up(12)    
...