在给定数字后查找n个斐波那契数字

有没有办法从给定k开始找到n个斐波那契数字？我知道基本的方法是找到所有从0开始的斐波那契数字，跟踪系列中的数字何时大于k，然后从该点找到n个数字。但有没有更简单的方法？在给定数字后查找n个斐波那契数字

如果我想在5,000,000之后找到3个斐波纳契数字会怎样？我是否必须从0开始找到系列中的所有数字？

此外，如果解决此问题的唯一方法是从0开始，那么哪种方法会更好？迭代还是递归？

谢谢。

来源

2014-09-19 drunkenfist

要回答你的最后一个问题，反复将是远远大于递归更高效的大多数 - 如果不是全部 - 平台。 – 2014-09-19 00:30:21

递归方法需要更长的时间，因此迭代将是提高速度的方法。看看这里的解决方案，类似的方法，可能会为你工作：http://stackoverflow.com/a/24272606/499581 – 2014-09-19 00:31:14

使用golden ratio可以计算出Nth fibonacci。

phi = 1.61803... 

Xn=(phi^n - (1-phi)^n)/sqrt(5)

凡n开始以0

http://en.wikipedia.org/wiki/Golden_ratio#Relationship_to_Fibonacci_sequence

这个公式给你相关的下一个和以前Fibonacci number数的位置。也就是说，如果公式产生natural number，则它是Nth Fibonacci number。如果产生number with decimals它属于前一个和下一个natural number之间。如果数字为2.7，它是2和3之间，所以你正在寻找fib(3)，fib(4)和fib(5)

或者您可以使用Gessel formula。

A number is a Fibonacci if and only if 

5*n^2+4 is a square number or 5*n^2-4 is a square number

所以，你可以开始计数，你``N（在本例中5*10^6），直到你遇到两个第一Fibonacci。

来源

2014-09-19 00:33:35 ssedano

谢谢，但我怎么会发现5,000,000后3斐波那契数字？我应该插入X（n）的随机值，使X（n）> 5 mil和X（n-1）<5 mil？否则，这将与迭代方法相同。 – drunkenfist 2014-09-19 00:56:11

@drunkenfist请注意，由于'n'变大，'（1-phi）^ n'变得非常小，所以对于大'n'方程约为'Xn = phi^n/sqrt（5）'。这意味着你可以用'n = log（Xn * sqrt（5））/ log（phi）'来找到'n'的近似值。 – user3386109 2014-09-19 03:08:28

@ user3386109我不知道我非常理解你想说什么。但是如果你的意思是用上述公式中的5mil值代替，那么这将是错误的，因为5mil可能不是斐波纳契数。问题并不是说给定的'k'是斐波那契数。它可以是任何随机数字。 – drunkenfist 2014-09-19 04:04:51

你可能想看看这个 http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

虽然我不认为这是值得使用的N个大的输入，此方法使用比奈的公式。

来源

2014-09-19 00:34:02

斐波纳契数列呈指数级增长，这意味着在超过500万之前，您不必做很多迭代。事实上，第37次斐波纳契数字在500万以上。

，所以我不会再显得比天真迭代，这里的Python：

def fib(a0, k): 
    a, b = 0, 1 
    while a < a0: 
     a, b = b, a + b 
    for _ in xrange(k): 
     yield a 
     a, b = b, a + b 

print list(fib(5000000, 3))

来源

2014-09-20 02:40:15

在给定数字后查找n个斐波那契数字

回答

相关问题