计算一个数字的表示数量,作为斐波纳契数的总和

Question

我的小组很难找到一个好的算法但我们能想到的只是一个指数的算法.有没有办法让它更快？这是完整的问题:

定义一个函数

function F(n:Integer):Integer;

这将计算非负数n的不同表示的数量,作为具有不相等的正指数的斐波那契数的总和.例如(Fib(k)表示第k个斐波纳契数):

F(0)= 0

F(1)= 2,因为1 = Fib(1)= Fib(2)

F(2)= 2,因为2 = Fib(3)= Fib(1)+ Fib(2)

F(3)= 3,因为3 = Fib(4)= Fib(3)+ Fib(1)= Fib(3)+ Fib(2)

等等

我认为第一个不可避免的步骤是制作一个n个 Fibonacci数的数组,如下所示:

Fib[1]:=1;
Fib[2]:=1;
for i:=3 to n do
    Fib[i]:=Fib[i-1]+Fib[i-2];

当然,我们可以通过仅计算小于或等于n的 Fibonacci数来优化它,但这无济于事,因为无论如何都不允许动态数组.那么我们如何才能避免指数时间的复杂性呢？

Answer 1

让我们来证明一些关于数字的东西:

引理1:令Ñ≥1是一个整数和纤维蛋白原(I)是具有最大Fibonacci数Fib的(ⅰ)≤Ñ.然后在n的表示中,作为具有不同指数的斐波纳契数的总和,出现Fib(i)或Fib(i-1),但不是两者.

证明:我们可以通过归纳显示总和Fib(1)+ Fib(2)+ ... + Fib(i-2)= Fib(i)-1.由于Fib(i)<n,我们在表示中至少需要Fib(i-1)或Fib(i).但不是两者,因为Fib(i)+ Fib(i-1)= Fib(i + 1)> n(否则Fib(i)将不是小于或等于n的最大Fibonacci数).

引理2:n-Fib(i)<Fib(i-1)和n-Fib(i-1)<Fib(i).

证明:这些很容易显示.留给读者练习.

我最初认为这会导致递归F(n)= F(n - Fib(i))+ F(n - Fib(i - 1)),但有一个问题:它可能是n - Fib (i - 1)≥Fib(i - 1),因此在这种情况下可能会发生F(i - 1)被重用,我们不允许这样做.我们可以很容易地解决这个问题:我们可以给函数F一个额外的布尔标志,告诉它不允许递归到F(n - Fib(i)).

最后一个问题仍然存在:如何计算i？一个重要的观察结果是Fibonacci数呈指数增长,因此我们得到i = O(log n).我们可以使用蛮力来找到它(计算所有斐波纳契数到n:

function F(n : Integer, recurseHigh = True: Bool):
    if n == 0: return 1
    a, b = 1, 1
    while a + b <= n:
        a, b = b, a + b
    res = 0
    if recurseHigh: res += F(n - b)
    res += F(n - a, n - a < a)
    return res

即使对于32位整数的这种"愚蠢"实现,它恰好也能够足够快地工作.如果你使用memoization,它确实适用于更大的数字,但是你需要动态分配的内存.

我还没有证明这个运行时的复杂性,但如果使用memoization,它确实很快.如果我们将斐波那契数字预先计算到n并对i进行二进制搜索,我认为它是O(log²n)加法并且将是O(log n*log log n).不确定没有记忆的情况,它似乎不适用于超过2³²的n.

如果你感兴趣的话,这里有一些F的值,用Python中的上述函数的memoized版本计算:

F(0) = 1
F(1) = 2
F(2) = 2
F(3) = 3
F(4) = 3
F(5) = 3
F(6) = 4
F(7) = 3
F(8) = 4
F(9) = 5
F(10) = 4
F(11) = 5
F(12) = 4
F(13) = 4
F(14) = 6
F(4079078553298575003715036404948112232583483826150114126141906775660304738681982981114711241662261246) = 70875138187634460005150866420231716864000000
F(2093397132298013861818922996230028521104292633652443820564201469339117288431349400794759495467500744) = 157806495228764859558469497848542003200000000
F(1832962638825344364456510906608935117588449684478844475703210731222814604429713055795735059447061144) = 9556121706647393773891318116777984000000000
F(6529981124822323555642594388843027053160471595955101601272729237158412478312608142562647329142961542) = 7311968902691913059222356326906593280000000
F(3031139617090050615428607946661983338146903521304736547757088122017649742323928728412275969860093980) = 16200410965370556030391586130218188800000000
F(4787808019310723702107647550328703908551674469886971208491257565640200610624347175457519382346088080) = 7986384770542363809305167745746206720000000
F(568279248853026201557238405432647353484815906567776936304155013089292340520978607228915696160572347) = 213144111166298008572590523452227584000000000
F(7953857553962936439961076971832463917976466235413432258794084414322612186613216541515131230793180511) = 276031486797406622817346654015856836608000000
F(2724019577196318260962320594925520373472226823978772590344943295935004764155341943491062476123088637) = 155006702456719127405700915456167116800000000
F(4922026488474420417379924107498371752969733346340977075329964125801364261449011746275640792914985997) = 3611539307706585535227777776416785118003200
F(10^1000) = 1726698225267318906119107341755992908460082681412498622901372213247990324071889761112794235130300620075124162289430696248595221333809537338231776141120533748424614771724793270540367766223552120024230917898667149630483676495477354911576060816395737762381023625725682073094801703249961941588546705389069111632315001874553269267034143125999981126056382866927910912000000000000000000000000000000000000000000000000000000000000000000000000000000

我们观察到它似乎是F(n)=Θ(sqrt(n)),另一个我尚未证明的结果.

更新:这是Python代码:

memo = {}
def F(n, x=True):
    if n == 0: return 1
    if (n, x) in memo: return memo[n,x]
    i = 1
    a, b = 1, 1
    while b + a <= n:
        a, b = b, a + b
    memo[n,x] = (F(n - b) if x else 0) + F(n - a, n - a < a)
    return memo[n,x]

更新2:通过使用二进制搜索来查找i并使用快速矩阵求幂计算Fib(i),即使没有记忆也可以获得更好的运行时间.可能不值得努力,尤其不适用于32位n.

更新3:只是为了好玩,这是一个可证明只O(log n)添加的实现:

fib = [0,1]
def greedy(n):
    while fib[-1] < n:
        fib.append(fib[-1] + fib[-2])
    i = 1
    while fib[i+1] <= n: i += 1
    digs = set()
    while n:
        while fib[i] > n: i -= 1
        digs.add(i)
        n -= fib[i]
    return digs

def F(n):
    digs = greedy(n)
    top = max(digs)
    dp = [[[0,0,0] for _ in xrange(4)] for _ in xrange(top+1)]
    for j in xrange(0, 2): dp[0][j][0] = 1
    for i in xrange(1, top + 1):
        for j in xrange(0,2):
            for k in xrange(0,j+1):
                if i in digs:
                    dp[i][j][k] = dp[i-1][k+j][j] + dp[i-1][k+j+1][j+1]
                else:
                    dp[i][j][k] = dp[i-1][k+j][j] + dp[i-1][k+j-1][j-1]
    return dp[top][0][0]

它首先在斐波那契基数中找到数字的贪婪表示,然后使用DP来查找在该表示中携带数字以构建最终数字的方式的数量.dp[i,j,k]是表示1..i在斐波那契基数中表示数字前缀的方法的数量,如果我们已经进j位i并k进入位置i - 1.使用它,我们可以F(10^50000)在5秒内计算(结果有超过20000个十进制数字!)

Answer 2

我对Niklas B.的答案的两个方面感兴趣:计算的速度(即使对于大数字),以及结果具有小的素因子的倾向.这些提示可以将解决方案计算为小项的乘积,事实证明是这种情况.

为了解释发生了什么,我需要一些符号和术语.对于任何非负整数n,我将定义的(唯一的)贪婪表示的n是通过反复以最大Fibonacci数不超过获得的斐波那契数的总和n.因此,例如,贪婪的表示10是8 + 2.我们很容易发现,我们从不使用Fib(1)这种贪婪的表现形式.

我还想要一种简洁的方法来编写这些表示,为此我将使用位串.很像二进制,除了地方值遵循Fibonacci序列而不是2的幂序列,我将首先用最低有效数字写.因此,例如00100001,1在位置2和位置7,所以代表Fib(2) + Fib(7) = 1 + 13 = 14.(是的,我开始计算0,并遵循通常的约定Fib(0) = 0.)

找到所有表示的蛮力方法是从贪婪的表示开始,然后探索将表单的子001模式重写为表单模式的所有可能性110; 即,替换Fib(k+2)用Fib(k) + Fib(k+1)一些k.

因此,我们总是可以将贪婪表示写n为位串,并且位串将是0s和1s 的序列,没有两个相邻的1s.现在关键的观察是我们可以将这个位串分割成碎片并计算每个单独块的重写次数,乘以得到表示的总数.这是有效的,因为bitstring中的某些子模式阻止了字符串部分到模式左边的重写规则与右边的重写规则之间的交互.

举个例子,让我们来看看n = 78.它贪婪的表现形式00010000101,蛮力的方法可以快速识别出全套的表现形式.其中有十个:

00010000101
01100000101
00010011001
01100011001
00011101001
01101101001
0001001111
0110001111
0001110111
0110110111

我们可以分出第一部分的图案,0001从第二,0000101.上面的每个组合来自重写0001,单独重写0000101和将两个重写粘合在一起.图案的左侧部分有2个重写(包括原始),右侧有5个重写,因此我们总共得到10个表示.

是什么让这个工作是左半的任何改写,0001与任一端01或10,而右半边的任何重写开头00或11.所以两者都没有匹配001或者110与边界重叠.每当我们将两个1s分开偶数个零时,我们就会得到这种分离.

这解释了Niklas答案中看到的小素因子:在一个随机选择的数字中,会有许多0偶数长度的s 序列,并且每个序列代表我们可以分割计算的点.

解释变得有点复杂,所以这里有一些Python代码.我已经验证,结果由Niklas的同意所有n达10**6,和选择的随机选择的大n.它应该具有相同的算法复杂性.

def combinations(n):
    # Find Fibonacci numbers not exceeding n, along with their indices.
    # We don't need Fib(0) or Fib(1), so start at Fib(2).
    fibs = []
    a, b, index = 1, 2, 2
    while a <= n:
        fibs.append((index, a))
        a, b, index = b, a + b, index + 1

    # Compute greedy representation of n as a sum of Fibonacci numbers;
    # accumulate the indices of those numbers in indices.
    indices = []
    for index, fib in reversed(fibs):
        if n >= fib:
            n -= fib
            indices.append(index)
    indices = indices[::-1]

    # Compute the 'signature' of the number: the lengths of the pieces
    # of the form 00...01.
    signature = [i2 - i1 for i1, i2 in zip([-1] + indices[:-1], indices)]

    # Iterate to simultaneously compute total number of rewrites,
    # and the total number with the top bit set.
    total, top_set = 1, 1
    for l in signature:
        total, top_set = ((l + 2) // 2 * total - (l + 1) % 2 * top_set, total)

    # And return the grand total.
    return total

编辑:代码大大简化.

编辑2:我刚刚再次遇到这个答案,并怀疑有一种更直截了当的方式.这是另一个代码简化,清楚地表明O(log n)需要操作.

def combinations(n):
    """Number of ways to write n as a sum of positive
    Fibonacci numbers with distinct indices.
    """
    # Find Fibonacci numbers not exceeding n.
    fibs = []
    fib, next_fib = 0, 1
    while fib <= n:
        fibs.append(fib)
        fib, next_fib = next_fib, fib + next_fib

    # Compute greedy representation, most significant bit first.
    greedy = []
    for fib in reversed(fibs):
        greedy.append(fib <= n)
        if greedy[-1]:
            n -= fib

    # Iterate to compute number of rewrites.
    x, y, z = 1, 0, 0
    for bit in reversed(greedy):
        x, y, z = (0, y + z, x) if bit else (x + z, z, y)
    return y + z