英文:
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<=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));
}
}
答案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 <= 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;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论