Números de fibonacci na linguagem C

“Seja n 0. O número de Fibonacci para 0 é:

0

Seja n 1. O número de Fibonacci para 1 é:

1

Seja n 2. O número de Fibonacci para 2 é:

1 + 0 = 1

Seja n 3. O número de Fibonacci para 3 é:

1 + 1 = 2

Seja n 4. O número de Fibonacci para 4 é:

2 + 1 = 3

Seja N 5. O número de Fibonacci para 5 é:

3 + 2 = 5

Seja n 6. O número de Fibonacci para 6 é:

5 + 3 = 8

Seja n 7. O número de Fibonacci para 7 é:

8 + 5 = 13

Seja n 8. O número de Fibonacci para 8 é:

13 + 8 = 21

Seja N 9. O número de Fibonacci para 9 é:

21 + 13 = 34

A tabela a seguir mostra os primeiros doze números de Fibonacci:

A primeira linha dá os números de Fibonacci. A segunda linha fornece os índices baseados em zero para a matriz correspondente. Esses índices são os diferentes inteiros N, começando de zero. Pode ser visto da tabela que o décimo número de Fibonacci é 34 + 21 = 55. Além disso, o primeiro número de Fibonacci é, 55 + 34 = 89 .

O objetivo deste artigo é produzir um número de fibonacci no tempo O (n) e em tempo constante o (1), usando a linguagem do computador C.

Os números de fibonacci são inteiros, começando de 0.”

A fórmula para um número de fibonacci

Como visto na tabela acima, o número atual de fibonacci é a soma dos dois números anteriores. O número de fibonacci para 0 é 0, e o número de fibonacci para 1 é 1. Esses dois primeiros números, em sua ordem, devem ser aceitos como tal. Desenvolvendo os seguintes números de Fibonacci, comece a partir daí, para dar 1 + 0 = 1; 1 + 1 = 2; 2 + 1 = 3, etc.

A fórmula para um determinado número de fibonacci pode ser fornecido em três linhas ou uma linha. A fórmula em três linhas é dada da seguinte forma:

Esta fórmula é a definição de um número de fibonacci.

Produzindo números de fibonacci no tempo O (n)

Mais de um número de fibonacci pode ser produzido a partir de zero para um determinado valor de n. Nesse caso, n é o maior índice mais 1 para a matriz - assuma a indexação baseada em zero. O número de fibonacci para i = 0 é produzido (i.e 0). O número de fibonacci para i = 1 é então produzido (i.e., 1). O número de fibonacci para i = 2 é produzido em seguida (i.e., 1 novamente). O número de fibonacci para i = 3 é então produzido (i.e., 2). O número de fibonacci para i = 4 é então produzido (i.e., 3). Isso continua até que o número de Fibonacci para o número fornecido (índice) de n, digamos 12, para o maior índice de 11, seja produzido (89).

Um programa C que retira a entrada do teclado e o produz para o terminal (tela) começa com:

#incluir

Com esta diretiva de pré-processamento, o texto digitado no teclado aparecerá na tela. A saída do programa também aparecerá na tela. A função Fibonacci é:

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

As duas primeiras declarações da função são consideradas como duas operações. O corpo do loop for considerado como uma operação. Se n é 12, então o corpo do loop for 10 vezes porque a primeira e a segunda operações, para o índice e o índice 1, já ocorreram. Isso dá uma complexidade de tempo de O (12), escrita como O (n).

Observe a declaração:

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

No corpo do loop for. Ele adiciona os dois números de Fibonacci anteriores para obter o número atual de Fibonacci (Nextno).

Uma função principal C adequada para o programa acima é:

int main (int argc, char ** argv)

int n = 12;
int arr [12];
Fibonacci (arr, n);
para (int i = 0; iprintf ("%i", arr [i]);
printf ("\ n");
retornar 0;

Produzindo um número de fibonacci em tempo constante

Acima, o índice para o número de Fibonacci, 89, é 11, e não 12, para indexação baseada em zero. Seja 11 n. Nesse caso, o número atual de Fibonacci é 89. Se n for 10, o número atual de fibonacci seria 55. Se n for 9, o número atual de fibonacci seria 34. Isso continua para baixo até que n for 0, o número de fibonacci seria 0.

Existe uma fórmula matemática para obter o número atual de fibonacci, dado o índice baseado em zero (número), com o nome da variável n. A fórmula é:

Observe que, no lado direito da equação, não é a raiz quadrada de 5 que é elevada ao poder n; É a expressão entre parênteses que é elevada ao poder n. Existem duas dessas expressões.

Então, quando n é 0, fib_n será 0. Quando n é 1, fib_n será 1. Quando n é 2, fib_n será 1. Quando n é 3, fib_n será 2 - e assim por diante.

Essa função matemática é uma operação principal e retorna apenas um número de Fibonacci e não uma sequência de números correspondentes a, digamos, índice 0 ao índice 11. Este é um código de tempo constante. Ainda pode ser usado para produzir uma sequência de números de Fibonacci, apenas chamando -o repetidamente com diferentes valores de n, como índices, em um programa.

A complexidade do tempo para essa função matemática para produzir seu número de fibonacci é O (1), tempo constante.

Agora, essa função matemática é codificada abaixo para produzir 12 números de Fibonacci. Usaria menos tempo total do que o algoritmo anterior.

O código para esta função matemática para produzir seu número de fibonacci é:

#incluir
#incluir
Fibno duplo (int n)
fibn duplo = (pow ((1+sqrt (5))/2, n) - pow ((1 -sqrt (5))/2, n))/sqrt (5);
retornar fibn;

Observe que a matemática.A biblioteca H está incluída desta vez, que traz funções predefinidas do poder (POW) e da raiz quadrada (SQRT) para o programa. A função produz apenas um número de fibonacci e não uma sequência deles. Uma função principal adequada para este código é:

int main (int argc, char ** argv)

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

Com um índice de 11, a saída é 89.000000. No entanto, para executar este programa com o compilador GCC, use uma linha de comando como:

GCC Temp.c -o temp -lm

onde “Temp.C ”é o código -fonte e“ Temp ”é o programa compilado. Observe o uso do interruptor, "-lm", onde "l" é minúsculo l.

Conclusão

O primeiro número de fibonacci é 0. O segundo número de fibonacci é 1. O resto é obtido adicionando os dois números anteriores de Fibonacci. Os números de Fibonacci são inteiros. Para obter a sequência de números de Fibonacci de zero no tempo O (n), use uma função com uma declaração como:

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

Onde Nextno é o número atual do índice I, e "A" é a matriz para segurar os números de sequência de Fibonacci. Os dois primeiros números, 0 e 1, são produzidos de forma independente.

Para obter apenas um número de Fibonacci no tempo O (1), use a fórmula matemática:

onde n é o índice baseado em zero.

Os números de fibonacci podem ser obtidos usando matrizes matemáticas. No entanto, esta é uma discussão para algum outro momento.