java - 斐波那契数列，如何找到该数(java)

Question

我的任务是找到斐波那契列表中第一个非零成员的索引，该索引可以被这个某个值整除(在下面的示例中，这些值是:17 12 61)。因此，我创建了斐波那契数列，遍历该数列除以每个成员并检查余数是否为零:

    public static void main(String[] args) {

    String stringInputValues = "17 12 61";
    Scanner scan = new Scanner(stringInputValues);

    int i = 0;
    BigInteger value = BigInteger.ZERO;;

    //start create Fibonacci numbers
    int N = 9000;
    BigInteger[] fibArray = new BigInteger[N + 1];
    fibArray[0] = BigInteger.ZERO;
    fibArray[1] = BigInteger.ONE;
    for (i = 2; i <= N; i++) {
        fibArray[i] = fibArray[i - 1].add(fibArray[i - 2]);

    }
    //end create Fibonacci numbers
    while (scan.hasNext()) {
        value = BigInteger.valueOf(scan.nextLong());
        for (i = 0; i <= fibArray.length - 1; i++) {
            if (i > 0 && fibArray[i].remainder(value) == BigInteger.ZERO) {

                System.out.println(i);
                break;
            }
        }
    }
}

这不适用于分隔符的大值(数字太大以至于我得到java.lang.OutOfMemoryError:Java堆空间)，例如233328 433156 1032566 而不是 17 12 61 我觉得我的算法太简单而且效率低下。你能帮我做一个更有效的吗？ 谢谢!

Answer 1

关键是一次计算一个斐波那契数。该解决方案有一个方法，该方法返回可被参数整除的斐波那契数的索引:

import java.math.BigInteger;

public class FibonacciDivider {

    public static void main(String [] args) {
        int [] input = {233328, 433156, 1032566};
        for (int val: input) {
            System.out.println("index of Fibo. num. divisible by " + val +
                    ": " +  findIndexOfFibonacciWithDivisor(BigInteger.valueOf(val)));
        }
    }

    public static int findIndexOfFibonacciWithDivisor(BigInteger divisor) {
        BigInteger a = BigInteger.ZERO;
        BigInteger b = BigInteger.ONE;
        int index = 0;
        while (true) {
            index++;
            BigInteger c = b.add(a);
            // the mod() method returns the remainder
            if (c.mod(divisor).equals(BigInteger.ZERO)) return index;
            a = b;
            b = c;
        }
    }
}

输出(到目前为止!)是:

index of Fibo. num. divisible by 233328: 1619
index of Fibo. num. divisible by 433156: 281

它仍在 1032566 上启动!

更新:斐波那契指数。编号能被 1032566 整除:1548851