有没有一种有效的方法来检查数字是否属于斐波那契数列?JS:检查数字是否属于斐波那契数列(无循环)
我见过很多循环的例子,它们在数组中创建序列并每次检查序列的新生成序号是否等于输入数字。有另一种方法吗?
有没有一种有效的方法来检查数字是否属于斐波那契数列?JS:检查数字是否属于斐波那契数列(无循环)
我见过很多循环的例子,它们在数组中创建序列并每次检查序列的新生成序号是否等于输入数字。有另一种方法吗?
http://www.geeksforgeeks.org/check-number-fibonacci-number/
这链路的信息,有关于斐波纳契数的特殊品质,这意味着,一些是斐波那契当且仅当一个或两个(5和* N 2 + 4)或(5 * N 2 - 4 )是一个完美的广场。
所以,
function (num) {
if (isSquare(5*(num*num)-4) || isSquare(5*(num*num)+4) {
return true;
} else { return false; }
}
然后isSquare将只是一个简单的检查功能。
编辑:值得注意的是,虽然这是一个更有效和简单的方法来找到斐波纳契数字,它确实有一个上限。在大约第70个斐波纳契数及以上时,您可能会看到问题,因为数字太大。
def is_squared(number):
temp_root = math.sqrt(number);
temp_root = int(temp_root);
return (temp_root * temp_root == number);
def check_all_fibo(test_number_list):
result_fibo_list = [];
for item in test_number_list:
if item==0 or item == 1 or item == 2:
result_fibo_list.append(item);
continue;
if is_squared(5 * item * item - 4) or is_squared(5 * item * item + 4):
result_fibo_list.append(item);
return result_fibo_list;
这是一个由我执行的python实现。但请记住,该公式只适用于纤维不太大的情况。
function isSquare(n) {
return n > 0 && Math.sqrt(n) % 1 === 0;
};
//Equation modified from http://www.geeksforgeeks.org/check-number-fibonacci-number/
function isFibonacci(numberToCheck)
{
// numberToCheck is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both
// is a perferct square
return isPerfectSquare(5*numberToCheck*numberToCheck + 4) ||
isPerfectSquare(5*numberToCheck*numberToCheck - 4);
}
for(var i = 0; i<= 10000; ++i) {
console.log(i + " - " + isFibonacci(i));
}
虽然这很可能会失败。
你可以做一个上限的指数搜索,然后以'f0'作为下界并对一个有效的斐波那契数进行二分搜索。我不确定是否有可能更快,请问一位数学家。 – ASDFGerte