Na verdade, os dois primeiros números de Fibonacci são predefinidos. O primeiro número de Fibonacci é 0 e o segundo número de Fibonacci é 1. Com indexação baseada em zero e assumindo que os números de Fibonacci estão em uma matriz, então:
no índice 0 , o número de Fibonacci é 0 , ( predefinido ) ;no índice 1 , o número de Fibonacci é 1 , ( predefinido ) ;
no índice dois , o número de Fibonacci é 1 = 1 + 0 , ( por definição ) ;
no índice 3 , o número de Fibonacci é dois = 1 + 1 , ( por definição ) ;
no índice 4 , o número de Fibonacci é 3 = dois + 1 , ( por definição ) ;
no índice 5 , o número de Fibonacci é 5 = 3 + dois , ( por definição ) ;
no índice 6 , o número de Fibonacci é 8 = 5 + 3 , ( por definição ) ;
no índice 7 , o número de Fibonacci é 13 = 8 + 5 , ( por definição ) ;
no índice 8 , o número de Fibonacci é vinte e um = 13 + 8 , ( por definição ) ;
no índice 9 , o número de Fibonacci é 3. 4 = vinte e um + 13 , ( por definição ) ;
e assim por diante.
Na programação, a variável n e not i é usada para os índices baseados em zero para esses números de Fibonacci. E com isso, os primeiros doze números de Fibonacci são:
| 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 |
A segunda linha da tabela fornece os índices baseados em zero, cada um dos quais teria a variável n na programação. A primeira linha fornece os números de Fibonacci correspondentes. Portanto, os números de Fibonacci não são apenas quaisquer números. A definição principal começa com 0, para o primeiro número de Fibonacci e 1 para o segundo número de Fibonacci. O resto dos números são produzidos a partir daí.
Os números de Fibonacci podem ser produzidos em tempo O(n) e também em tempo O(1). Para o tempo O(n), se n for 12, por exemplo, os primeiros doze números de Fibonacci seriam produzidos. Para o tempo O(1), apenas um número de Fibonacci é produzido. Por exemplo, se n é 6, então o número de Fibonacci 8 seria produzido.
Este artigo explica essas duas maneiras de produzir números de Fibonacci em Java.
Fórmula para um número de Fibonacci
Existe uma fórmula matemática para um número de Fibonacci. Esta fórmula pode ser escrita em três linhas ou uma linha. Em três linhas, está escrito como:
onde F n é o número de Fibonacci no n baseado em zero º índice. É assim que o número de Fibonacci é definido.
Produzindo Números de Fibonacci em Tempo O(n)
Se os números de Fibonacci fossem produzidos em O(3) vezes, os números 0, 1, 1 seriam produzidos; esses são os três primeiros números de Fibonacci. O último n baseado em zero º o índice aqui é 2. Se os números de Fibonacci forem produzidos em O(7) vezes, os números 0, 1, 1, 2, 3, 5, 8 seriam produzidos; esses são os primeiros sete números de Fibonacci. O último n baseado em zero º índice aqui, é 6. Se os números de Fibonacci forem produzidos em O(n) vezes, os números, 0, 1, 1, 2, 3, 5, 8 – – -, seriam produzidos; esses são os primeiros n números de Fibonacci. O último n baseado em zero º índice aqui é n-1.
O método Java em uma classe para produzir os primeiros n números de Fibonacci é:
classe Fibonacci {vazio fibonacci ( int [ ] P ) {
int n = P. comprimento ;
E se ( n > 0 )
P [ 0 ] = 0 ;
E se ( n > 1 )
P [ 1 ] = 1 ;
por ( int eu = dois ; eu < n ; eu ++ ) { //n=0 e n=2 foram considerados
int atual Não = P [ eu - 1 ] + P [ eu - dois ] ;
P [ eu ] = atual Não ;
}
}
}
A classe Fibonacci é privada. o fibonacci() O método pega o array P e retorna void. O método começa determinando o comprimento da matriz. Este comprimento de n é o número de números de Fibonacci necessários. O primeiro e o segundo números de Fibonacci são determinados explicitamente e colocados nas primeiras e segundas posições na matriz.
O resto dos números de Fibonacci a partir do terceiro (índice, n = 2) são determinados em um loop for e colocados em suas posições na matriz. Portanto, a função deve retornar void. A instrução principal no loop for adiciona os dois números anteriores.
A variável de índice, i, foi usada em vez de n, para fins de clareza.
Uma classe Java Main adequada (com o método Java main) é:
público classe Principal {público estático vazio a Principal ( Corda argumentos [ ] ) {
int m = 12 ;
int [ ] arr = novo int [ m ] ;
Fibonacci obj = novo Fibonacci ( ) ;
obj. fibonacci ( arr ) ;
por ( int eu = 0 ; eu < m ; eu ++ )
Sistema . Fora . imprimir ( arr [ eu ] + ' ' ) ;
Sistema . Fora . imprimir ( ) ;
}
}
Depois que os números foram produzidos pelo método fibonacci(), o método principal do Java os lê.
Produzindo um número de Fibonacci em tempo constante
Existe uma fórmula matemática que pode ser usada para produzir um número de Fibonacci, quando dado o índice baseado em zero correspondente, n. A fórmula é:
onde n é o índice baseado em zero e Fib n é o número de Fibonacci correspondente. 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 é 0, Fib n seria 0. Se n é 1, Fib n seria 1. Se n é 2, Fib n seria 1. Se n é 3, Fib n seria 2. Se n é 4, Fib n seria 3 - e assim por diante. O leitor pode verificar essa fórmula matematicamente, substituindo valores diferentes por n e avaliando.
Quando codificada, essa fórmula produziria apenas um número de Fibonacci para n. Se mais de um número de Fibonacci for necessário, o código da fórmula deve ser chamado uma vez para cada um dos diferentes índices correspondentes.
Em Java, o método para produzir apenas um número de Fibonacci é:
importar java.lang.* ;classe Fib {
em dobro fibNo ( int n ) {
em dobro 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 ;
}
}
O pacote java.lang.* teve que ser importado no início do programa. Isso ocorre porque o pacote possui a classe Math, que possui os métodos power (pow) e raiz quadrada (sqrt). O método Java personalizado aqui implementa a fórmula matemática diretamente.
A complexidade de tempo para esta função é O(1), constante de uma operação principal. Uma classe Java Main adequada, com o método Java main para o método acima é:
público classe Principal {público estático vazio a Principal ( Corda argumentos [ ] ) {
int N = onze ;
Fib obj = novo Fib ( ) ;
em dobro certo = obj. fibNo ( N ) ;
Sistema . Fora . imprimir ( certo ) ;
}
}
O índice n = 11 é enviado e o número de Fibonacci, 89, é retornado. A saída é:
89.00000000000003Os dígitos decimais desnecessários podem ser removidos, mas isso é uma discussão para outro momento.
Conclusão
Os números de Fibonacci são uma sequência particular de números inteiros. Para obter o número atual, adicione os dois números correspondentes imediatamente anteriores. Os dois primeiros números de Fibonacci, 0 seguido de 1, são pré-declarados, para toda a sequência. O resto dos números de Fibonacci são produzidos a partir daí.
Para produzir números de Fibonacci do índice 2, para aquele que corresponde ao índice n-1, use um loop for com a instrução principal:
int atual Não = P [ eu - 1 ] + P [ eu - dois ] ;onde currNo é o número atual de Fibonacci e P é a matriz para armazenar os n números.
Para produzir apenas um número de Fibonacci de qualquer índice baseado em zero n, use a fórmula matemática:
