我正在寻找最快的方法来确定一个long值是否是一个完美的正方形(即它的平方根是另一个整数):
Math.sqrt()
函数以简单的方式完成了它,但我想知道是否有办法通过将自己限制为仅整数域来更快地完成它.这是我现在正在做的非常简单直接的方式:
public final static boolean isPerfectSquare(long n)
{
if (n < 0)
return false;
long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}
注意:我在许多Project Euler问题中使用此函数.因此,没有其他人必须维护此代码.而这种微优化实际上可以产生影响,因为部分挑战是在不到一分钟的时间内完成每个算法,并且在某些问题中需要将此函数调用数百万次.
我尝试过不同的问题解决方案:
0.5不需要添加Math.sqrt()的结果,至少在我的机器上没有.Math.sqrt().这可能是因为Math.sqrt()使用类似牛顿方法的东西,但在硬件中实现,因此它比Java快得多.此外,牛顿的方法仍然需要使用双打.Math.sqrt().or在C++中使用语句比使用语句更快switch,但在Java和C#中,or和之间似乎没有区别switch.or我会说,而不是开关或声明if(lookup[(int)(n&0x3F)]) { test } else return false; …是否有任何算法来计算子线性时间内的第n个斐波纳契数？
有许多计算任意n的F(n)的方法,其中许多方法具有很大的运行时和内存使用率.
但是,假设我想问相反的问题:
给定F(n)n> 2,n是什么？
(由于F(1)= F(2)= 1并且没有明确的逆,因此n> 2限制在那里.
解决这个问题最有效的方法是什么？通过枚举斐波纳契数并在达到目标数时停止,可以很容易地在线性时间内完成此操作,但有没有比这更快的方法呢？
编辑:目前,这里发布的最佳解决方案使用O(log n)内存在O(log n)时间内运行,假设数学运算在O(1)中运行并且机器字可以在O(1)空间中保存任何数字.我很好奇是否可以降低内存要求,因为你可以使用O(1)空间计算斐波纳契数.
我需要编写一个Java代码来检查用户输入的数字是否在Fibonacci序列中.
我没有问题写Fibonacci序列输出,但(可能是因为它深夜)我正在努力想到"是否"它是斐波纳契数的序列.我一遍又一遍地开始.它确实在我的脑海里.
我现在拥有的是第n个.
public static void main(String[] args)
{
ConsoleReader console = new ConsoleReader();
System.out.println("Enter the value for your n: ");
int num = (console.readInt());
System.out.println("\nThe largest nth fibonacci: "+fib(num));
System.out.println();
}
static int fib(int n){
int f = 0;
int g = 1;
int largeNum = -1;
for(int i = 0; i < n; i++)
{
if(i == (n-1))
largeNum = f;
System.out.print(f + " ");
f = f + g;
g = f - g;
}
return largeNum; …我需要编写一个程序来递归地检查一个数字是否是斐波那契数列；迭代地完成同样的任务很容易；递归地找到第 n 个斐波那契数也很容易，但我陷入了如何使用递归检查一个数是否是斐波那契数的困境。这是查找第 n 个 fib 的代码。数字：
int fib(int n){
if (n <= 1){
return n;
}else {
return (fib(n-1) + fib (n-2));
}
}
我不知道该怎么做是如何修改上面的代码来检查给定的数字是否是斐波那契？