我正在尝试解决一个问题，部分解决方案是找到小于输入数的芬波那契数之和。现在输入数字的上限是10**9。我已将问题简化为以下 O(n) 解决方案，我想知道是否有更有效的解决方案。
b=[1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764,
10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039,
1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816,
39088168, 63245985, 102334154, 165580140, 267914295, 433494436, 701408732, 1134903169, 1836311902]
def test_lambda(a):
list_numbers= filter(lambda x: x<=a, b)
return len(list_numbers)
如您所见，我正在将列表 b 的值与给定输入进行比较，并返回小于给定数字的元素。
b 是到该索引为止的斐波那契数和的列表，因此第一个数字是 1，总和是 1，第二个是 1 总和是 2，第三个 2 总和是 4...
最佳答案
您可以简单地使用二进制搜索(例如使用 bisect_right 函数):
from bisect import bisect_right
def test_lambda(a):
return bisect_right(list_numbers,a)
或者如果你想要小于输入数字的总和，你可以使用:
from bisect import bisect_right
def less_than(a):
return a[bisect_right(list_numbers,a)-1]
这是有效的，因为列表是预先计算的并且是严格递增的。所以这意味着它是一个有序列表。二进制搜索在 O(log n) 中工作，因此可以高效地完成搜索。此外，我会将 0 添加到列表中(在第一个位置)，这样以 0 作为输入的查询也会得到解析:
from bisect import bisect_right
b=[0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583,
4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810,
514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351,
24157816, 39088168, 63245985, 102334154, 165580140, 267914295, 433494436,
701408732, 1134903169, 1836311902
]
def less_than(a):
return a[bisect_right(list_numbers,a)-1]
关于python - 在小于 O(n) 的时间内找到小于给定数字的斐波那契和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45488137/