我正在尝试解决Java中Codewars上连续Fib数字的乘积。示例测试运行良好,但是当我单击"尝试"时,它会超时。
我的错误可能是什么?
您可以在此处找到任务详细信息:https://www.codewars.com/kata/product-of-consecutive-fib-numbers
public class ProdFib {
public static long[] productFib(long prod) {
int a = 0;
int ta, ta2= 0;
int a2 = 1;
while (a * a2 <= prod){
ta = a;
ta2 = a2;
a2 = a + a2;
a = ta2;
if(a * a2 == prod){
long[] re = new long[]{a,a2,1};
return re;
}
if(a * a2 > prod){
long[] re = new long[]{a,a2,0};
return re;
}
}
return null;
}
}
您的问题是您将变量定义为int
而不是long
。
如果您尝试使用产品运行程序44361286907595736L
它将进入无限循环。这样做的原因是,当您将两个int
s相乘时,结果也是一个int
。这种刺激是165580141和267914296多重分型的结果。这些是合法的整数,但是当您将它们相乘时,对于整数溢出来说,该数字太大了。所以你得到一个比44361286907595736L
小得多的数字。而且您的循环不会停止。
如果将变量定义为 long
,则不会发生这种情况。这是程序的可读性稍高的版本。
public static long[] productFib(long prod) {
long prev = 0;
long curr = 1;
long multiplied = prev * curr;
while (multiplied < prod) {
long temp = curr;
curr += prev;
prev = temp;
multiplied = prev * curr;
}
return new long[] { prev, curr, multiplied == prod ? 1 : 0 };
}
问题定义:输入:产品 - 想要的产品输出:3 个元素的数组: {F1, F2, result}
其中 F1 是第一个斐波那契数, F2是第二个斐波那契数, 结果等于 1 如果 F1 * F2 = 乘积, 否则:结果 = 0
使用以下公式可以更有效地解决此问题:1. 获取第 n 个斐波那契数的直接公式。2. 获取给定斐波那契数索引的直接公式。
您可以在以下链接中获取相关公式和解释:https://en.wikipedia.org/wiki/Fibonacci_number
这个想法是获取斐波那契数的索引:sqrt(product(
然后我们可以得到下一个和上一个斐波那契数,并将他们的产品与给定的产品进行比较
这是相关的 Java 代码:
private static double phi = (1 + Math.sqrt(5)) / 2;
public static void main(String[] args) {
System.out.println(Arrays.toString(fibProd(800))); // [34, 55, 0]
System.out.println(Arrays.toString(fibProd(714))); // [21, 34, 1]
System.out.println(Arrays.toString(fibProd(15))); // [3, 5, 1]
System.out.println(Arrays.toString(fibProd(40))); // [5, 8, 1]
System.out.println(Arrays.toString(fibProd(2))); // [1, 2, 1]
System.out.println(Arrays.toString(fibProd(3))); // [2, 3, 0]
}
private static long[] fibProd(long product) {
long currentIndex = getFibIndex(Math.round(Math.sqrt(product)));
long currentElement = getFibElement(currentIndex);
long previousElement = getFibElement(currentIndex - 1);
long nextElement = getFibElement(currentIndex + 1);
int c1 = Long.compare(previousElement * currentElement, product);
if(c1 == 0) {
return new long[] {previousElement, currentElement, 1};
}
int c2 = Long.compare(currentElement * nextElement, product);
if(c2 == 0) {
return new long[] {currentElement, nextElement, 1};
}
if (c1 < c2) {
return new long[] {currentElement, nextElement, 0};
} else {
return new long[] {previousElement, currentElement, 0};
}
}
private static long getFibIndex(long item)
{
double m = item * Math.sqrt(5) + 0.5;
return Math.round(Math.log(m) / Math.log(phi));
}
private static long getFibElement(long index) {
return Math.round(Math.pow(phi, index) / Math.sqrt(5));
}
试试这个
public class ProdFib {
public static long[] productFib(long prod) {
int i = 0;
int f1 = 0;
int f2 = 0;
while ((f(i) * f(i + 1) != prod && f(i) * f(i + 1) < prod)) {
i += 1;
f1 = f(i);
f2 = f(i + 1);
}
if (f1 * f2 == prod)
return new long[] { f1, f2, 1 };
else
return new long[] { f1, f2, 0 };
}
public static int f(int i) {
if (i == 0) {
return 0;
}
if (i == 1) {
return 1;
}
return f(i - 2) + f(i - 1);
}
public static void main(String[] args) {
long[] r = productFib(1000);
System.out.println(r[0] + " " + r[1] + " " + r[2]);
}
}