求在小于O(n)中小于给定数的斐波那契和

Question

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)

Answer 1

您可以简单地使用二分搜索（例如使用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]