Serie di Fibonacci

Si risolva il seguente problema: sia dato da tastiera un numero intero n. Calcolare i valori della serie di Fibonacci fino all' n-esimo elemento, e memorizzarli in un vettore. La serie di Fibonacci è caratterizzata cosí: i primi due elementi della serie valgono 1. Ogni successivo elemento della serie si ottiene sommando i due precedenti elementi.

Il problema si risolve leggendo il numero n da tastiera, e allocando un vettore di n elementi interi. I primi due elementi della serie devono valere 1, e mettiamo 1 nei primi due elementi del vettore. Per calcolare i valori successivi, facciamo un ciclo che parte da 2 e arriva al valore di n meno uno (infatti, per memorizzare n valori, usiamo gli indici da 0 a n-1. Per ognuno di questi indici, l'elemento del vettore si calcola semplicemente sommando i due elementi precedenti.

Questo è il programma completo fibonacci.c

/*
  Calcola gli elementi della serie di
Fibonacci e li mette in un vettore.
*/

#include<stdlib.h>

int main() {
  int *fib;
  int n;
  int i;


		/* lettura del valore di n */
  scanf("%d", &n);


		/* allocazione vettore */
  fib=malloc(n*sizeof(int));


		/* calcolo serie */
  fib[0]=1;
  fib[1]=1;

  for(i=2; i<=n-1; i++) 
    fib[i]=fib[i-1]+fib[i-2];


		/* stampa serie */
  for(i=0; i<=n-1; i++)
    printf("%d\n", fib[i]);

  return 0;
}

Consideriamo ora la seguente variante: il numero letto da tastiera non indica più il numero di elementi da calcolare, ma il massimo valore che ci interessa. In altre parole, leggiamo un numero intero max da tastiera, e il ciclo di calcolo degli elementi della serie si interrompe quando si trova un valore che supera max. Detto in un altro modo ancora: quando fib[n] supera max si esce dal ciclo.

In questo caso, non sappiamo in partenza quanti elementi servono per memorizzare tutta la serie. Infatti, il numero max non è il massimo indice del vettore. Il massimo indice si può trovare solo dopo aver calcolato tutti gli elementi fino a quello che supera max.

Risolviamo il problema facendo una allocazione iniziale di dieci elementi. Se a un certo punto ci rendiamo conto che non sono sufficienti per memorizzare tutto l'array, facciamo una riallocazione con realloc. Dal momento che non sappiamo quante iterazioni sono necessarie, usiamo un ciclo while. All'interno di questo ciclo facciamo il calcolo di un elemento del vettore, e incrementiamo il valore della variabile n che ci dà l'indice dell'elemento che stiamo calcolando. Se questo numero raggiunge la dimensione del vettore (numero di elementi correntemente allocati), allora vuol dire che il prossimo elemento che verrà calcolato sarà fuori dalla zona di memoria allocata, per cui dobbiamo fare un riallocazione.

Di seguito si riporta il programma completo refib.c

/*
  Calcola gli elementi della serie di
Fibonacci e li mette in un vettore.
Riallocazione del vettore.
*/

#include<stdlib.h>

int main() {
  int dim;
  int *fib;

  int max;
  int n;
  int i;


		/* lettura del valore di n */
  scanf("%d", &max);


		/* allocazione vettore */
  dim=10;
  fib=malloc(dim*sizeof(int));


		/* calcolo serie */
  fib[0]=1;
  fib[1]=1;

  n=1;
  while(fib[n]<max) {
    n++;		/* nuovo indice */

    if(n>=dim) {	/* se il vettore non basta, rialloca */
      dim+=10;
      fib=realloc(fib, dim*sizeof(int));
    }

    fib[n]=fib[n-1]+fib[n-2];	/* calcolo elemento */
  }


		/* stampa serie */
  for(i=0; i<=n-1; i++)
    printf("%d\n", fib[i]);

  return 0;
}