Numeri di fibonacci in lingua Java
In effetti, i primi due numeri di Fibonacci sono predefiniti. Il primo numero di fibonacci è 0 e il secondo numero di fibonacci è 1. Con indicizzazione basata su zero e assumere che i numeri di Fibonacci siano in un array, quindi:
All'indice 0, il numero di Fibonacci è 0, (predefinito);All'indice 1, il numero di Fibonacci è 1, (predefinito);
All'indice 2, il numero di fibonacci è 1 = 1 + 0, (per definizione);
All'indice 3, il numero di fibonacci è 2 = 1 + 1, (per definizione);
All'indice 4, il numero di fibonacci è 3 = 2 + 1, (per definizione);
All'indice 5, il numero di Fibonacci è 5 = 3 + 2, (per definizione);
All'indice 6, il numero di Fibonacci è 8 = 5 + 3, (per definizione);
All'indice 7, il numero di Fibonacci è 13 = 8 + 5, (per definizione);
All'indice 8, il numero di Fibonacci è 21 = 13 + 8, (per definizione);
All'indice 9, il numero di Fibonacci è 34 = 21 + 13, (per definizione);
e così via.
Nella programmazione, la variabile N e non i viene utilizzata per gli indici a base zero per questi numeri di fibonacci. E con ciò, i primi dodici numeri di Fibonacci sono:
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
La seconda riga nella tabella fornisce gli indici a base zero, ognuno dei quali avrebbe la variabile N nella programmazione. La prima riga fornisce i corrispondenti numeri di fibonacci. Quindi, i numeri di Fibonacci non sono solo numeri. La definizione principale inizia con 0, per il primo numero di fibonacci e 1 per il secondo numero di fibonacci. Il resto dei numeri è prodotto da lì.
I numeri di Fibonacci possono essere prodotti nel tempo di O (n) e anche in O (1). Per o (n) tempo, se n è 12 per esempio, verranno prodotti i primi dodici numeri di fibonacci. Per o (1) tempo, viene prodotto un solo numero di fibonacci. Ad esempio, se n è 6, allora il fibonacci numero 8 sarebbe prodotto.
Questo articolo spiega questi due modi di produrre numeri di fibonacci in Java.
Formula per un numero di fibonacci
C'è una formula matematica per un numero di fibonacci. Questa formula può essere scritta in tre righe o una riga. In tre righe, è scritto come:
dove fN è il numero di fibonacci al n basato sullo zeroth indice. Ecco come viene definito il numero di fibonacci.
Producendo numeri di fibonacci in o (n) tempo
Se i numeri di Fibonacci devono essere prodotti in O (3) volte, i numeri, 0, 1, 1 verrebbero prodotti; Questi sono i primi tre numeri di fibonacci. L'ultimo n a base di zeroth indice qui, è 2. Se i numeri di fibonacci devono essere prodotti in O (7) volte, i numeri, 0, 1, 1, 2, 3, 5, 8 sarebbero prodotti; Questi sono i primi sette numeri di fibonacci. L'ultimo n a base di zeroth indice qui, è 6. Se i numeri di fibonacci devono essere prodotti in o (n) tempi, i numeri, 0, 1, 1, 2, 3, 5, 8 - - - - sarebbero prodotti; Quelli sono i primi numeri di n fibonacci. L'ultimo n a base di zeroth L'indice qui è N-1.
Il metodo Java in una classe per produrre i primi numeri N Fibonacci è:
class fibonaccivoid fibonacci (int [] p)
int n = p.lunghezza;
if (n> 0)
P [0] = 0;
if (n> 1)
P [1] = 1;
per (int i = 2; i
P [i] = Currno;
La classe, Fibonacci è privata. IL fibonacci () Il metodo prende l'array P e restituisce vuoto. Il metodo inizia determinando la lunghezza dell'array. Questa lunghezza di n è il numero di numeri di fibonacci richiesti. Il primo e il secondo numero di fibonacci sono determinati esplicitamente e messi nella prima e nelle seconde posizioni nell'array.
Il resto dei numeri di Fibonacci che inizia dal terzo (indice, n = 2) è determinato in un per loop e messo nelle loro posizioni nell'array. Quindi, la funzione deve restituire vuoto. La dichiarazione principale nel per loop aggiunge i due numeri precedenti.
La variabile indice, i, è stata usata al posto di n, ai fini della chiarezza.
Una classe principale di Java (con il metodo principale Java) è:
Classe pubblica Mainpublic static void main (string args [])
int m = 12;
int [] arr = new int [m];
Fibonacci obj = new fibonacci ();
obj.fibonacci (arr);
per (int i = 0; i
Sistema.fuori.println ();
Dopo che i numeri sono stati prodotti dal metodo Fibonacci (), il metodo principale Java li legge.
Producendo un numero di fibonacci in tempo costante
Esiste una formula matematica che può essere utilizzata per produrre un numero di fibonacci, quando viene dato l'indice corrispondente a base zero, n. La formula è:
dove n è l'indice e FIB basato su zeroN è il numero di fibonacci corrispondente. 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.
Se n è 0, fibN sarebbe 0. Se n è 1, FIBN sarebbe 1. Se n è 2, FIBN sarebbe 1. Se n è 3, FIBN sarebbe 2. Se n è 4, FIBN sarebbe 3 - e così via. Il lettore può verificare matematicamente questa formula, sostituendo valori diversi per N e valutando.
Se codificato, questa formula produrrebbe solo un numero di fibonacci per n. Se sono necessari più di un numero di fibonacci, il codice per la formula deve essere chiamato una volta per ciascuno dei diversi indici corrispondenti.
In Java, il metodo per produrre un solo numero di fibonacci è:
Importa Java.Lang.*;Classe fib
Double fibno (int n)
Double fibn = (matematica.POW ((1+matematica.sqrt (5))/2, n) -math.POW ((1 math.sqrt (5)) / 2, n)) / matematica.sqrt (5);
restituire fibn;
Il Java.Lang.* Il pacchetto doveva essere importato all'inizio del programma. Questo perché il pacchetto ha la classe matematica, che ha i metodi Power (Pow) e Square Root (SQRT). Il metodo Java personalizzato qui implementa direttamente la formula matematica.
La complessità temporale per questa funzione è O (1), addomesticata costante di un'operazione principale. Una classe principale di Java adatto, con il metodo principale Java per il metodo sopra è:
Classe pubblica Mainpublic static void main (string args [])
int n = 11;
Fib obj = new fib ();
doppio ret = obj.fibno (n);
Sistema.fuori.println (ret);
Viene inviato l'indice n = 11 e il numero di fibonacci, 89 viene restituito. L'output è:
89.00000000000003Le cifre decimali inutili possono essere rimosse, ma questa è una discussione per qualche altra volta.
Conclusione
I numeri di fibonacci sono una sequenza particolare di numeri interi. Per ottenere il numero corrente, aggiungi i precedenti due numeri corrispondenti immediati. I primi due numeri di Fibonacci, 0 seguiti da 1, sono pre-declassi, per l'intera sequenza. Il resto dei numeri di Fibonacci è prodotto da lì.
Per produrre numeri di fibonacci dall'indice 2, a quello che corrisponde all'indice N-1, utilizzare un per loop con la dichiarazione principale:
int CurrNo = P [i - 1] + P [i - 2];dove Currno è l'attuale numero di fibonacci e p è l'array per archiviare i numeri N.
Per produrre un solo numero di fibonacci da qualsiasi indice basato su zero n, usa la formula matematica: