我正在嘗試在 Java 中解決 Codewars 上連續 Fib 數字的乘積。示例測試運行良好，但是當我單擊嘗試時，它會超時。我的錯誤可能是什么？您可以在此處找到任務詳細信息：https ://www.codewars.com/kata/product-of-consecutive-fib-numberspublic 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; } }
3 回答
函數式編程
TA貢獻1807條經驗 獲得超9個贊
您的問題是您將變量定義為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 };
}
猛跑小豬
TA貢獻1858條經驗 獲得超8個贊
問題定義：輸入：產品 - 想要的產品輸出：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) {
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));
}
萬千封印
TA貢獻1891條經驗 獲得超3個贊
嘗試這個
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]);
}
}
添加回答
舉報
0/150
提交
取消