确定数字是否是斐波那契数
我需要编写一个Java代码来检查用户输入的数字是否在斐波那契数列中。
我没有写斐波那契序列输出的问题，但（可能是因为它深夜），我正在努力思考“是否”它是一个斐波那契数的顺序。 我一遍又一遍地重新开始。 它真的在做我的头。
我现在拥有的是第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;
}
阅读维基百科上标题为“识别斐波纳契数字”的部分。
或者，当且仅当5z ^ 2 + 4或5z ^ 2 - 4中的一个是完美正方形时，正整数z是斐波那契数。
或者，您可以继续生成斐波那契数字，直到数字与您的数字相等：如果数字是斐波纳契数字，那么您的数字是斐波那契数字，如果不是，则数字最终会比您的数字更大，并且您可以停止。 然而这是非常低效的。
如果我理解正确，你需要做什么（而不是写出前n个斐波那契数）是确定n是否是斐波那契数。
所以你应该修改你的方法来继续生成斐波那契数列，直到得到一个数字> = n。 如果等于，n是斐波那契数，否则不是。
更新：由@ Moron一再声称基于公式的算法在性能上优于上面的简单算法，我实际上做了基准比较 - 具体地说，在Jacopo的作为生成器算法的解决方案和StevenH的最后一个版本作为基于公式的算法之间。 作为参考，这里是确切的代码：
public static void main(String[] args) {
measureExecutionTimeForGeneratorAlgorithm(1);
measureExecutionTimeForFormulaAlgorithm(1);
measureExecutionTimeForGeneratorAlgorithm(10);
measureExecutionTimeForFormulaAlgorithm(10);
measureExecutionTimeForGeneratorAlgorithm(100);
measureExecutionTimeForFormulaAlgorithm(100);
measureExecutionTimeForGeneratorAlgorithm(1000);
measureExecutionTimeForFormulaAlgorithm(1000);
measureExecutionTimeForGeneratorAlgorithm(10000);
measureExecutionTimeForFormulaAlgorithm(10000);
measureExecutionTimeForGeneratorAlgorithm(100000);
measureExecutionTimeForFormulaAlgorithm(100000);
measureExecutionTimeForGeneratorAlgorithm(1000000);
measureExecutionTimeForFormulaAlgorithm(1000000);
measureExecutionTimeForGeneratorAlgorithm(10000000);
measureExecutionTimeForFormulaAlgorithm(10000000);
measureExecutionTimeForGeneratorAlgorithm(100000000);
measureExecutionTimeForFormulaAlgorithm(100000000);
measureExecutionTimeForGeneratorAlgorithm(1000000000);
measureExecutionTimeForFormulaAlgorithm(1000000000);
measureExecutionTimeForGeneratorAlgorithm(2000000000);
measureExecutionTimeForFormulaAlgorithm(2000000000);
}
static void measureExecutionTimeForGeneratorAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByGeneration(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running generator algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static void measureExecutionTimeForFormulaAlgorithm(int x) {
final int count = 1000000;
final long start = System.nanoTime();
for (int i = 0; i < count; i++) {
isFibByFormula(x);
}
final double elapsedTimeInSec = (System.nanoTime() - start) * 1.0e-9;
System.out.println("Running formula algorithm " + count + " times for " + x + " took " +elapsedTimeInSec + " seconds");
}
static boolean isFibByGeneration(int x) {
int a=0;
int b=1;
int f=1;
while (b < x){
f = a + b;
a = b;
b = f;
}
return x == f;
}
private static boolean isFibByFormula(int num) {
double first = 5 * Math.pow((num), 2) + 4;
double second = 5 * Math.pow((num), 2) - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
private static boolean isWholeNumber(double num) {
return num - Math.round(num) == 0;
}
结果让我感到惊讶：
Running generator algorithm 1000000 times for 1 took 0.007173537000000001 seconds
Running formula algorithm 1000000 times for 1 took 0.223365539 seconds
Running generator algorithm 1000000 times for 10 took 0.017330694 seconds
Running formula algorithm 1000000 times for 10 took 0.279445852 seconds
Running generator algorithm 1000000 times for 100 took 0.030283179 seconds
Running formula algorithm 1000000 times for 100 took 0.27773557800000004 seconds
Running generator algorithm 1000000 times for 1000 took 0.041044322 seconds
Running formula algorithm 1000000 times for 1000 took 0.277931134 seconds
Running generator algorithm 1000000 times for 10000 took 0.051103143000000004 seconds
Running formula algorithm 1000000 times for 10000 took 0.276980175 seconds
Running generator algorithm 1000000 times for 100000 took 0.062019335 seconds
Running formula algorithm 1000000 times for 100000 took 0.276227007 seconds
Running generator algorithm 1000000 times for 1000000 took 0.07422898800000001 seconds
Running formula algorithm 1000000 times for 1000000 took 0.275485013 seconds
Running generator algorithm 1000000 times for 10000000 took 0.085803922 seconds
Running formula algorithm 1000000 times for 10000000 took 0.27701090500000003 seconds
Running generator algorithm 1000000 times for 100000000 took 0.09543419600000001 seconds
Running formula algorithm 1000000 times for 100000000 took 0.274908403 seconds
Running generator algorithm 1000000 times for 1000000000 took 0.10683704200000001 seconds
Running formula algorithm 1000000 times for 1000000000 took 0.27524084800000004 seconds
Running generator algorithm 1000000 times for 2000000000 took 0.13019867100000002 seconds
Running formula algorithm 1000000 times for 2000000000 took 0.274846384 seconds
简而言之，生成器算法的方法在所有正整数值上都优于基于公式的解决方案 - 即使接近最大整数值也是超过两倍！ 基于信念的性能优化非常多;-)
为了记录，修改上述代码以使用long变量而不是int ，生成器算法变得更慢（如预期的那样，因为它现在需要累加long值），公式开始更快的切入点大约为1000000000000L，即1012。
Update2：正如IVlad和Moron指出的那样，我不是浮点计算方面的专家:-)根据他们的建议我改进了这个公式：
private static boolean isFibByFormula(long num)
{
double power = (double)num * (double)num;
double first = 5 * power + 4;
double second = 5 * power - 4;
return isWholeNumber(Math.sqrt(first)) || isWholeNumber(Math.sqrt(second));
}
这将转换点降低到约。 108（对于long版本 - 对于所有int值， int生成器仍然更快）。 毫无疑问，用@Moron建议的方式替换sqrt调用会进一步降低转换点。
我的（和IVlad's）的观点是，总会有一个切入点，低于该切入点，生成器算法会更快。 所以关于哪一个表现更好的说法通常没有意义，只能在上下文中。
而不是通过索引， n ，写一个函数，该函数接受一个限制，并让它生成斐波那契数，直到包括这个限制。 让它返回一个布尔值，取决于它是命中还是跳过限制，并且可以用它来检查该值是否在序列中。
由于它是功课，这样的微调可能是我们应该给你的全部...
链接地址: http://www.djcxy.com/p/86605.html上一篇: Determining whether a number is a Fibonacci number
下一篇: Does a range of integers contain at least one perfect square?