Números de fibonacci na linguagem Java
De fato, 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 a 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 2, o número de fibonacci é 1 = 1 + 0, (por definição);
No índice 3, o número de fibonacci é 2 = 1 + 1, (por definição);
No índice 4, o número de Fibonacci é 3 = 2 + 1, (por definição);
No índice 5, o número de Fibonacci é 5 = 3 + 2, (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 é 21 = 13 + 8, (por definição);
No índice 9, o número de Fibonacci é 34 = 21 + 13, (por definição);
e assim por diante.
Na programação, a variável n, e não eu é 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 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
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. Então, os números de fibonacci não são apenas 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 restante dos números é produzido a partir daí.
Os números de Fibonacci podem ser produzidos no tempo O (n) e também no tempo O (1). Por o (n) tempo, se n é 12 por exemplo, os primeiros doze números de fibonacci seriam produzidos. Por O (1) tempo, apenas um número de Fibonacci é produzido. Por exemplo, se n for 6, então o Fibonacci número 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 fn é o número de Fibonacci no N baseado em zeroº índice. É assim que o número de fibonacci é definido.
Produzindo números de fibonacci no tempo O (n)
Se os números de Fibonacci forem 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º Í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 sete primeiros números de Fibonacci. O último n baseado em zeroº Índice aqui é 6. Se os números de Fibonacci forem produzidos em 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 fibonaccivoid fibonacci (int [] p)
int n = p.comprimento;
se (n> 0)
P [0] = 0;
se (n> 1)
P [1] = 1;
para (int i = 2; i
P [i] = currno;
A classe, Fibonacci é privada. O Fibonacci () Método leva a matriz 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úmero de Fibonacci são determinados explicitamente e colocados na primeira e segunda posições na matriz.
O restante dos números de Fibonacci, a partir do terceiro (índice, n = 2), é determinado em um loop for e colocado em suas posições na matriz. Então, a função tem que retornar vazio. A declaração principal no loop for acrescenta os dois números anteriores.
A variável de índice, i, foi usada em vez de n, para fins de clareza.
Uma classe principal Java adequada (com o método principal Java) é:
classe pública principalpublic static void main (string args [])
int m = 12;
int [] arr = new int [m];
Fibonacci obj = new fibonacci ();
obj.Fibonacci (arr);
para (int i = 0; i
Sistema.fora.println ();
Depois que os números foram produzidos pelo método fibonacci (), o método principal 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 recebe o índice zero correspondente, n. A fórmula é:
onde n é o índice baseado em zero e fibn é o número de fibonacci correspondente. 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.
Se n é 0, fibn seria 0. Se n é 1, fibn seria 1. Se n é 2, fibn seria 1. Se n é 3, fibn seria 2. Se n é 4, fibn seria 3 - e assim por diante. O leitor pode verificar essa fórmula matematicamente, substituindo diferentes valores por n e avaliando.
Quando codificado, 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 para a 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
Fibno duplo (int n)
duplo fibn = (matemática.Pow ((1+matemática.sqrt (5))/2, n) -math.Pow ((1-math.sqrt (5)) / 2, n)) / matemática.sqrt (5);
retornar fibn;
O java.Lang.* O pacote teve que ser importado no início do programa. Isso ocorre porque o pacote possui a classe de matemática, que possui os métodos Power (POW) e raiz quadrada (SQRT). O método Java personalizado aqui implementa diretamente a fórmula matemática.
A complexidade do tempo para esta função é O (1), manso constante de uma operação principal. Uma classe principal Java adequada, com o método principal Java para o método acima é:
classe pública principalpublic static void main (string args [])
int n = 11;
Fib obj = new fib ();
duplo ret = obj.fibno (n);
Sistema.fora.println (ret);
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 algum outro momento.
Conclusão
Os números de Fibonacci são uma sequência específica de números inteiros. Para obter o número atual, adicione os dois números anteriores imediatos. Os dois primeiros números de Fibonacci, 0 seguidos por 1, são pré-declarados, para toda a sequência. O restante dos números de Fibonacci é produzido a partir daí.
Para produzir números de Fibonacci a partir do índice 2, para o que corresponde ao índice N-1, use um loop para a declaração principal:
int currno = p [i - 1] + p [i - 2];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 a partir de qualquer índice baseado em zero, use a fórmula matemática: