suma - series numericas en java netbeans

Secuencia de Fibonacci recursiva de Java

Question

Por favor, explica este código (es simple, pero por favor ten paciencia porque todavía soy un novato: P):

public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}

Estoy confundido con la última línea, especialmente porque si n = 5 por ejemplo, entonces se llamaría fibonacci (4) + fibonacci (3) y así sucesivamente, pero no entiendo cómo este algoritmo calcula el valor en el índice 5 por este método. Por favor explique con muchos detalles!

Answer 1

Por qué esta respuesta es diferente

Cualquier otra respuesta, ya sea:

• Imprime en lugar de devoluciones
• Realiza 2 llamadas recursivas por iteración
• Ignora la pregunta usando bucles

(a un lado: ninguno de estos es realmente eficiente, use la fórmula de Binet para calcular directamente el ^enésimo término)

Tail Recursive Fib

Aquí hay un enfoque recursivo que evita una llamada recursiva doble al pasar tanto la respuesta anterior como la anterior.

private static final int FIB_0 = 0;
private static final int FIB_1 = 1;
private int calcFibonacci(final int target) {
if (target == 0) { return FIB_0; }
if (target == 1) { return FIB_1; }
return calcFibonacci(target, 1, FIB_1, FIB_0);
}
private int calcFibonacci(final int target, final int previous, final int fibPrevious, final int fibPreviousMinusOne) {
final int current = previous + 1;
final int fibCurrent = fibPrevious + fibPreviousMinusOne;
// If you want, print here / memoize for future calls
if (target == current) { return fibCurrent; }
return calcFibonacci(target, current, fibCurrent, fibPrevious);
}

Answer 2

Úselo while :

public int fib(int index) {
int tmp = 0, step1 = 0, step2 = 1, fibNumber = 0;
while (tmp < index - 1) {
fibNumber = step1 + step2;
step1 = step2;
step2 = fibNumber;
tmp += 1;
};
return fibNumber;
}

La ventaja de esta solución es que es fácil leer el código y entenderlo, esperando que ayude

Answer 3

@chro es perfecto, pero no muestra la forma correcta de hacerlo de forma recursiva. Aquí está la solución:

class Fib {
static int count;
public static void main(String[] args) {
log(fibWrong(20)); // 6765
log("Count: " + count); // 21891
count = 0;
log(fibRight(20)); // 6765
log("Count: " + count); // 19
}
static long fibRight(long n) {
return calcFib(n-2, 1, 1);
}
static long fibWrong(long n) {
count++;
if (n == 0 || n == 1) {
return n;
} else if (n < 0) {
log("Overflow!");
System.exit(1);
return n;
} else {
return fibWrong(n-1) + fibWrong(n-2);
}
}
static long calcFib(long nth, long prev, long next) {
count++;
if (nth-- == 0)
return next;
if (prev+next < 0) {
log("Overflow with " + (nth+1)
+ " combinations remaining");
System.exit(1);
}
return calcFib(nth, next, prev+next);
}
static void log(Object o) {
System.out.println(o);
}
}

Answer 4

Al utilizar un ConcurrentHashMap interno que teóricamente podría permitir que esta implementación recursiva funcione correctamente en un entorno multiproceso, he implementado una función fib que utiliza tanto BigInteger como Recursion. Toma alrededor de 53ms para calcular los primeros 100 números fib.

private final Map<BigInteger,BigInteger> cacheBig
= new ConcurrentHashMap<>();
public BigInteger fibRecursiveBigCache(BigInteger n) {
BigInteger a = cacheBig.computeIfAbsent(n, this::fibBigCache);
return a;
}
public BigInteger fibBigCache(BigInteger n) {
if ( n.compareTo(BigInteger.ONE ) <= 0 ){
return n;
} else if (cacheBig.containsKey(n)){
return cacheBig.get(n);
} else {
return
fibBigCache(n.subtract(BigInteger.ONE))
.add(fibBigCache(n.subtract(TWO)));
}
}

El código de prueba es:

@Test
public void testFibRecursiveBigIntegerCache() {
long start = System.currentTimeMillis();
FibonacciSeries fib = new FibonacciSeries();
IntStream.rangeClosed(0,100).forEach(p -&R {
BigInteger n = BigInteger.valueOf(p);
n = fib.fibRecursiveBigCache(n);
System.out.println(String.format("fib of %d is %d", p,n));
});
long end = System.currentTimeMillis();
System.out.println("elapsed:" +
(end - start) + "," +
((end - start)/1000));
}

and output from the test is: . . . . . fib of 93 is 12200160415121876738 fib of 94 is 19740274219868223167 fib of 95 is 31940434634990099905 fib of 96 is 51680708854858323072 fib of 97 is 83621143489848422977 fib of 98 is 135301852344706746049 fib of 99 is 218922995834555169026 fib of 100 is 354224848179261915075 elapsed:58,0

Answer 5

Aquí hay un recursivo febonacci de una línea:

public long fib( long n ) {
return n <= 0 ? 0 : n == 1 ? 1 : fib( n - 1 ) + fib( n - 2 );
}

Answer 6

Creo que esta es una manera simple:

public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int number = input.nextInt();
long a = 0;
long b = 1;
for(int i = 1; i<number;i++){
long c = a +b;
a=b;
b=c;
System.out.println(c);
}
}
}

Answer 7

En la secuencia de fibonacci, cada elemento es la suma de los dos anteriores. Entonces, usted escribió un algoritmo recursivo.

Asi que,

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(2) = fibonacci(1) + fibonacci(0)

Ahora ya sabes fibonacci(1)==1 and fibonacci(0) == 0 . Por lo tanto, puede calcular posteriormente los otros valores.

Ahora,

fibonacci(2) = 1+0 = 1
fibonacci(3) = 1+1 = 2
fibonacci(4) = 2+1 = 3
fibonacci(5) = 3+2 = 5

Y a partir de la secuencia de fibonacci 0,1,1,2,3,5,8,13,21.... podemos ver que para el 5th element la secuencia de fibonacci devuelve 5 .

Vea aquí para el Tutorial de Recursión .

Answer 8

En pseudo código, donde n = 5, ocurre lo siguiente:

fibonacci (4) + fibonnacci (3)

Esto se descompone en:

(fibonacci (3) + fibonnacci (2)) + (fibonacci (2) + fibonnacci (1))

Esto se descompone en:

(((fibonacci (2) + fibonnacci (1)) + ((fibonacci (1) + fibonnacci (0))) + (((fibonacci (1) + fibonnacci (0)) + 1))

Esto se descompone en:

((((fibonacci (1) + fibonnacci (0)) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Esto se descompone en:

((((1 + 0) + 1) + ((1 + 0)) + ((1 + 0) + 1))

Esto resulta en: 5

Dado que la secuencia de fibonnacci es 1 1 2 3 5 8 ... , el quinto elemento es 5. Puede usar la misma metodología para descubrir las otras iteraciones.

Answer 9

Es una secuencia básica que muestra u obtiene una salida de 1 1 2 3 5 8 es una secuencia en la que la suma del número anterior se mostrará a continuación.

Intente ver el enlace debajo de la secuencia recursiva de Fibonacci de Java Tutorial

public static long getFibonacci(int number){
if(number<=1) return number;
else return getFibonacci(number-1) + getFibonacci(number-2);
}

Haga clic aquí Vea secuencia recursiva de Fibonacci de Java Tutorial para alimentación con cuchara

Answer 10

Este es el mejor video que he encontrado que explica completamente la recursión y la secuencia de Fibonacci en Java.

http://www.youtube.com/watch?v=dsmBRUCzS7k

Este es su código para la secuencia y su explicación es mejor de lo que podría hacer tratando de escribirla.

public static void main(String[] args)
{
int index = 0;
while (true)
{
System.out.println(fibonacci(index));
index++;
}
}
public static long fibonacci (int i)
{
if (i == 0) return 0;
if (i<= 2) return 1;
long fibTerm = fibonacci(i - 1) + fibonacci(i - 2);
return fibTerm;
}

Answer 11

Fibonacci simple

public static void main(String[]args){
int i = 0;
int u = 1;
while(i<100){
System.out.println(i);
i = u+i;
System.out.println(u);
u = u+i;
}
}
}

Answer 12

Hay 2 problemas con su código:

1. El resultado se almacena en int, que puede manejar solo los primeros 48 números de Fibonacci, después de esto, el entero se completa menos el bit y el resultado es incorrecto.
2. Pero nunca se puede ejecutar fibonacci (50).
   El código
   fibonacci(n - 1) + fibonacci(n - 2)
   esta muy mal
   El problema es que llama fibonacci no 50 veces sino mucho más.
   Al principio llama a fibonacci (49) + fibonacci (48),
   siguiente fibonacci (48) + fibonacci (47) y fibonacci (47) + fibonacci (46)
   Cada vez se volvió peor fibonacci (n), por lo que la complejidad es exponencial.

El enfoque del código no recursivo:

 double fibbonaci(int n){
double prev=0d, next=1d, result=0d;
for (int i = 0; i < n; i++) {
result=prev+next;
prev=next;
next=result;
}
return result;
}

Answer 13

La mayoría de las respuestas son buenas y explica cómo funciona la recursión en fibonacci.

Aquí hay un análisis de las tres técnicas que incluye la recursión también:

1. En bucle
2. Recursión
3. Memoization

Aquí está mi código para probar los tres:

public class Fibonnaci {
// Output = 0 1 1 2 3 5 8 13
static int fibMemo[];
public static void main(String args[]) {
int num = 20;
System.out.println("By For Loop");
Long startTimeForLoop = System.nanoTime();
// returns the fib series
int fibSeries[] = fib(num);
for (int i = 0; i < fibSeries.length; i++) {
System.out.print(" " + fibSeries[i] + " ");
}
Long stopTimeForLoop = System.nanoTime();
System.out.println("");
System.out.println("For Loop Time:" + (stopTimeForLoop - startTimeForLoop));
System.out.println("By Using Recursion");
Long startTimeRecursion = System.nanoTime();
// uses recursion
int fibSeriesRec[] = fibByRec(num);
for (int i = 0; i < fibSeriesRec.length; i++) {
System.out.print(" " + fibSeriesRec[i] + " ");
}
Long stopTimeRecursion = System.nanoTime();
System.out.println("");
System.out.println("Recursion Time:" + (stopTimeRecursion -startTimeRecursion));
System.out.println("By Using Memoization Technique");
Long startTimeMemo = System.nanoTime();
// uses memoization
fibMemo = new int[num];
fibByRecMemo(num-1);
for (int i = 0; i < fibMemo.length; i++) {
System.out.print(" " + fibMemo[i] + " ");
}
Long stopTimeMemo = System.nanoTime();
System.out.println("");
System.out.println("Memoization Time:" + (stopTimeMemo - startTimeMemo));
}
//fib by memoization
public static int fibByRecMemo(int num){
if(num == 0){
fibMemo[0] = 0;
return 0;
}
if(num ==1 || num ==2){
fibMemo[num] = 1;
return 1;
}
if(fibMemo[num] == 0){
fibMemo[num] = fibByRecMemo(num-1) + fibByRecMemo(num -2);
return fibMemo[num];
}else{
return fibMemo[num];
}
}
public static int[] fibByRec(int num) {
int fib[] = new int[num];
for (int i = 0; i < num; i++) {
fib[i] = fibRec(i);
}
return fib;
}
public static int fibRec(int num) {
if (num == 0) {
return 0;
} else if (num == 1 || num == 2) {
return 1;
} else {
return fibRec(num - 1) + fibRec(num - 2);
}
}
public static int[] fib(int num) {
int fibSum[] = new int[num];
for (int i = 0; i < num; i++) {
if (i == 0) {
fibSum[i] = i;
continue;
}
if (i == 1 || i == 2) {
fibSum[i] = 1;
continue;
}
fibSum[i] = fibSum[i - 1] + fibSum[i - 2];
}
return fibSum;
}
}

Aquí están los resultados:

By For Loop
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
For Loop Time:347688
By Using Recursion
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Recursion Time:767004
By Using Memoization Technique
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Memoization Time:327031

Por lo tanto, podemos ver que la memorización es la mejor en cuanto a tiempo y para el bucle coincide estrechamente.

Pero la recursividad lleva más tiempo y es posible que deba evitarla en la vida real. Además, si está utilizando recurrencia, asegúrese de optimizar la solución.

Answer 14

La mayoría de las soluciones que se ofrecen aquí se ejecutan en O (2 ^ n) complejidad. Volver a calcular nodos idénticos en árbol recursivo es ineficiente y desperdicia ciclos de CPU.

Podemos usar la memorización para hacer funcionar la función de fibonacci en el tiempo O (n)

public static int fibonacci(int n) {
return fibonacci(n, new int[n + 1]);
}
public static int fibonacci(int i, int[] memo) {
if (i == 0 || i == 1) {
return i;
}
if (memo[i] == 0) {
memo[i] = fibonacci(i - 1, memo) + fibonacci(i - 2, memo);
}
return memo[i];
}

Si seguimos la ruta de programación dinámica ascendente, el siguiente código es lo suficientemente simple para calcular fibonacci:

public static int fibonacci1(int n) {
if (n == 0) {
return n;
} else if (n == 1) {
return n;
}
final int[] memo = new int[n];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i < n; i++) {
memo[i] = memo[i - 1] + memo[i - 2];
}
return memo[n - 1] + memo[n - 2];
}

Answer 15

La recursión puede ser difícil de entender a veces. Simplemente evalúelo en un pedazo de papel para un pequeño número:

fib(4)
-> fib(3) + fib(2)
-> fib(2) + fib(1) + fib(1) + fib(0)
-> fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
-> 1 + 0 + 1 + 1 + 0
-> 3

No estoy seguro de cómo Java realmente evalúa esto, pero el resultado será el mismo.

Answer 16

La respuesta RanRag (aceptada) funcionará bien, pero no es una solución optimizada hasta que se memorice, como mínimo, como se explica en la respuesta de Anil.

Para recursivo considere a continuación el enfoque, las llamadas a métodos de TestFibonacci son mínimas

public class TestFibonacci {
public static void main(String[] args) {
int n = 10;
if (n == 1) {
System.out.println(1);
} else if (n == 2) {
System.out.println(1);
System.out.println(1);
} else {
System.out.println(1);
System.out.println(1);
int currentNo = 3;
calFibRec(n, 1, 1, currentNo);
}
}
public static void calFibRec(int n, int secondLast, int last,
int currentNo) {
if (currentNo <= n) {
int sum = secondLast + last;
System.out.println(sum);
calFibRec(n, last, sum, ++currentNo);
}
}
}

Answer 17

La serie Fibonacci es un código simple que muestra el poder de la programación dinámica. Todo lo que aprendimos de la jornada escolar es ejecutarlo a través de un código recursivo iterativo o máximo. El código recursivo funciona bien hasta 20 o más, si le das números más grandes verás que lleva mucho tiempo calcular. En la programación dinámica puede codificar de la siguiente manera y lleva segundos calcular la respuesta.

static double fib(int n) {
if (n < 2)
return n;
if (fib[n] != 0)
return fib[n];
fib[n] = fib(n - 1) + fib(n - 2);
return fib[n];
}

Usted almacena valores en una matriz y procede a un nuevo cálculo solo cuando la matriz no puede proporcionarle la respuesta.

Answer 18

Michael Goodrich et al proporcionan un algoritmo realmente inteligente en estructuras de datos y algoritmos en Java, para resolver fibonacci recursivamente en tiempo lineal devolviendo una matriz de [fib (n), fib (n-1)].

public static long[] fibGood(int n) {
if (n < = 1) {
long[] answer = {n,0};
return answer;
} else {
long[] tmp = fibGood(n-1);
long[] answer = {tmp[0] + tmp[1], tmp[0]};
return answer;
}
}

Esto produce fib (n) = fibGood (n) [0].

Answer 19

Para la solución recursiva de Fibonacci, es importante guardar la salida de números de Fibonacci más pequeños, mientras se recupera el valor de un número mayor. Esto se llama "Memoizing".

Aquí hay un código que usa la memorización de los valores de fibonacci más pequeños, mientras recupera el número de fibonacci más grande. Este código es eficiente y no realiza múltiples solicitudes de la misma función.

import java.util.HashMap;
public class Fibonacci {
private HashMap<Integer, Integer> map;
public Fibonacci() {
map = new HashMap<>();
}
public int findFibonacciValue(int number) {
if (number == 0 || number == 1) {
return number;
}
else if (map.containsKey(number)) {
return map.get(number);
}
else {
int fibonacciValue = findFibonacciValue(number - 2) + findFibonacciValue(number - 1);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}

Answer 20

Sí, es importante memorizar el valor de retorno calculado de cada llamada al método de recursión, para que pueda visualizar la serie en el método de llamada.

Hay algunos refinamientos en la implementación provista. A continuación encontrará la implementación que nos brinda un resultado más correcto y versátil:

import java.util.HashMap;
import java.util.stream.Collectors;
public class Fibonacci {
private static HashMap<Long, Long> map;
public static void main(String[] args) {
long n = 50;
map = new HashMap<>();
findFibonacciValue(n);
System.out.println(map.values().stream().collect(Collectors.toList()));
}
public static long findFibonacciValue(long number) {
if (number <= 1) {
if (number == 0) {
map.put(number, 0L);
return 0L;
}
map.put(number, 1L);
return 1L;
} else if (map.containsKey(number)) {
return map.get(number);
} else {
long fibonacciValue = findFibonacciValue(number - 1L) + findFibonacciValue(number - 2L);
map.put(number, fibonacciValue);
return fibonacciValue;
}
}
}

La salida para el número 50 es:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025]

Answer 21

Solo para complementar, si quieres poder calcular números más grandes, debes usar BigInteger.

Un ejemplo iterativo.

import java.math.BigInteger;
class Fibonacci{
public static void main(String args[]){
int n=10000;
BigInteger[] vec = new BigInteger[n];
vec[0]=BigInteger.ZERO;
vec[1]=BigInteger.ONE;
// calculating
for(int i = 2 ; i<n ; i++){
vec[i]=vec[i-1].add(vec[i-2]);
}
// printing
for(int i = vec.length-1 ; i>=0 ; i--){
System.out.println(vec[i]);
System.out.println("");
}
}
}

Answer 22

También puede simplificar su función de la siguiente manera:

public int fibonacci(int n) {
if (n < 2) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

Answer 23

Una secuencia de Fibbonacci es aquella que suma el resultado de un número cuando se agrega al resultado anterior comenzando con 1.

 so.. 1 + 1 = 2
2 + 3 = 5
3 + 5 = 8
5 + 8 = 13
8 + 13 = 21

Una vez que comprendamos qué es Fibbonacci, podemos comenzar a desglosar el código.

public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}

La primera si la declaración comprueba si hay un caso base, donde el bucle puede estallar. La declaración else if a continuación está haciendo lo mismo, pero podría volverse a escribir así ...

 public int fibonacci(int n) {
if(n < 2)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}

Ahora que se establece un caso base, debemos comprender la pila de llamadas. La primera llamada a "fibonacci" será la última en resolverse en la pila (secuencia de llamadas) mientras se resuelven en el orden inverso al que fueron llamadas. El último método llamado se resuelve primero, luego el último que se llama antes de ese y así sucesivamente ...

Entonces, todas las llamadas se hacen primero antes de que cualquier cosa sea "calculada" con esos resultados. Con una entrada de 8, esperamos una salida de 21 (consulte la tabla anterior).

fibonacci (n - 1) sigue siendo llamado hasta que alcanza el caso base, luego se llama a fibonacci (n - 2) hasta que alcanza el caso base. Cuando la pila comienza a sumar el resultado en orden inverso, el resultado será similar a ...

1 + 1 = 1 ---- last call of the stack (hits a base case).
2 + 1 = 3 ---- Next level of the stack (resolving backwards).
2 + 3 = 5 ---- Next level of the stack (continuing to resolve).

Siguen burbujeando (resolviendo hacia atrás) hasta que la suma correcta se devuelve a la primera llamada en la pila y así es como obtienes tu respuesta.

Una vez dicho esto, este algoritmo es muy ineficiente porque calcula el mismo resultado para cada rama en la que se divide el código. Un enfoque mucho mejor es uno de "abajo hacia arriba" en el que no se requiere Memoization (caching) o recursion (deep call stack).

Al igual que...

 static int BottomUpFib(int current)
{
if (current < 2) return current;
int fib = 1;
int last = 1;
for (int i = 2; i < current; i++)
{
int temp = fib;
fib += last;
last = temp;
}
return fib;
}

Answer 24

en la secuencia de fibonacci , los primeros dos elementos son 0 y 1, cada otro elemento es la suma de los dos elementos anteriores. es decir:
0 1 1 2 3 5 8 ...

por lo que el quinto elemento es la suma de los artículos 4 y 3.

Answer 25

fibonacci en más detalles

public class Fibonacci {
public static long fib(int n) {
if (n <= 1) return n;
else return fib(n-1) + fib(n-2);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
for (int i = 1; i <= N; i++)
System.out.println(i + ": " + fib(i));
}
}

Haz que sea tan simple como sea necesario sin necesidad de usar while loop y otro loop

Answer 26

 F(n)
/ /
F(n-1) F(n-2)
/ / / /
F(n-2) F(n-3) F(n-3) F(n-4)
/ /
F(n-3) F(n-4)

Un punto importante a tener en cuenta es que este algoritmo es exponencial porque no almacena el resultado de números calculados previamente. por ejemplo, F (n-3) se llama 3 veces.

Para más detalles, consulte el algoritmo por dasgupta capítulo 0.2

Answer 27

 import java.util.*;
/*
@ Author 12CSE54
@ Date 28.10.14
*/
public class cfibonacci
{
public void print(int p)
{
int a=0,b=1,c;
int q[]=new int[30];
q[0]=a;
q[1]=b;
for(int i=2;i<p;i++)
{
c=a+b;
q[i]=c;
a=b;
b=c;
}
System.out.println("elements are..../n");
for(int i=0;i<q.length;i++)
System.out.println(q[i]);
}
public static void main(String ar[])throws Exception
{
Scanner s=new Scanner(System.in);
int n;
System.out.println("Enter the number of elements/n");
n=sc.nextInt();
cfibonacci c=new cfibonacci();
c.printf(n);
}
}

Answer 28

 public static long fib(int n) {
long population = 0;
if ((n == 0) || (n == 1)) // base cases
{
return n;
} else // recursion step
{
population+=fib(n - 1) + fib(n - 2);
}
return population;
}

Answer 29

public class FibonacciSeries {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i <= N; i++) {
int result = fibonacciSeries(i);
System.out.println(result);
}
scanner.close();
}
private static int fibonacciSeries(int n) {
if (n < 0) {
return 1;
} else if (n > 0) {
return fibonacciSeries(n - 1) + fibonacciSeries(n - 2);
}
return 0;
}
}

Answer 30

public class febo
{
public static void main(String...a)
{
int x[]=new int[15];
x[0]=0;
x[1]=1;
for(int i=2;i<x.length;i++)
{
x[i]=x[i-1]+x[i-2];
}
for(int i=0;i<x.length;i++)
{
System.out.println(x[i]);
}
}
}