Fibonacci usando 1 Magnitud de

Question

me hizo la siguiente pregunta en una entrevista:

¿Hay alguna forma en la que la serie de Fibonacci se puede generar utilizando sólo 1 variable?

No supe qué responder. ¿Qué debería haber dicho?

Answer 1

Sí, puede utilizado el closed-form expression:

donde

Puede calcular la expresión usando double y redondear el resultado a la ne arest entero. Debido a la precisión finita de la aritmética de coma flotante, esta fórmula dará una respuesta incorrecta para n lo suficientemente grande, pero creo que funcionará en el caso cuando el resultado se ajuste a un entero Java de 32 bits.

Answer 2

Sí, pero aún necesita recordar 2 valores. Podría tomar una variable de 64 bits y usarla como 2 vars de 32 bits.

Answer 3

Por supuesto, el uso de la recursividad:

public class Test { 

    public static int fib(int n) { 
     return n < 2 ? n : fib(n-1) + fib(n-2); 
    } 

    public static void main(String[] args) { 
     for(int i = 0; i <= 10; i++) { 
      System.out.print(fib(i)+", "); 
     } 
     System.out.println("..."); 
    } 
} 

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 

Answer 4

La respuesta es "sí", pero tal vez podría ser más específico.

El primer ejemplo que se me ocurrió, el uso de la recursividad doble (que conduce a una complejidad exponencial, no se recomienda):

int fib(int a) { 
    if (a < 2) { 
    return 1 
    } else { 
    return fib(a-1) + fib(a-2); 
    } 
} 

Suponiendo una> = 0 (se podría añadir un cheque para eso).

(Editar - se utiliza la convención equivocado de F (0) indefinido, F (1) = 1)

Answer 5

Hasta cierto punto, sí (aunque en C, podría convertirlo a Java, se vería mucho más feo).

#include <stdio.h> 
#include <stdlib.h> 

int main (void) { 
    unsigned long i = 1; 
    printf ("0\n"); 
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) { 
     printf ("%d\n", i & 0xffff); 
     i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff)); 
    } 
    return 0; 
} 

que produce:

0 
1 
1 
2 
3 
5 
8 
13 
21 
34 
55 
89 
144 
233 
377 
610 
987 
1597 
2584 
4181 
6765 
10946 
17711 
28657 

:-)

La verdadera pregunta, por supuesto, es: ¿Por qué quieres?

---

Si tiene curiosidad sobre cómo funciona, es realmente bastante simple. La única variable se divide en dos partes y esas dos partes mantienen los valores individuales para la secuencia de Fibonacci. Todavía es técnicamente una variable, hemos impuesto una estructura adicional para lograr nuestros fines.

Answer 6

Después de la inicial 1 1, que en teoría es posible generar un valor de la anterior (hasta precisión de la máquina, vuelve a morder) a través de:

f = Math.round(f * PHI) 

donde PHI es la constante definida en otro comentario :

static final double PHI = (1 + Math.sqrt(5))/2;

Answer 7

siempre se puede hacer algo como esto:

String theOneVar = "100;0;1"; 
    while (true) { 
     if (theOneVar.split(";")[0].equals("0")) break; 
     System.out.println(theOneVar.split(";")[1]); 
     theOneVar = String.format("%s;%s;%s", 
      Integer.parseInt(theOneVar.split(";")[0]) - 1, 
      theOneVar.split(";")[2], 
      new BigInteger(theOneVar.split(";")[1]).add(
       new BigInteger(theOneVar.split(";")[2]) 
      ) 
     ); 
    } 

Esta impresora (as seen on ideone.com):

0 
1 
1 
2 
3 
5 
8 
13 
: 
: 
83621143489848422977 
135301852344706746049 
218922995834555169026 

Esto utiliza sólo una variable explícita, y es esencialmente un algoritmo no recursivo lineal. Sin embargo, se debe decir que este es un abuso de String.

Answer 8

Aquí hay un ejemplo en C#. Muestra los primeros 100 términos. La relación entre los términos en Fibonacci se aproxima a la proporción áurea (1.618033 ...), por lo que un enfoque de variable única simplemente requiere una multiplicación por una constante para cada término.

Yay math!

double fib = 1; 
for (int i = 0; i < 100; i++) 
{ 
    Console.WriteLine("" + fib); 
    fib = Math.Round(fib *= 1.6180339887d); 
} 

Answer 9

Así que esto es malo, sino:

static String fibRecord = "x;"; 

static int nextFib() { 
    try { 
    return fibRecord.indexOf(';'); 
    } finally { 
    fibRecord = fibRecord.replaceAll("(x*);(x*)", "$1$2;$1"); 
    } 
} 

public static void main(String[] ignored) { 
    for (int i=0; i < 30; i++) { 
    System.out.println(nextFib()); 
    } 
} 

Mi máquina de aquí comienza a caer sobre todo el número de Fibonacci 38a.

Answer 10

class fibo{ 
    public static void main (String args[]) { 
    long i = 1; 
    while (((i & 0xffff0000) >> 16) + (i & 0xffff) <= 0xffff) { 
     System.out.println(i & 0xffff); 
     i = ((i & 0xffff) << 16) | ((i >> 16) + (i & 0xffff)); 
    } 
    } 
} 

Aquí está el código java de la serie Fibonacci usando una variable.

Answer 11

EL PROGRAMA ES PARA IMPRIMIR HASTA 10 NÚMERO PERO PUEDE CAMBIARLO.

import java. i o.*; 

class q 
{ 

public static void main()throws IO Exception 

{ 

int n=0; 

for(int i=1; i<=10 ; i++) 

{ 

    System.out.print(n +" "); 

    n=(int)Math.round(n*1.618) 

    } 

} 

} 


1.618 = PHI 

el programa tiene algunos errores en la importación y en la declaración principal, pero el cuerpo está lleno correcta

Answer 12

public class test { 


public static void main(String[] args) { 
int arr[]=new int[13]; 
arr[0]=0; 
arr[1]=1; 

for(int i=2;i<=12;i++){ 
arr[i]=arr[i-1]+arr[i-2]; 
} 
for(int i=0;i<=arr.length-1;i++){ 
System.out.print(arr[i]+" "); 
} 

} 

}