Significado dos números de Fibonacci
Os números de Fibonacci são uma sequência particular de inteiros positivos, começando em 0. Os números inteiros são inteiros positivos. Assim, um número de Fibonacci é uma sequência particular de números inteiros ou números naturais, começando em 0. Nessa sequência, os dois primeiros números são 0 e 1, nessa ordem. O resto dos números são desenvolvidos a partir daí, adicionando os dois números anteriores. Os primeiros doze números de Fibonacci são obtidos da seguinte forma:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Em outras palavras, os primeiros doze números de Fibonacci são:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Claro, o décimo terceiro número seria: 144 = 55 + 89. Os números de Fibonacci podem ser imaginados em uma matriz, assim:
| 0 | 1 | 1 | dois | 3 | 5 | 8 | 13 | vinte e um | 3. 4 | 55 | 89 |
Um array tem índices. Na tabela a seguir, a segunda linha mostra os índices baseados em zero correspondentes para os números de Fibonacci em uma matriz:
| 0 | 1 | 1 | dois | 3 | 5 | 8 | 13 | vinte e um | 3. 4 | 55 | 89 |
| 0 | 1 | dois | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | onze |
Com índices baseados em zero, se houver doze elementos, o último índice será 11.
Os números de Fibonacci podem ser produzidos em tempo O(n) ou em tempo O(1). Nessas expressões de complexidade de tempo, n significa n operações principais e 1 significa 1 operação principal. Com O(n), n números de Fibonacci são produzidos, começando em 0. Com O(1), um número de Fibonacci é produzido a partir do índice correspondente. É por isso que O(1) leva apenas uma operação principal em vez de n operações principais.
O objetivo deste artigo é explicar como produzir números de Fibonacci, de qualquer maneira, usando JavaScript, que na verdade é ECMAScript hoje.
Ambiente de codificação
O ambiente node.js não será usado como o leitor poderia ter previsto. Em vez disso, o navegador será usado para interpretação do código e exibição dos resultados. O script (código) deve ser escrito em um arquivo de editor de texto, que deve ser salvo com a extensão “.html”. O script deve ter como código mínimo:
DOCTYPE HTML >< html >
< cabeça >
< título > Números de Fibonacci com JavaScript título >
cabeça >
< corpo >
< tipo de script = 'texto/ecmascript' >
roteiro >
corpo >
html >
Este é um código mínimo aproximado que uma página da web precisa. Toda a codificação deste artigo fica entre as tags .
Para executar o código escrito (adicionado), basta clicar duas vezes no ícone do nome do arquivo e o navegador do computador o abrirá.
Definição de um número de Fibonacci
Existe uma definição matemática para um número de Fibonacci. Ele é definido da seguinte forma:
Onde Fn é um número de Fibonacci correspondente a um índice baseado em zero, n.
Os dois primeiros números: 0 e 1, são pré-declarados, nessa ordem. A última linha desta função mostra como o resto dos números se originam dos dois primeiros números em sua ordem.
Esta definição também é uma das fórmulas para o número de Fibonacci.
Produzindo Números de Fibonacci em Tempo O(n)
Se n for 1, apenas 0 será exibido como um número de Fibonacci. Se n for 2, então 0 e 1 seriam exibidos como números de Fibonacci, nessa ordem. Se n for 3, então 0, 1 e 1 serão exibidos como números de Fibonacci nessa ordem. Se n for 4, então 0, 1, 1 e 2 seriam exibidos como números de Fibonacci, nessa ordem. Se n for 5, então 0, 1, 1, 2 e 3 seriam exibidos como números de Fibonacci, nessa ordem. Se n for 6, então 0, 1, 1, 2, 3 e 5 seriam exibidos como números de Fibonacci, nessa ordem – e assim por diante.
A função ECMAscript para gerar os primeiros n inteiros de Fibonacci (números) é:
< tipo de script = 'texto/ecmascript' >função fibonacci ( UMA ) {
n = UMA. comprimento ;
E se ( n > 0 )
UMA [ 0 ] = 0 ;
E se ( n > 1 )
UMA [ 1 ] = 1 ;
por ( eu = dois ; eu < n ; eu ++ ) { //n=0 e n=2 foram considerados
atual Não = UMA [ eu - 1 ] + UMA [ eu - dois ] ;
UMA [ eu ] = atual Não ;
}
}
A tag de script de fechamento não foi mostrada. A função recebe um array. Os dois primeiros números de Fibonacci são atribuídos em sua posição. O loop for itera do índice baseado em zero, 2 até um pouco abaixo de n. A declaração mais importante no loop for é:
currNo = A[i – 1] + A[i – 2];
Isso adiciona os dois números anteriores imediatos na matriz para ter o número atual. Quando a função fibonacci() termina de ser executada, todos os elementos do array são os primeiros n números de Fibonacci. Um código adequado para chamar a função fibonacci() e exibir os números de Fibonacci é:
N = 12 ;arr = novo Variedade ( N ) ;
fibonacci ( arr ) ;
por ( eu = 0 ; eu < N ; eu ++ )
documento. Escreva ( arr [ eu ] + ' ' ) ;
documento. Escreva ( '
' ) ;
roteiro >
Este código mostra a tag de script de fechamento. O código é digitado abaixo do código acima. A saída exibida na página da web é:
0 1 1 2 3 5 8 13 21 34 55 89
como esperado.
Produzindo um número de Fibonacci em tempo O(1)
O(1) é tempo constante. Refere-se a uma operação principal. Outra fórmula matemática para produzir um número de Fibonacci é:
Observe que no lado direito da equação, não é a raiz quadrada de 5 que é elevada à potência n; é a expressão entre parênteses que é elevada à potência n. Existem duas dessas expressões.
Se n for 0, Fibn seria 0. Se n for 1, Fibn seria 1. Se n for 2, Fibn seria 1. Se n for 3, Fibn seria 2. Se n for 4, Fibn seria 3 – e assim por diante. O leitor pode verificar matematicamente essa fórmula substituindo valores diferentes por n e avaliando. n é um índice baseado em zero nesta fórmula. O resultado é o número de Fibonacci correspondente.
O código ECMAScript (JavaScript) para esta fórmula é:
< tipo de script = 'texto/ecmascript' >função fibNo ( n ) {
FibN = ( Matemática . Pancada ( ( 1 + Matemática . quadrado ( 5 ) ) / dois , n ) - Matemática . Pancada ( ( 1 - Matemática . quadrado ( 5 ) ) / dois , n ) ) / Matemática . quadrado ( 5 ) ;
Retorna FibN ;
}
A tag de script de fechamento não foi mostrada. Observe como as funções predefinidas de potência (pow) e raiz quadrada (sqrt) foram usadas. Em ECMAScript (JavaScript), o módulo Math não precisa ser importado. A função fibNo() implementa a fórmula diretamente. Uma chamada e exibição adequadas para a função fibNo() na página da web são:
N = onze ;certo = fibNo ( N ) ;
documento. Escreva ( certo ) ;
roteiro >
O código mostra a tag de script de fechamento. A saída é:
89.00000000000003
É possível remover os dígitos decimais desnecessários da resposta. No entanto, isso é uma discussão para outro momento.
Se for necessário mais de um número de Fibonacci, o código deve chamar a fórmula uma vez para cada índice n correspondente baseado em zero.
Conclusão
Os números de Fibonacci são uma sequência particular de inteiros positivos, começando em 0. Os números inteiros são inteiros positivos. Assim, um número de Fibonacci é uma sequência particular de números inteiros ou números naturais, começando em 0. Nessa sequência, os dois primeiros números são 0 e 1, nessa ordem. Esses dois primeiros números são apenas definidos como tal. O resto dos números são desenvolvidos a partir daí, adicionando os dois números anteriores imediatos.
Depois de produzir os dois primeiros números de Fibonacci, para produzir o restante dos números de Fibonacci, para terminar com um total de n números, um loop for deve ser usado com a instrução:
currNo = A[i – 1] + A[i – 2];
Isso adiciona os dois últimos números de Fibonacci imediatos para ter o número de Fibonacci atual.
Quando dado um índice baseado em zero, para ter o número de Fibonacci correspondente, use a fórmula:
