时间戳

首页 > 解决方案 > 两个连续斐波那契数的乘积 - 代码超时

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

问题描述

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

标签： javatimeoutfibonacci

解决方案

您的问题是您将变量定义为int而不是long.

如果您尝试使用 prod 运行程序，44361286907595736L它将进入无限循环。这样做的原因是当你将两个ints 相乘时，结果也是一个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 };

}

推荐阅读