查找斐波那契一致子数组的总和

Question

我们有一个输入整数，比方说 13。我们可以找到总和为 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 的最小总和值。

我还会为斐波那契数列使用生成器：

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)

查找斐波那契一致子数组的总和

Finding sum of a fibonacci consistent subarray

python

optimization

fibonacci