两个连续斐波那契数的乘积 - 代码超时

Question

我正在尝试在 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;

   }

 }

Answer 1

您的问题是您将变量定义为int而不是long.如果您尝试使用 prod 运行程序，44361286907595736L它将进入无限循环。这样做的原因是当你将两个ints 相乘时，结果也是一个int。该产品是 165580141 和 267914296 相乘的结果。这些是合法的整数，但是当你将它们相乘时，这个数字对于整数溢出来说太大了。所以你得到一个比 低得多的数字44361286907595736L。你的循环不会停止。如果您将变量定义为long，则不会发生这种情况。这是您的程序的可读性稍强的版本。public static long[] productFib(long prod) {&nbsp; &nbsp; long prev = 0;&nbsp; &nbsp; long curr = 1;&nbsp; &nbsp; long multiplied = prev * curr;&nbsp; &nbsp; while (multiplied < prod) {&nbsp; &nbsp; &nbsp; &nbsp; long temp = curr;&nbsp; &nbsp; &nbsp; &nbsp; curr += prev;&nbsp; &nbsp; &nbsp; &nbsp; prev = temp;&nbsp; &nbsp; &nbsp; &nbsp; multiplied = prev * curr;&nbsp; &nbsp; }&nbsp; &nbsp; return new long[] { prev, curr, multiplied == prod ? 1 : 0 };}

Answer 2

问题定义：输入：产品 - 想要的产品输出：3 个元素的数组：{F1，F2，结果}其中 F1 是第一个斐波那契数，F2 是第二个斐波那契数，如果 F1 * F2 = 乘积，则结果等于 1，否则：结果 = 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) {&nbsp;&nbsp; System.out.println(Arrays.toString(fibProd(800))); // [34, 55, 0]&nbsp; System.out.println(Arrays.toString(fibProd(714))); // [21, 34, 1]&nbsp; System.out.println(Arrays.toString(fibProd(15))); // [3, 5, 1]&nbsp; System.out.println(Arrays.toString(fibProd(40))); // [5, 8, 1]&nbsp; System.out.println(Arrays.toString(fibProd(2))); // [1, 2, 1]&nbsp; System.out.println(Arrays.toString(fibProd(3))); // [2, 3, 0]}private static long[] fibProd(long product) {&nbsp; &nbsp; long currentIndex = getFibIndex(Math.round(Math.sqrt(product)));&nbsp; &nbsp; long currentElement = getFibElement(currentIndex);&nbsp; &nbsp; long previousElement = getFibElement(currentIndex - 1);&nbsp; &nbsp; long nextElement = getFibElement(currentIndex + 1);&nbsp; &nbsp; int c1 = Long.compare(previousElement * currentElement, product);&nbsp; &nbsp; if(c1 == 0) {&nbsp; &nbsp; &nbsp; &nbsp; return new long[] {previousElement, currentElement, 1};&nbsp; &nbsp; }&nbsp; &nbsp; int c2 = Long.compare(currentElement * nextElement, product);&nbsp; &nbsp; if(c2 == 0) {&nbsp; &nbsp; &nbsp; &nbsp; return new long[] {currentElement, nextElement, 1};&nbsp; &nbsp; }&nbsp; &nbsp; if (c1 < c2) {&nbsp; &nbsp; &nbsp; &nbsp; return new long[] {currentElement, nextElement, 0};&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; return new long[] {previousElement, currentElement, 0};&nbsp; &nbsp; }}private static long getFibIndex(long item)&nbsp;{&nbsp;&nbsp; &nbsp; double m = item * Math.sqrt(5) + 0.5;&nbsp; &nbsp; return Math.round(Math.log(m) / Math.log(phi));}private static long getFibElement(long index) {&nbsp; &nbsp; return Math.round(Math.pow(phi, index)&nbsp; / Math.sqrt(5));&nbsp;}

Answer 3

尝试这个public class ProdFib {public static long[] productFib(long prod) {&nbsp; &nbsp; int i = 0;&nbsp; &nbsp; int f1 = 0;&nbsp; &nbsp; int f2 = 0;&nbsp; &nbsp; while ((f(i) * f(i + 1) != prod && f(i) * f(i + 1) < prod)) {&nbsp; &nbsp; &nbsp; &nbsp; i += 1;&nbsp; &nbsp; &nbsp; &nbsp; f1 = f(i);&nbsp; &nbsp; &nbsp; &nbsp; f2 = f(i + 1);&nbsp; &nbsp; }&nbsp; &nbsp; if (f1 * f2 == prod)&nbsp; &nbsp; &nbsp; &nbsp; return new long[] { f1, f2, 1 };&nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; return new long[] { f1, f2, 0 };}public static int f(int i) {&nbsp; &nbsp; if (i == 0) {&nbsp; &nbsp; &nbsp; &nbsp; return 0;&nbsp; &nbsp; }&nbsp; &nbsp; if (i == 1) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; }&nbsp; &nbsp; return f(i - 2) + f(i - 1);}public static void main(String[] args) {&nbsp; &nbsp; long[] r = productFib(1000);&nbsp; &nbsp; System.out.println(r[0] + " " + r[1] + " " + r[2]);}}