求fibonacci一致子阵的和

Question

我们有一个输入整数，比方说13。我们可以找到fibonacci数的一致子数组，它的总和为10-2，3，5。我需要找到下一个数，它不是一致子数组的和。在这种情况下，这个数字将是14。我有这段代码，但问题是，可以优化它，使其不迭代从左指针=1和右指针=1开始的所有N，但不知何故从以前的N中“导入”，我不知道如何做到这一点，所以可能有人会帮上忙。

def fib(n):
    if n == 1: return 1
    if n == 2: return 1
    return fib(n-1) + fib(n-2)


def fibosubarr(n):
    L_pointer = 1
    R_pointer = 2
    sumfibs = 1
    while sumfibs != n:

        if sumfibs > n and L_pointer < R_pointer:
            sumfibs -= fib(L_pointer)
            L_pointer += 1

        elif sumfibs < n and L_poiner < R_pointer:
            sumfibs += fib(R_pointer)
            R_pointer += 1

        else: return False
    return True
    
n = int(input())

while fibosubarr(n):
    n += 1
print(n)

Answer 1

这是一种叫做“回忆录”的技巧。这里的fib函数跟踪当前列表，并仅在必要时对其进行扩展。一旦生成了一个数字，就不需要再做一次了。

_fib = [1,1]
def fib(n):
    while len(_fib) <= n:
        _fib.append( _fib[-2]+_fib[-1] )
    return _fib[n]

由于你的计划，200000造成了明显的延误。有了这个计划，就连20亿美元也能即时运行。

Answer 2

要获得下一个子数组和，只需调用一个函数--只要跟踪超过n的最小和值。

我还会用生成器来表示Fibonacci数：

def genfib():
    a = 1
    b = 1
    while True:
        yield b
        a, b = b, a + b

def fibosubarr(n):
    left = genfib()
    right = genfib()

    sumfibs = next(right)
    closest = float("inf")
    while sumfibs:
        if sumfibs > n:
            closest = min(sumfibs, closest)
            sumfibs -= next(left)
        elif sumfibs < n:
            sumfibs += next(right)
        else:
            return n
    return closest

现在您可以这样做了--生成至少是输入值的下一个有效和：

n = int(input())
print(fibosubarr(n))

您还可以循环从一个这样的和到下一个：

n = 0
for _ in range(10):  # first 10 such sums
    n = fibosubarr(n+1)
    print(n)