Фибоначчи работает в python, но не работает в Java

У меня есть этот код для вычисления числа fibonacci в python. Он работает и дает ожидаемый результат. но когда я перевел то же самое на Java, он терпит неудачу. Любая идея о том, что здесь происходит не так?

В python:

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

fib3(12) --> 144

В 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

Ответ 1

В этом разделе:

a=b;
b=a+b;

вы назначаете b в a+b, но a уже b. Так что вы удваиваете b

Самое простое решение - это временная переменная:

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;
}

В python a, b = b, a + b автоматически сохраняет промежуточный tuple, прежде чем назначать новые значения переменным, в то время как в Java вы должны быть явно об этом

Нарушая инструкции Python, a, b = b, a + b выполняет эту разборку:

  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)

В более простом смысле, оставаясь на python, вот процесс:

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

Ответ 2

Проблема в том, что вы получили одно значение от b до a в то же время, назначая b сумму a и b. Получите этот синхронный своп неправильно, и вы получите неправильный ответ.

В духе кода Python я представляю:

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

Это делает обмен фактически в то же время, что и добавление (строго не, но это достаточно хорошо). Обратите внимание, что это хорошо определенная Java, так как язык точно определяет порядок оценки операторов, в отличие от C и С++ (где эквивалент вышеуказанного кода разрешен, чтобы заставить демонов вылететь из вашего носа из-за того, что он Undefined Поведение).

ОК, если у вас возникли проблемы с носовыми демонами, я бы предложил не использовать этот компилятор в будущем. Но у вас не было бы никакой гарантии получения правильной функции fib()...

Ответ 3

a = b;
b = a+b;

Это вычисляет b = 2*b, потому что значение a перезаписывается временем, когда вы вычисляете новое значение для b. Замените его на:

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

Ответ 4

a=b;
b=a+b;

... есть проблема. Вам нужно сохранить старое значение a, прежде чем добавлять его в b.

Ответ 5

Код не эквивалентен и полагается на способность python назначать несколько примитивов в одной строке a,b=b,a+b; вам нужна временная переменная -

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;
}

Ответ 6

В java - Когда вы пишете "a = b; b = a + b;" вы, по существу, говорите, что a должно быть равным, а затем (поскольку "a" теперь равно "b" ), что "b" должно быть в два раза больше, чем оно было первоначально. Есть два способа исправить это. 1) Вы можете либо продолжить функцию, которую вы изначально используете, а затем создать int 'temp' для хранения 'a', прежде чем вы измените 'a'. 2) Вы также можете делать то, что я бы предпочел (это будет использовать намного больше времени, однако для алгоритма, такого как фибоначчи, и, как правило, это ужасная идея для приложений реального мира), использует рекурсивную функцию, которая будет называть себя.

Это будет выглядеть примерно так:

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

Это, вероятно, не точный код, а нечто очень похожее. Надеюсь, что это было полезно!