java - code - fibonacci series algorithm

fibonacci funciona en python pero falla en Java

Question

Tengo este código para calcular el número de fibonacci en python . Funciona y da el resultado esperado. pero cuando traduje lo mismo a Java , falla. ¿Alguna idea de lo que está mal aquí?

En python :

def fib3(n): 
  a,b=0,1
  while n>0:
      a,b=b,a+b
      n-=1
  return a

fib3(12) --> 144

En Java :

 public static int fib2(int n){
        int a = 0;
        int b =1;
        while(n-- >0){
            a=b;
            b=a+b;

        }
    return a;
}

fib2(12) --> 2048

Answer 1

El código no es equivalente y se basa en la capacidad de Python para asignar múltiples primitivas en una línea a,b=b,a+b ; necesitas una variable temporal -

public static int fib2(int n){
  int a = 0;
  int b =1;
  while(n-- >0){
      int t = b; // <-- to hold the original value of b.
      b = a + b;
      a = t;
  }
  return a;
}

Answer 2

El problema es que tienes un valor de b a a al mismo tiempo que asigna a b la suma de a y b . Si ese intercambio simultáneo es incorrecto, obtienes la respuesta incorrecta.

En el espíritu del código Python, les presento:

public static int fib(int n) {
    int a = 0, b = 1;
    while (n-->0)
        b = a + (a = b);
    return a;
}

Esto hace el intercambio efectivamente al mismo tiempo que el agregado (estrictamente no, pero es lo suficientemente bueno). Tenga en cuenta que esto es Java bien definido , ya que el lenguaje define el orden de evaluación de los operadores de manera precisa, a diferencia de C y C ++ (donde el equivalente del código anterior está permitido para hacer que los demonios salgan volando de su nariz debido a su comportamiento indefinido).

De acuerdo, si le hizo experimentar problemas con los demonios nasales, sugeriría no usar ese compilador en el futuro. Pero no tendría ninguna seguridad de obtener una función fib () correcta ...

Answer 3

En esta sección:

a=b;
b=a+b;

estás asignando b a a+b , pero a ya está b . Así que realmente estás doblando b

La solución más fácil es una variable temporal:

public static int fib2(int n){
    int a = 0;
    int b =1;
    while(n-- >0){
        int old_a;
        old_a = a;
        a=b;
        b=old_a+b;
    }
    return a;
}

En Python, a, b = b, a + b almacena una tuple intermedia automáticamente antes de asignar los nuevos valores a las variables, mientras que en Java debe ser explícito al respecto

Desglosando las instrucciones de Python, a, b = b, a + b está ejecutando este desmontaje:

  5          17 LOAD_FAST                1 (b)
             20 LOAD_FAST                0 (a)
             23 LOAD_FAST                1 (b)
             26 BINARY_ADD
             27 ROT_TWO
             28 STORE_FAST               0 (a)
             31 STORE_FAST               1 (b)

En un sentido más simple, permaneciendo python, aquí está el proceso:

temp_tuple = (b, a + b)
a, b = temp_tuple

Answer 4

En java: cuando escribes "a = b; b = a + b;" esencialmente estás diciendo que a debería ser igual a ser y luego que (ya que ''a'' ahora es igual a ''b'') que ''b'' debería ser el doble de lo que originalmente era. Hay dos maneras en que puedes arreglar esto. 1) Puede continuar con la función que está usando originalmente y luego crear una int ''temp'' para almacenar ''a'' antes de cambiar ''a''. 2) También puede hacer lo que preferiría (esto usará mucho más tiempo, sin embargo, para un algoritmo como fibonacci y generalmente sería una idea terrible para aplicaciones del mundo real) es usar una función recursiva que se llamará a sí misma.

En general, se vería algo como lo siguiente.

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

Ese probablemente no sería el código exacto sino algo muy similar. Espero que haya sido útil!

Answer 5

a = b;
b = a+b;

Esto calcula b = 2*b porque el valor de a se sobrescribe cuando usted calcula el nuevo valor para b . Reemplácelo con:

t = b;
b = a+b;
a = t

Answer 6

a=b;
b=a+b;

... es el problema. Debe guardar el valor anterior de a antes de agregarlo a b .