• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Flavio Amorim

[C] Sequencia Fibonacci recursiva

8 mensagens neste tópico

Sequência de Fibonacci usando recursividade.

#include<stdio.h>

int fib(int n)
{
if(n==0 || n==1)
	return(1);
else
	return(fib(n-2)+fib(n-1));

}
main()
{ int n,x;
printf("introduza um n:\n");
scanf("%d",&n);
x=fib(n);
printf("soma=%d\n",x);

}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Atenção que esse método é altamente ineficiente.

Tens aqui a explicação:

http://www.upgaming-hq.com/cd_ioi_05/manual/technique.html

Eles falam de programação dinâmica para resolver esse problema, mas não era preciso ir tão longe, "memoization" também resolveria.

Edit: afinal também falam de memoization, já não me lembrava da página.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu já tinha escrito um programa que apresentava a série Fibonacci (dentro de certos limites).

#include <stdio.h>
#include <stdlib.h>

#define ITERATIONS 25

int main()
{
    unsigned long int array[iTERATIONS];
    int i;
    
    array[0] = 0;
    array[1] = 1;
    printf("%lu\n", array[0]);
    printf("%lu\n", array[1]);
    
    for(i = 2; i < ITERATIONS; ++i)
    {
        array[i] = array[i-1] + array[i-2];
        printf("%lu\n", array[i]);
    }
    puts("");
    return 0;
} 

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O(log n):

    [ 1 1 ] n      [ F(n+1)  F(n)  ]

    [ 1 0 ]    =  [ F(n)      F(n-1)]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Python:

front = 2
back = 1
total = 3

while front < 1000000:

middle = front
front = front + back
back = middle
        print front

input()

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

OCaml :

exception Input_Negativo;;

(* versão terminal recursiva *) 
let rec fib_fast x acc1 acc2 = 
   if x<0 then raise Input_Negativo
   else 
     if x = 0 then acc1
     else 
       if  x = 1 then acc2
    else fib_fast (x-1) acc2 (acc2+acc1)
;;

Para quem gosta linguagem funcional

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Boas, Sei que o post é antigo, mas não custa nada adicionar outro caso e reforçar para quem chega depois :)


unsigned int fib(unsigned int n)
{
   unsigned int i, prev, cur, next;

   if(n < 2 )
        return n; 

   for(i=2; i <= n; i++)
   {
          next = cur + prev;
          prev = cur;
          cur = next;
   }

   return next;
}

Nada como uma forma iterativa :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora