Stack Overflow programa de sequência de Fibonacci

1. Stack Overflow programa de sequência de Fibonacci

luanobre
(usa Outra)

Enviado em 30/08/2017 - 00:53h

Boa noite pessoal, estou com problemas para resolver o overflow deste código:



#include <stdio.h>

#include <sys/wait.h>

#include <sys/types.h>

#include <unistd.h>



int fib(int x){



        if(x<=2){

                return 1;

        }else{

                return fib(x-1) + fib(x-2);

        }

}



int main(){

        pid_t pid;

        int x, i;



        pid = fork();



        if(pid != 0){

                waitpid(-1,0,0);

        }else{

                printf("Informe um número que deseja que gere a sequencia Fibonacci: ");

                scanf("%d", &x);

                printf("Sequência de Fibonacci... \n");

        for(i=0; i<x;i++){

                printf(" %d |", fib(i+1));

        }

        printf("\n");

}

}

Alguém pode me ajudar??

0 0

Quote

2. Re: Stack Overflow programa de sequência de Fibonacci

paulo1205
(usa Ubuntu)

Enviado em 31/08/2017 - 02:03h

á erro a partir de que valor de x?

Por curiosidade, com que finalidade você usou fork() nesse programa?

0 0

Quote

3. Re: Stack Overflow programa de sequência de Fibonacci

paulo1205
(usa Ubuntu)

Enviado em 31/08/2017 - 03:36h

O problema é que essas chamadas recursivas, que parecem tão simples e inocentes, acabam tendo uma execução que cresce exponencialmente, de acordo com o valor o argumento.

Melhor seria se você convertesse essa versão recursiva, que cresce exponencialmente, numa implementação usando laço de repetição, que cresce apenas linearmente. Aliás, você até já tem um laço de repetição, pois você imprime todos os valores de Fib(1) até Fib(n), de modo que você pode reaproveitar os dois valores calculados nas iterações anteriores, para que a interação corrente execute com tempo constante.

0 0

Quote

4. Re: Stack Overflow programa de sequência de Fibonacci

luanobre
(usa Outra)

Enviado em 31/08/2017 - 06:38h

paulo1205 escreveu:

á erro a partir de que valor de x?

Por curiosidade, com que finalidade você usou fork() nesse programa?

Esse exercício é pra gente ver como se comportam os processos dentro do SO. O erro acontece a partir do 50° valor de Fibonacci e não é pra acontecer o estouro. Independente do valor que se digitar, o programa deverá mostrar os valores...

0 0

Quote

5. Re: Stack Overflow programa de sequência de Fibonacci

luanobre
(usa Outra)

Enviado em 31/08/2017 - 06:42h

paulo1205 escreveu:

O problema é que essas chamadas recursivas, que parecem tão simples e inocentes, acabam tendo uma execução que cresce exponencialmente, de acordo com o valor o argumento.

Melhor seria se você convertesse essa versão recursiva, que cresce exponencialmente, numa implementação usando laço de repetição, que cresce apenas linearmente. Aliás, você até já tem um laço de repetição, pois você imprime todos os valores de Fib(1) até Fib(n), de modo que você pode reaproveitar os dois valores calculados nas iterações anteriores, para que a interação corrente execute com tempo constante.

Então , eu cheguei a ver essa solução mesmo em outras pesquisas mas eu não conseguir implementar no código .

0 0

Quote

6. Re: Stack Overflow programa de sequência de Fibonacci

paulo1205
(usa Ubuntu)

Enviado em 31/08/2017 - 10:00h

A sequência de Fibonacci não usa números negativos, então você pode trabalhar com unsigned ou unsigned long em lugar de int.

// Imprime os N primeiros números da sequência de Fibonacci.

unsigned long N, n, Fib_n, Fib_n_1, Fib_n_2;



// Lê N (não mostro como).



if(N>0)

  printf("Fib(1)=1\n");

if(N>1)

  printf("Fib(2)=1\n");

if(N>2){

  Fib_n_1=Fib_n_2=1;

  for(n=3; n<=N; n++){

    Fib_n=Fib_n_1+Fib_n_2;

    printf("Fib(%lu)=%lu\n", n, Fib_n);

    Fib_n_2=Fib_n_1;

    Fib_n_1=Fib_n;

  }

}

1 0

Quote

7. Re: Stack Overflow programa de sequência de Fibonacci

luanobre
(usa Outra)

Enviado em 31/08/2017 - 23:13h

paulo1205 escreveu:

A sequência de Fibonacci não usa números negativos, então você pode trabalhar com unsigned ou unsigned long em lugar de int.

// Imprime os N primeiros números da sequência de Fibonacci.

unsigned long N, n, Fib_n, Fib_n_1, Fib_n_2;



// Lê N (não mostro como).



if(N>0)

  printf("Fib(1)=1\n");

if(N>1)

  printf("Fib(2)=1\n");

if(N>2){

  Fib_n_1=Fib_n_2=1;

  for(n=3; n<=N; n++){

    Fib_n=Fib_n_1+Fib_n_2;

    printf("Fib(%lu)=%lu\n", n, Fib_n);

    Fib_n_2=Fib_n_1;

    Fib_n_1=Fib_n;

  }

}