斐波那契数列 - 如何计算前 100 个偶数斐波那契数之和？

Question

斐波那契数列定义为以 1 和 1 开头的整数序列，其中每个后续值都是前两个值的总和，即

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) where n>=2

我的目标是计算前 100 个偶数斐波那契数的总和。

到目前为止，我发现这段代码可以完美地计算偶数之和到 400 万，但是我无法找到编辑代码以使其在第 100 个值的总和处停止，而不是达到 400 万。


public class Improvement {
  public static int Fibonacci(int j) {
      
      /**
       * 
       * Recursive took a long time so continued with iterative 
       * 
       * Complexity is n squared.. try to improve to just n
       * 
       */
            int tmp;
            int a = 2;
            int b = 1;
            int total = 0;

            do {
              if(isEven(a)) total +=a;
              tmp = a + b;
              b = a;
              a = tmp;      
            } while (a < j);

            return total;

          }

          private static boolean isEven(int a) {
            return (a & 1) == 0;
          }

          public static void main(String[] args) {
            // Notice there is no more loop here
            System.out.println(Fibonacci(4_000_000));
          }
        }

只是为了显示来自@mr1554 代码答案的控制台，显示了前 100 个偶数值，然后所有值的总和为 4850741640，如下所示：

感谢任何帮助，谢谢！

Answer 1

如我所料，您需要一个程序对 Fibonacci 系列的 100 个第一个偶数求和。

这里有一个示例代码，当你运行程序会要求你确定偶数的个数，你想要 100 个值，例如，在 consul 中输入 100:

public static void main(String[] args) {
    int firstNumber = 0;
    int secondNumber = 2;
    System.out.print("Enter the number of odd elements of the Fibonacci Series to sum : ");
    Scanner scan = new Scanner(System.in);
    int elementCount = scan.nextInt(); // number of even values you want
    System.out.print(firstNumber + ", ");
    System.out.print(secondNumber + ", ");


    long sum = 2;
    for (int i = 2; i < elementCount; i++) {
        int nextNumber = firstNumber + secondNumber;
        System.out.print(nextNumber + ", ");

        sum += (nextNumber);

        firstNumber = secondNumber;
        secondNumber = nextNumber;

    }
    System.out.print("...");

    System.out.println("\n" + "the sum of " + elementCount + " values of fibonacci series is: " + sum);
}

Answer 2

你说。

My goal is to calculate the sum of the first 100 even-values Fibonacci numbers.

这个数字很快就会变得非常大。您需要：

使用 BigInteger
使用mod函数判断是否偶数

为此，我本可以从 (1,1) 开始，但它只有一个学期，所以 ...

BigInteger m = BigInteger.ZERO;
BigInteger n = BigInteger.ONE;

BigInteger sumOfEven= BigInteger.ZERO;
int count = 0;
BigInteger t;
while( count < 100) {
    t = n.add(m);
    // check if even
    if (t.mod(BigInteger.TWO).equals(BigInteger.ZERO)) {
        sumOfEven = sumOfEven.add(t);
        count++;
    }
    n = m;
    m = t;
}
System.out.println(sumOfEven);

版画

290905784918002003245752779317049533129517076702883498623284700

另一方面，如果根据您的评论。

My aim is to calculate the sum of the first 100 even numbers

那你也可以这样做

sumFirstNeven = (((2N + 2)N)/2 = (N+1)N

so (101)100 = 10100 and the complexity is O(1)

Answer 3

您需要使用 BigInteger，因为 long 很容易溢出斐波那契的尺度。 BigInteger 也很难检查是奇数还是偶数，但您可以使用 BigInteger::testBit 返回 boolean，如 answer.

中所述

这是一些完整的代码：

BigInteger fibonacciSum(int count, boolean isOdd) {
    int i = 0;
    BigInteger sum = BigInteger.ZERO;
    BigInteger current = BigInteger.ONE;
    BigInteger next = BigInteger.ONE;
    BigInteger temp;

    while (i < count) {
        temp = current;
        current = current.add(next);
        next = temp;

        if ((current.testBit(0) && isOdd) || ((!current.testBit(0) && !isOdd))) {
            sum = sum.add(current);
            i++;
        }
    }

    return sum;
}

或者您可以使用 Stream API:

BigInteger fibonacciSum(int count, boolean isOdd) {
    final BigInteger[] firstSecond = new BigInteger[] {BigInteger.ONE, BigInteger.ONE};
    return Stream.iterate(
            firstSecond, 
            num -> new BigInteger[] { num[1], num[0].add(num[1]) })
        .filter(pair -> 
            (pair[1].testBit(0) && isOdd) || 
            (!pair[1].testBit(0) && !isOdd))
        .limit(count)
        .map(pair -> pair[1])
        .reduce(BigInteger.ZERO, BigInteger::add);
}

无论如何，不要忘记测试一下：

@Test
void test() {
    assertThat(
        fibonacciSum(100, false),
        is(new BigInteger("290905784918002003245752779317049533129517076702883498623284700")));
}

斐波那契数列 - 如何计算前 100 个偶数斐波那契数之和？

Fibonacci sequence - How to calculate the sum of the first 100 even-values Fibonacci numbers?

java

performance

fibonacci