Liczby Fibonacciego. Rekurencja

Mam tutaj kod z użyciem rekurencji. Liczby generuje dobrze ale jeśli chce je wyświetlić w funkcji main a nie w fibo to od razu po wystarowaniu okno się zamyka. Nie wyskakują żadne informacje o błędach.

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

void fibo ( int tab[], int n, int x);

int main(void)
{
    int n = 0;
    int tab[n];
    int x = 2;
    int i;
    
    tab[0] = 1;
    tab[1] = 1;
    
    printf("Podaj zakres: ");
    scanf("%d", &n);
    fibo (tab, n, x);
    
    for (i = 0; i < n; i++)
        printf("%d\n",tab[i]);
         
    
  system("PAUSE");	
  return 0;
}           
  

    void fibo ( int tab[], int n, int x)
    {
    
        tab[x] = tab[x-1] + tab[x-2];
        x++;
        if(x<n)
        fibo (tab, n, x);
        printf(" %d\n",  tab[x]);
       
    }
         
       

Spróbuj tak:

void fibo ( int * tab, int n, int x)

Powinno pomóc, ale dawno nie pisałem w C++ i mogę się mylić

    int n;
    printf("Podaj zakres: ");
    scanf("%d", &n);
    int tab[n];  // po scanf
...
    tab[0] = 0; // było 1 
 

Jeżeli chcesz tylko wyświetlać obliczone liczby, nie używaj tablic. Numeracja tablicy zaczyna się od 0. Weź to pod uwagę jeżeli chciałbyś stablicować wyniki.
Przeanalizuj kod:

 
#include <iostream>
using namespace std;

int Fibonacci(int x)
{
if (x==1||x==2)
    return 1;
 else
 return Fibonacci(x-1) + Fibonacci(x-2);
}

int main()
{
   int n;
   cout << "Podaj szukana ilosc liczb= ";
   cin >> n;
   for(int i=1;i<=n;++i)
   cout << i << " wyraz ciagu Fibonacciego to: " << Fibonacci(i) <<endl;
                
   system("pause>null");
   return 0;

Używanie rekurencji do obliczania wyrazów ciągu Fibonacciego jest bardzo nieoptymalne i powinno być karane.

bogdans napisał(a)

Używanie rekurencji do obliczania wyrazów ciągu Fibonacciego jest bardzo nieoptymalne i powinno być karane.

Używanie ciągu Fibonacciego do nauki rekurencji jest bardzo powszechne w szkołach i powinniśmy w takim razie zamknąć połowę belfrów :P

Bierze się to zapewne stąd, że definicja ciągu Fibonacciego jest rekurencyjna. Przy obliczeniach ręcznych wyrazów ciągu stosowana jest rekurencja z zapamiętywaniem, która jest sensowna.
Wracając do zamykania nauczycieli, taka kara jest trochę zbyt surowa. Tym niemniej nauczyciel informatyki, który każe napisać program obliczający rekurencyjnie wyrazy ciągu Fibonacciego, a nie uzupełni tego polecenia porównaniem ilości wykonanych w programie dodawań z ilością dodawań w programie wykorzystującym tablicę, powinien mieć zakaz nauczania.

Używanie rekurencji do obliczania wyrazów ciągu Fibonacciego jest bardzo nieoptymalne i powinno być karane.

A co powiesz na to:

#include <iostream>
using namespace std;

unsigned long long fib(unsigned char x)
  {
   static unsigned long long tb[94]={0,1,1,0};
   if(x<2) return x;
   if(x>93) return 0;
   if(tb[x]) return tb[x];
   return tb[x]=fib(x-1)+fib(x-2);
  }
  
int main()
  {
   for(int i=0;i<95;++i) cout<<i<<'\t'<<fib(i)<<endl;
   cin.get();
   return 0;
  }

Czyżby nie jest to wersja rekurencyjna?

Sarrus napisał(a)

bogdans napisał(a)

Używanie rekurencji do obliczania wyrazów ciągu Fibonacciego jest bardzo nieoptymalne i powinno być karane.

Używanie ciągu Fibonacciego do nauki rekurencji jest bardzo powszechne w szkołach i powinniśmy w takim razie zamknąć połowę belfrów :P

Do nauki rekurencji to się powinno używać funkcji Ackermanna.

Wersja rekurencyjna z zapamiętywaniem - złożoność obliczeniowa i pamięciowa O(n):

val fibs: Stream[Int] = 0 #:: 1 #:: (fibs zip fibs.tail).map{ case (a,b) => a+b } 

Wersja obliczająca dowolną liczbę ciągu w czasie O(log n), złożoność pamięciowa O(log n):

def fib(n: Int): (Int, Int) = n match {
  case 0 => (1, 1)
  case 1 => (1, 2)
  case x if x > 1 => 
    val (a,b) = fib(n / 2 - 1)
    val c = a + b
    if (n % 2 == 0) (a*a + b*b, c*c - a*a)
    else (c*c - a*a, b*b + c*c)
  case _ => throw new IllegalArgumentException("Podaj liczbę >= 0")
}

Xitami napisał(a)

    int n;
    printf("Podaj zakres: ");
    scanf("%d", &n);
    int tab[n];  // po scanf
...
    tab[0] = 0; // było 1 
 

Dobra, działa. Tylko, że ja to chciałem napisać w ANSI a tutaj warunek, że deklaracja zmiennych ma być zaraz po słowie main. Czy dobrze mówię?

camaro napisał(a)

[...]Tylko, że ja to chciałem napisać w ANSI a tutaj warunek, że deklaracja zmiennych ma być zaraz po słowie main. Czy dobrze mówię?
Nie
jeszcze inaczej

long long fibonacci(long n){
     long long i,h,j,k,t;
     i=h=1;
     j=k=0;
     while(n>0){
            if(n%2 == 1){
                   t= j*h;
                   j=  i*h + j*k +t;
                   i= i*k + t;
            }
            t=h*h;
            h=2*k*h + t;
            k=k*k + t;
            n=n/2;} 

int n = 0;
int tab[n];
int x = 2;
int i;
 
tab[0] = 1;
tab[1] = 1;

Czy tobie w ogóle się to kompiluje? A że się wywala to się nie dziwię.
Najpierw tworzysz tablicę intów o wielkości 0 "int tab[n]", a pare linijek niżej odwołujesz się do dwóch pierwszych jej elementów: tab[0], tab[1].