有沒有一種有效的方法來檢查數字是否屬於斐波那契數列?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