减少计算斐波那契数列的特定代码所需的时间的方法是什么?

huangapple go评论104阅读模式
英文:

way to reduce time taken by this particular code for fibonacci numbers?

问题

import java.util.*;
import java.math.*;

public class FibonacciSumSquares {
    private static BigInteger getFibonacciSumSquares(int n) {
        if (n <= 2) return BigInteger.valueOf(n);
        BigInteger sum = BigInteger.valueOf(2);
        long last = 1, lastTwo = 1, current = 0;
        BigInteger lastBigInteger = BigInteger.ONE;
        BigInteger lastTwoBigInteger = BigInteger.ONE;
        BigInteger currentBigInteger;
        boolean isUsePrimary = true;

        for (int i = 3; i <= n; i++) {
            if (isUsePrimary) {
                current = last + lastTwo;
                current = current * current;
                if (String.valueOf(current).length() < 12) {
                    lastTwo = last;
                    last = current;
                    sum = sum.add(BigInteger.valueOf(current));
                } else {
                    isUsePrimary = false;
                    lastTwoBigInteger = BigInteger.valueOf(lastTwo);
                    lastBigInteger = BigInteger.valueOf(last);
                    currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
                    currentBigInteger = currentBigInteger.pow(2);

                    sum = sum.add(currentBigInteger);
                }
            } //end of outer if
            else {
                currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
                lastTwoBigInteger = lastBigInteger;
                currentBigInteger = currentBigInteger.pow(2);
                lastBigInteger = currentBigInteger;
                sum = sum.add(currentBigInteger);
            }
        }//end of for
        return sum.remainder(BigInteger.valueOf(10));
    }//end of function

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        System.out.println(getFibonacciSumSquares(n));
    }
}
英文:

As a fun project, I started this code where I wanted to find the last digit of the Fibonacci number's squared each time. It works fine but I want to reduce the time taken by it... any suggestions?

trivia: I find the Fibonacci number, square them, and then find the sum.

import java.util.*;
import java.math.*;
public class FibonacciSumSquares {
private static BigInteger getFibonacciSumSquares(int n) {
if(n&lt;=2)return BigInteger.valueOf(n);
BigInteger sum = BigInteger.valueOf(2);
long last = 1, lastTwo = 1, current = 0;
BigInteger lastBigInteger = BigInteger.ONE;
BigInteger lastTwoBigInteger = BigInteger.ONE;
BigInteger currentBigInteger;
boolean isUsePrimary = true;
for (int i = 3; i &lt;=n; i++) {
if (isUsePrimary){
current = last + lastTwo;
current = current * current;
if (String.valueOf(current).length()&lt;12) {
lastTwo = last;
last = current;
sum = sum.add(BigInteger.valueOf(current));
} else {
isUsePrimary = false;
lastTwoBigInteger = BigInteger.valueOf(lastTwo);
lastBigInteger = BigInteger.valueOf(last);
currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
currentBigInteger = currentBigInteger.pow(2);
sum = sum.add(currentBigInteger);
}
} //end of outer if
else {
currentBigInteger = lastBigInteger.add(lastTwoBigInteger);
lastTwoBigInteger=lastBigInteger;
currentBigInteger = currentBigInteger.pow(2);
lastBigInteger= currentBigInteger;
sum = sum.add(currentBigInteger);
}
}//end of for
return sum.remainder(BigInteger.valueOf(10));
}//end of function
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
System.out.println(getFibonacciSumSquares(n));
}

}

答案1

得分: 1

你只需要最后一位数字,这是一个经典的数学技巧 减少计算斐波那契数列的特定代码所需的时间的方法是什么?

通常的情况是,如果你只需要最后一位数字,那么在所有步骤中你可以忽略中间的所有其他数字,只要涉及加法或乘法操作。

你的公式基本上是 f(n+2) = [f(n) + f(n+1)]^2,而对于这个公式,最后一位数字只取决于之前结果的最后一位数字。此外,多个数字相加的和的最后一位只取决于每个相加数字的最后一位。

因此,你可以对每个当前值或和值进行模 10 运算,你不需要使用 BigInteger 甚至 long 来做这个操作,直接使用 int 就可以。

private static int getFibonacciSquaredSumMod10(int n) {
    if (n <= 1)
        return n;
    int sum = 0;
    int last = 1, lastTwo = 1, current = 0;

    for (int i = 2; i <= n; i++) {
        current = last + lastTwo;
        current = (current * current) % 10;
        lastTwo = last;
        last = current;
        sum = (sum + current) % 10;
    }
    return sum;
}
英文:

Oh, you just want the last digit, that's a classic math twist 减少计算斐波那契数列的特定代码所需的时间的方法是什么?

The catch is usually that if you only need the last digit, you can ignore all the other digits in all steps between, as long as it's only adding or multiplying.

Your formula is basically f(n+2) = [f(n) + f(n+1)]^2, and for that, the last digit is only dependent on the last digits of the previous results. Also, the last digit of a sum is only dependent on the last digits of every number you add.

So you can do mod 10 for every current or sum value, and you don't need BigInteger or even long to do that, you can just use int.

private static int getFibonacciSquaredSumMod10(int n) {
if (n &lt;= 1)
return n;
int sum = 0;
int last = 1, lastTwo = 1, current = 0;
for (int i = 2; i &lt;= n; i++) {
current = last + lastTwo;
current = (current * current) % 10;
lastTwo = last;
last = current;
sum = (sum + current) % 10;
}
return sum;
}

huangapple
  • 本文由 发表于 2020年8月27日 16:46:56
  • 转载请务必保留本文链接:https://go.coder-hub.com/63612408.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定