判断两个斐波纳契数

Question

我有许多斐波那契数，如果我要确定两个斐波纳契数是否是相邻或不相邻的邻居，一个基本的方法如下：

1. 获得第一个斐波那契数的指数数说I1
2. 获取第二斐波那契数的指标，说I2
3. 获取I1-I2的绝对值，即| I1-I2 | 如果该值为1，则返回true。 否则返回false。

在第一步和第二步中，可能需要多次比较才能通过访问数组来获取正确的索引。

在第三步，它需要一个减法和一个绝对操作。

我想知道是否存在另一种方法来快速确定斐波那契数的邻接关系。

我不在乎这个问题是否可以通过数学或任何黑客技术来解决。

如果有人有一些想法，请让我知道。非常感谢！

Answer 1

无需找到两个号码的索引。

鉴于这两个数属于斐波那契数列，如果它们的差值大于最小值。其中的数字是那两个不相邻的。其他方面他们是。

由于斐波纳契数列如下以下规则：

F(n) = F(n-1) + F(n-2) where F(n)>F(n-1)>F(n-2). 
So F(n) - F(n-1) = F(n-2) , 
=> Diff(n,n-1) < F(n-1) < F(n-k) for k >= 1 

之间的两个相邻的Fibonaci数差将总是小于它们之间的分钟数。

注意：只有当数字属于斐波那契数列时，这才有效。

Answer 2

通过Binet's formula，第n个斐波那契数大约是sqrt(5)*phi**n，其中phi是黄金口粮。您可以使用基地披对数轻松恢复索引：

from math import log, sqrt 

def fibs(n): 
    nums = [1,1] 
    for i in range(n-2): 
     nums.append(sum(nums[-2:])) 
    return nums 

phi = (1 + sqrt(5))/2 

def fibIndex(f): 
    return round((log(sqrt(5)*f,phi))) 

为了测试这个：

for f in fibs(20): print(fibIndex(f),f) 

输出：

2 1 
2 1 
3 2 
4 3 
5 5 
6 8 
7 13 
8 21 
9 34 
10 55 
11 89 
12 144 
13 233 
14 377 
15 610 
16 987 
17 1597 
18 2584 
19 4181 
20 6765 

当然，

def adjacentFibs(f,g): 
    return abs(fibIndex(f) - fibIndex(g)) == 1 

这以失败- 但是对于这种边界情况显式测试特殊逻辑没有多大意义。如果你愿意，可以添加它。

在某个阶段，浮点四舍五入错误将成为一个问题。为此，您需要用整数对数算法（例如涉及二进制搜索的算法）替换math.log。

在编辑：

我集中于如何恢复指数（而且我会信守答案，因为这是在自己的权利一个有趣的问题）的问题，但作为@LeandroCaniglia指出了他们的优秀评论，如果你想要做的只是检查两个斐波那契数是否相邻，这是过度的，因为Binet公式的另一个结果是足够大的相邻斐波那契数有一个与phi相差很小的比率。你可以这样做：

def adjFibs(f,g): 
    f,g = min(f,g), max(f,g) 
    if g <= 34: 
     return adjacentFibs(f,g) 
    else: 
     return abs(g/f - phi) < 0.01 

这假设他们确实是斐波那契数。基于索引的方法可以用来验证它们（计算索引，然后使用具有该索引的完整Binet公式）。

Answer 3

只需计算它们之间的差异即可。如果它小于它们相邻的两个数字中的较小者，如果它更大，则不是。

在Fibonacci序列中的每个三元组A，B，C符合规则

c = a + b 

因此，对于每对相邻的Fibonaccis (x, y)的，它们(y-x)之间的差是等于先前斐波纳契的值，这当然必须小于x。

如果2 Fibonaccis，如(x, z)不相邻，那么他们的差异必须大于两者中的较小者。至少（如果它们相距一个斐波纳契），差值将等于它们之间的斐波那契数（这当然是大于比两个数中较小的那个）。

由于对（A，B，C，d）

since c= a+b 
and d = b+c 
then d-b = (b+c) - b = c