Почему я получаю отрицательный результат при запуске моей программы для вычисления суммы всех четных чисел Фибоначчи? - PullRequest
Новая
       10

Почему я получаю отрицательный результат при запуске моей программы для вычисления суммы всех четных чисел Фибоначчи?

0 голосов
/ 02 октября 2019

Справочная информация:

Я работаю над проблемой Project Euler # 2, и у меня есть класс, созданный для решения этой проблемы. Для тех, кто еще этого не делал, это проблема:

Каждый новый термин в последовательности Фибоначчи генерируется путем добавления двух предыдущих терминов. Начиная с 1 и 2, первые 10 слагаемых будут: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, .... Рассматривая члены в последовательности Фибоначчи, значения которых не превышают четырех миллионов, найдите сумму четных членов.

Задача:

У меня есть программа, созданная для решения данной проблемы, но когда я ее запускаю, я получаю значение -1833689714 . Это не должно быть возвращаемое значение, так как я суммирую только положительные числа, и никаких умножений, которые я знаю, не выполняется. Как это исправить?

Мой код 

import java.util.ArrayList;

class Main {
  public static void main(String[] args) {

    int answer = resultsSum(fibonacci(4000000));
    System.out.println(answer);

  }

  public static int resultsSum(ArrayList<Integer> resultList){

    int total = 0;
    for(Integer r : resultList){

      total += r.intValue();

    }

    return total;

  }

  public static ArrayList<Integer> fibonacci(int n){

    ArrayList fibEvens = new ArrayList<Integer>();
    int a = 1;
    int b = 2;
    fibEvens.add(b);

    for(int i = 1; i < (n - 1); i++) {

      int tempVar = a;
      a = b;
      b += tempVar;
      if(b % 2 == 0){

        fibEvens.add(b);

      }
    }
    return fibEvens;
  }
}

https://projecteuler.net/problem=2

Ответы [ 3 ]

2 голосов
/ 02 октября 2019

Причина, по которой вы получаете отрицательный результат, состоит в том, что члены последовательности Фибоначчи выше 88-го члена превышают максимальное положительное значение типа данных Long в java, которое составляет 9 223 372 036 854 775,80.

Когда вы пытаетесь увеличить тип данных long за пределы максимального значения на единицу, он оборачивается до минимального значения (-9,223,372,036,854,775,80). В тот момент, когда термины Фибоначчи превышают максимальное значение, вы делаете это много раз.

Кроме того, проблема, которую вы опубликовали, указывает на то, что вы должны остановиться, когда значение числа получено из последовательностибольше 4 миллионов, не пытаясь добавить четные значения первых 4 миллионов значений (что огромно).

2 голосов
/ 02 октября 2019

Похоже, ваш код пытается добраться до 4-миллионного числа Фибоначчи, которое сильно отличается от слагаемых в последовательности Фибоначчи, значения которых не превышают четырех миллионов .

1 голос
/ 02 октября 2019

Поскольку

  • int тип данных хранит число от -2^31 до 2^31 - 1
  • Integer тип данных хранит число от -2^63 до 2^63 - 1

Попробуйте с BigInteger 

public static BigInteger fibonacci(int n) {
    BigInteger[] f = new BigInteger[n + 1];
    f[0] = BigInteger.ZERO;
    if (n > 0) {
        f[1] = BigInteger.ONE;
    }
    for (int i = 2; i < f.length; i++) {
        f[i] = f[i - 1].add(f[i - 2]);
    }
    return f[n];
}

Но значение Фибоначчи 4 миллиона очень длинное. Подробнее 300th , 500th

...