大斐波那契数的最后一位快速算法

Question

我正在尝试使用 java 求解斐波那契数列，但我的代码需要很长时间才能处理大数。

问题描述任务。给定一个整数，找到 th 斐波那契数 </code> 的最后一位（即 mod 10）。 输入格式。输入由一个整数组成。 约束。 <code>0 ≤ ≤ 10⁷.

输出格式。输出</code>.的最后一位 我的代码： <pre><code>public class FibonacciLastDigit { private static int getFibonacciLastDigitNaive(int n) { if (n <= 1) { return n; } BigInteger first = BigInteger.ZERO; BigInteger second = BigInteger.ONE; BigInteger temp; for (int i = 1; i < n; i++) { temp = first.add(second); first = second; second = temp; } return second.mod(BigInteger.TEN).intValue(); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); System.out.println(getFibonacciLastDigitNaive(n)); }}

如果输入 = 613455，我的代码将失败，获取值需要 30 秒，允许的最大时间为 1.5 秒。

我不得不使用大整数，因为 long 不够用。

Answer 1

斐波那契数列的最后一位有一个循环。每 60 个数字重复一次。因此，只需构建前 60 个数字的最后一位数字的 table，然后对输入执行模 60 运算和 table 查找。

您可能会在任何在线（或离线）table 斐波那契数列中看到周期。最下面一个link。

为了构建table，对于每个计算出的数字，如果它超过 9，您可以减去 10，因为您只需要最后一位，并且每个数字的最后一位仅取决于两个数字的最后一位以前的数字。您可以使用 int 数学（您既不需要 long 也不需要 BigInteger）。

Link: The first 300 Fibonacci numbers, factored

Answer 2

您的实现确实很天真，因为您被要求获取斐波那契数的最后一位，而不是实际的斐波那契数本身。您只需要保留最后一位数字，其他数字无关紧要。

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    System.out.println(getFibonacciLastDigit(n));
}

private static int getFibonacciLastDigit(int n) {
    if (n <= 1) {
        return n;
    }
    int first = 0;
    int second = 1;
    int temp;

    for (int i = 1; i < n; i++) {
        temp = (first + second) % 10;
        first = second;
        second = temp;
    }
    return second;
}

Answer 3

py中的代码必须是

lookup = {0:0,1:1}
N = int(input())
for i in range(2,N+1):
       lookup[i] = (lookup[i-1] + lookup[i-1])%10
print(lookup[N])

Answer 4

这里附上一个c++的程序，可以用java写程序的逻辑。通过这段代码，我们只需要找到第 60 个斐波那契数。而且这将执行得非常快，也不需要持有大量数字。

#include <iostream>

using namespace std;

long long int findOutTheFibonacciNumber(int n)
{
    int number = n % 60;
    if (number <= 1)
    {
        return number;
    }
    else
    {
        long long int a = 0;
        long long int b = 1;
        long long int c = 1;
        for (int i = 2; i <= number; i++)
        {
            c = (long long)a + b;
            a = b;
            b = c;
        }
        return c % 10;
    }
}

int main()
{
    int n;
    cin >> n;
    cout << findOutTheFibonacciNumber(n);
    return 0;
}

大斐波那契数的最后一位快速算法

Last Digit of a Large Fibonacci Number fast algorithm

java

algorithm

biginteger

fibonacci