Numeri di fibonacci in lingua C

“Sia n essere 0. Il numero di fibonacci per 0 è:

0

Sia n 1. Il numero di fibonacci per 1 è:

1

Sia N 2. Il numero di fibonacci per 2 è:

1 + 0 = 1

Sia N 3. Il numero di fibonacci per 3 è:

1 + 1 = 2

Sia N 4. Il numero di fibonacci per 4 è:

2 + 1 = 3

Sia N 5. Il numero di fibonacci per 5 è:

3 + 2 = 5

Sia N 6. Il numero di fibonacci per 6 è:

5 + 3 = 8

Sia N 7. Il numero di fibonacci per 7 è:

8 + 5 = 13

Sia N 8. Il numero di fibonacci per 8 è:

13 + 8 = 21

Sia N 9. Il numero di fibonacci per 9 è:

21 + 13 = 34

La tabella seguente mostra i primi dodici numeri Fibonacci:

La prima riga fornisce i numeri di Fibonacci. La seconda riga fornisce gli indici a base zero per l'array corrispondente. Questi indici sono i diversi num interi N, a partire da zero. Si può vedere dalla tabella che il decimo numero di fibonacci è 34 + 21 = 55. Inoltre, l'undicesimo numero di fibonacci è, 55 + 34 = 89 .

Lo scopo di questo articolo è quello di produrre un numero di fibonacci in o (n) tempo e nel tempo costante o (1), usando il linguaggio del computer c.

I numeri di Fibonacci sono numeri interi, a partire da 0."

La formula per un numero di fibonacci

Come visto dalla tabella sopra, il numero di fibonacci corrente è la somma dei due numeri precedenti. Il numero di fibonacci per 0 è 0 e il numero di fibonacci per 1 è 1. Questi primi due numeri, nel loro ordine, devono essere accettati come tali. Sviluppare i seguenti numeri di fibonacci, iniziare da lì, per dare 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3, ecc.

La formula per un particolare numero di fibonacci può essere fornita in tre righe o una riga. La formula in tre righe è data come segue:

Questa formula è la definizione di un numero di fibonacci.

Producendo numeri di fibonacci in o (n) tempo

Più di un numero di fibonacci può essere prodotto a partire da zero per un determinato valore di n. In questo caso, n è l'indice più alto più 1 per l'array - assumere indicizzazione a base zero. Viene prodotto il numero di fibonacci per i = 0 (i.E 0). Viene quindi prodotto il numero di fibonacci per i = 1 (i.e., 1). Il numero di fibonacci per i = 2 viene quindi prodotto dopo (i.e., 1 di nuovo). Viene quindi prodotto il numero di fibonacci per i = 3 (i.e., 2). Viene quindi prodotto il numero di fibonacci per i = 4 (i.e., 3). Ciò continua fino a quando viene prodotto il numero di Fibonacci per il numero dato (indice) di N, diciamo 12, per il più alto indice di 11.

Un programma C che prende input dalla tastiera e lo supera al terminale (schermo) inizia con:

#includere

Con questa direttiva pre-elaborazione, lo schermo verrà visualizzato il testo sulla tastiera. L'output del programma apparirà anche sullo schermo. La funzione Fibonacci è:

void fibonacci (int a [], int n)
if (n> 0)
A [0] = 0;
if (n> 1)
A [1] = 1;
per (int i = 2; iint nextNo = a [i - 1] + a [i - 2];
A [i] = nextno;

Le prime due dichiarazioni nella funzione sono considerate due operazioni. Il corpo del per loop può essere considerato come un'operazione. Se n è 12, il corpo del per loop funziona 10 volte perché la prima e la seconda operazione, per l'indice 0 e l'indice 1, hanno già avuto luogo. Questo dà una complessità temporale di O (12), scritta come O (N).

Nota la dichiarazione:

int nextNo = a [i - 1] + a [i - 2];

Nel corpo del per loop. Aggiunge i due precedenti numeri di Fibonacci per ottenere il numero di fibonacci corrente (NextNo).

Una funzione principale C idonea per il programma di cui sopra è:

int main (int argc, char ** argv)

int n = 12;
int arr [12];
fibonacci (arr, n);
per (int i = 0; iprintf ("%i", arr [i]);
printf ("\ n");
restituzione 0;

Producendo un numero di fibonacci in tempo costante

Sopra, l'indice per il numero di Fibonacci, 89, è 11 e non 12, per indicizzazione a base zero. Lascia che 11 sia n. In questo caso, l'attuale numero di fibonacci è 89. Se n è 10, il numero di fibonacci corrente sarebbe 55. Se n è 9, l'attuale numero di fibonacci sarebbe 34. Questo continua verso il basso fino a quando N è 0, il numero di fibonacci sarebbe 0.

Esiste una formula matematica per ottenere il numero di fibonacci corrente (uno), dato l'indice (numero) basato a zero, con il nome variabile n. La formula è:

Si noti che sul lato destro dell'equazione, non è la radice quadrata di 5 che viene sollevata al potere n; è l'espressione tra parentesi che viene sollevata al potere n. Ci sono due di queste espressioni.

Quindi, quando n è 0, FIB_N sarà 0. Quando n è 1, FIB_N sarà 1. Quando n è 2, FIB_N sarà 1. Quando n è 3, FIB_N sarà 2 - e così via.

Questa funzione matematica è un'operazione principale e restituisce solo un numero di fibonacci e non una sequenza di numeri corrispondenti, diciamo, indice da 0 a indice 11. Questo è un codice temporale costante. Può ancora essere usato per produrre una sequenza di numeri di fibonacci semplicemente chiamandolo più e più volte con valori diversi di N, come indici, in un programma.

La complessità temporale per questa funzione matematica per produrre il suo numero di fibonacci è O (1), tempo costante.

Ora, questa funzione matematica è codificata di seguito per produrre 12 numeri Fibonacci. Userebbe meno tempo complessivo rispetto al precedente algoritmo.

Il codice per questa funzione matematica per produrre il suo numero di fibonacci è:

#includere
#includere
Double fibno (int n)
Double Fibn = (pow ((1+sqrt (5))/2, n) - pow ((1 -sqrt (5))/2, n))/sqrt (5);
restituire fibn;

Nota che la matematica.La libreria H è inclusa questa volta, che porta al programma le funzioni predefinite di Power (Pow) e Square Root (SQRT). La funzione produce solo un numero di fibonacci e non una sequenza di essi. Una funzione principale adatta per questo codice è:

int main (int argc, char ** argv)

int n = 11;
doppio fibn = fibno (n);
printf ("%lf \ n", fibn);
restituzione 0;

Con un indice di 11, l'output è 89.000000. Tuttavia, per eseguire questo programma con il compilatore GCC, utilizzare una riga di comando come:

GCC TEMP.c -o temp -lm

dove “temp.C "è il codice sorgente e" temp "è il programma compilato. Nota l'uso dell'interruttore, "-lm", dove "L" è minuscolo L.

Conclusione

Il primo numero di fibonacci è 0. Il secondo numero di fibonacci è 1. Il resto viene ottenuto aggiungendo i precedenti due numeri di fibonacci. I numeri di fibonacci sono numeri interi. Per ottenere la sequenza di numeri di fibonacci da zero in o (n) tempo, utilizzare una funzione con un'istruzione come:

int nextNo = a [i - 1] + a [i - 2];

Dove NextNo è il numero corrente per l'indice I e "A" è l'array per contenere i numeri di sequenza Fibonacci. I primi due numeri, 0 e 1, sono prodotti in modo indipendente.

Per ottenere un solo numero di fibonacci in o (1) tempo, usa la formula matematica:

dove n è l'indice basato su zero.

I numeri di fibonacci possono essere ottenuti usando matrici matematiche. Tuttavia, questa è una discussione per qualche altra volta.