testing一个数字是否是斐波那契
我知道如何制作斐波纳契数列表，但我不知道如何testing一个给定的数字是否属于斐波那契列表 – 想到的一种方法是生成fib列表。 数字到这个数字，看看它是否属于数组，但是必须有另一个更简单和更快的方法。
有任何想法吗 ？
一个非常好的testing是N是一个斐波那契数，当且仅当5 N^2 + 4或5N^2 – 4是一个平方数。 有关如何有效地testing数字的方法，请参阅SO讨论 。
希望这可以帮助
正整数ω是斐波那契数当且仅当5ω2 + 4和5ω2 – 4中的一个是完美正方形。
看到Faboulous斐波那契数字更多。
虽然有几个人指出了完美平方的解决scheme，但它涉及到一个斐波那契数的平方，经常导致一个巨大的产品。
有less于80个斐波纳契数字，甚至可以保存在一个标准的64位整数。
这是我的解决scheme，其运行完全小于要testing的数量。
（用C＃编写，使用像double和long这样的基本types，但是对于更大的types，该algorithm应该可以正常工作）。
static bool IsFib(long T, out long idx) { double root5 = Math.Sqrt(5); double phi = (1 + root5) / 2; idx = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 ); long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5); return (u == T); }
我写了这个答案4年多了，一个评论者询问了第二个参数，通过out 。
参数＃2是Fibonacci序列中的“Index”。
如果要testing的值， T是一个斐波那契数，那么idx将是Fibonacci序列中该数字的从1开始的索引。 （除了一个明显的例外）
斐波那契数列是1 1 2 3 5 8 13等
3是序列中的第4个数字： IsFib(3, out idx); 将返回true和值4 。
8是序列中的第6个数字： IsFib(8, out idx); 将返回true和值6 。
13号是第7号; IsFib(13, out idx); 将返回true值7 。
唯一的例外是IsFib(1, out idx); ，即使值1出现在索引1和2中，也将返回2。
如果IsFib传递了一个非Fibonacci数字，它将返回false ，并且idx的值将是最大的斐波那契数的索引，小于T
16不是斐波那契值。
IsFib(16, out idx); 将返回false和值7 。
您可以使用Binet的公式将索引7转换为斐波那契值13，这是最大的数字小于16。
#!/bin/bash victim="144" curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null if [[ $? -eq 0 ]] ; then echo "$victim is a fibonacci number" else echo "$victim aint" fi
如果你的数字是有限的大小，比简单地把所有的斐波那契数字放在一个哈希表的上限之下，testing遏制就可以了。 斐波纳契数字很less（例如，低于5毫升只有38），因为它们成倍增长。
如果你的数字不是有界的大小，那么build议的平方检测技巧几乎肯定比生成斐波那契数列要慢，直到find或超过数字为止。
正整数ω是一个斐波那契数
当且仅当5ω2 + 4和5ω2 – 4之一是一个完美的正方形
来自Alfred Posamentier和Ingmar Lehmann的（Fabulous）FIBONACCI Numbers
bool isFibonacci(int w) { double X1 = 5 * Math.Pow(w, 2) + 4; double X2 = 5 * Math.Pow(w, 2) - 4; long X1_sqrt = (long)Math.Sqrt(X1); long X2_sqrt = (long)Math.Sqrt(X2); return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ; }
我从这个源复制它
打印1k和10k之间的斐波纳契数字片段。
for (int i = 1000; i < 10000; i++) { if (isFibonacci(i)) Console.Write(" "+i); }
OMG只有四个 ！
用其他方法
from math import * phi = 1.61803399 sqrt5 = sqrt(5) def F(n): return int((phi**n - (1-phi)**n) /sqrt5) def isFibonacci(z): return F(int(floor(log(sqrt5*z,phi)+0.5))) == z print [i for i in range(1000,10000) if isFibonacci(i)]
迈向一个解决scheme，看看比奈的公式。
（在维基百科上查找斐波那契数字下的“封闭expression式”）
它说，斐波那契数列的序列是由一个简单的封闭公式创build的：
我相信如果你解决了n ，并testing如果n是一个整数，你会得到你的答案。
编辑为@psmears指出，同样的维基百科文章也有检测斐波纳契数字的一节。 维基百科是一个很好的来源。
请参阅维基百科有关斐波纳契数字的文章 “识别斐波纳契数字”一节。
由于斐波纳契数字以指数forms增长，所以您build议的方法非常快。 另一个是这个 。
来自维基百科： http : //en.wikipedia.org/wiki/Fibonacci_number
一个正整数z是斐波那契数当且仅当5z ^ 2 + 4或5z ^ 2 – 4中的一个是一个完美的正方形。
根据我和psmears早先的答案，我写了这个C＃代码。
它慢慢地经过这些步骤，可以明显地减less和优化：
// Input: T: number to test. // Output: idx: index of the number in the Fibonacci sequence. // eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8) // Return value: True if Fibonacci, False otherwise. static bool IsFib(long T, out int idx) { double root5 = Math.Sqrt(5); double PSI = (1 + root5) / 2; // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number double a; a = T*root5; a = Math.Log(a) / Math.Log(PSI); a += 0.5; a = Math.Floor(a); idx = (Int32)a; long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5); if (u == T) { return true; } else { idx = 0; return false; } }
testing显示，这对第一个69斐波那契数字的作品，但打破了70。
F(69) = 117,669,030,460,994 - Works F(70) = 190,392,490,709,135 - Fails
总之，除非你使用BigInttypes的库，否则最好有一个简单的Fibonacci数字查找表并检查，而不是运行一个algorithm。
前300个号码的列表可以在线获得。
但是这个代码确实提供了一个可行的algorithm，只要你有足够的精度，并且不会溢出你的数字表示系统。
斐波纳契数的一般expression式为F（n）= [[（1 + sqrt（5））/ 2] sup n + 1 – [（1-sqrt（5））/ 2] sup n + 1] / sqrt （5）…..（*）对于大n，第二指数变为零，进行数值运算得到F（n）= [（1.618）sup n + 1] /2.236
如果K是要testing的数字，那么log（k * 2.2336）/ log（1.618）应该是一个整数！
例如K等于13我的计算器给出答案7.00246对于K等于14答案是7.1564。
您可以通过取最接近的整数作为答案来增加结果的置信度，并用（*）替代确认结果为K.
回复：艾哈迈德的代码 – 一个简单的方法，没有recursion或指针，相当天真，但要求几乎没有任何计算能力的真正titanic数字（大约2N添加validation第N个纤维数量，这在现代机器上将需要几毫秒最坏的情况）
如果发现任何东西，则返回pos;如果不是，则返回0（C / C ++将任何值！= 0视为true，所以相同的最终结果）
int isFib (long n) { int pos = 2; long last = 1; long current = 1; long temp; while (current < n) { temp = last; last = current; current = current + temp; pos++; } if (current == n) return pos; else return 0; }
你处理的数字有多大？
查找表能为你工作吗？ （您可以search的预先计算的数字列表）
还有一个封闭的expression式 ，我想你可以通过分析来获得答案（尽pipe我不是math家，所以我不能保证这个build议是有道理的）
我在这里介绍的方法上运行了一些基准testing，并join了简单的附加部分，预先计算一个数组，并将结果记入散列。 至less对于Perl来说，平方法比对数方法快一点，速度可能快20％。 正如abelenky所指出的那样，这是一个平衡位数的空间。
当然，最快的方法是将所有斐波那契数字散列在您的域空间中。 沿着abelenky提出的另一个观点，这些吸盘中只有94个小于2 ^ 64。
你应该预先计算它们，并把它们放在一个Perl哈希，Python字典，或其他任何东西。
斐波那契数的性质是非常有趣的，但是用它们来确定一个计算机程序中的某个整数是否是一个就像是每次程序开始时写一个子程序来计算pi。
这是我的解决scheme，我不确定它是否是基准。 我希望这有帮助！
def is_fibonacci?(i) a,b=0,1 until b >= i a,b=b,a+b return true if b == i end end
a，b = b，a + b正在做什么
0, 1 = 1, 0 +1 1, 1 = 1, 1 + 1 1, 2 = 2, 1 + 2 2, 3 = 3, 2 + 3 fib1 = fib2 fib2 = fib1 + fib2
一个Scala版本 –
def isFib(n: Int): Boolean = { def checkFib(f1: Int = 1, f2: Int = 1): Boolean = { if(n == f1 || n == f2) true else if(n < f2) false else checkFib(f2, f1+f2) } checkFib() }
Java解决scheme可以做到如下。 但仍然可以优化
以下解决scheme适用于
- 1≤T≤10^ 5
- 1≤N≤10^ 10
T是testing用例的数量，N是数字的范围
import java.util.Scanner; import java.math.BigDecimal; import java.math.RoundingMode; public class FibonacciTester { private static BigDecimal zero = BigDecimal.valueOf(0); private static BigDecimal one = BigDecimal.valueOf(1); private static BigDecimal two = BigDecimal.valueOf(2); private static BigDecimal four = BigDecimal.valueOf(4); private static BigDecimal five = BigDecimal.valueOf(5); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); BigDecimal[] inputs = new BigDecimal[n]; for (int i = 0; i < n; i++) { inputs[i] = sc.nextBigDecimal(); } for (int i = 0; i < inputs.length; i++) { if (isFibonacci(inputs[i])) System.out.println("IsFibo"); else System.out.println("IsNotFibo"); } } public static boolean isFibonacci(BigDecimal num) { if (num.compareTo(zero) <= 0) { return false; } BigDecimal base = num.multiply(num).multiply(five); BigDecimal possibility1 = base.add(four); BigDecimal possibility2 = base.subtract(four); return (isPerfectSquare(possibility1) || isPerfectSquare(possibility2)); } public static boolean isPerfectSquare(BigDecimal num) { BigDecimal squareRoot = one; BigDecimal square = one; BigDecimal i = one; BigDecimal newSquareRoot; int comparison = -1; while (comparison != 0) { if (comparison < 0) { i = i.multiply(two); newSquareRoot = squareRoot.add(i).setScale(0, RoundingMode.HALF_UP); } else { i = i.divide(two); newSquareRoot = squareRoot.subtract(i).setScale(0, RoundingMode.HALF_UP); } if (newSquareRoot.compareTo(squareRoot) == 0) { return false; } squareRoot = newSquareRoot; square = squareRoot.multiply(squareRoot); comparison = square.compareTo(num); } return true; } }
int isfib(int n /* number */, int &pos /* position */) { if (n == 1) { pos=2; // 1 1 return 1; } else if (n == 2) { pos=3; // 1 1 2 return 1; } else { int m = n /2; int p, q, x, y; int t1=0, t2 =0; for (int i = m; i < n; i++) { p = i; q = n -p; // p + q = n t1 = isfib(p, x); if (t1) t2 = isfib(q, y); if (t1 && t2 && x == y +1) { pos = x+1; return 1; //true } } pos = -1; return 0; //false } }
这个怎么样？
#include <stdio.h> #include <math.h> int main() { int number_entered, x, y; printf("Please enter a number.\n"); scanf("%d", &number_entered); x = y = 5 * number_entered^2 + 4; /*Test if 5N^2 + 4 is a square number.*/ x = sqrt(x); x = x^2; if (x == y) { printf("That number is in the Fibonacci sequence.\n"); } x = y = 5 * number_entered^2 - 4; /*Test if 5N^2 - 4 is a square number.*/ x = sqrt(x); x = x^2; if (x == y) { printf("That number is in the Fibonacci sequence.\n"); } else { printf("That number isn't in the Fibonacci sequence.\n"); } return 0; }
这会工作吗？
