2

在研究 项目欧拉练习 (#78)时，我了解到为了对数字进行分区，您可以创建一个幂级数。从该系列中，您可以扩展并使用术语系数来获得划分特定数字的方法的数量。

从那里，我创建了这个小函数：

## I've included two arguments, 'lim' for the number you wish to partition and 'ways' a list of numbers you can use to partition that number 'lim'. ##

def stack(lim,ways):

    ## create a list of length of 'lim' filled with 0's. ##
    posi = [0] * (lim + 1)

    ## allow the posi[0] to be 1 ##
    posi[0] = 1

    ## double loop -- with the amount of 'ways'. ##
    for i in ways:
        for k in range(i, lim + 1):
            posi[k] += posi[k - i]

    ## return the 'lim' numbered from the list which will be the 'lim' coefficient. ##
    return posi[lim] 

>>> stack(100,[1,5,10,25,50,100])
>>> 293
>>> stack(100,range(1,100))
>>> 190569291
>>> stack(10000,range(1,10000))
>>> 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435143L

这在相对较小的分区上工作得很好，但是在这个练习中没有。有没有办法通过递归或更快的算法来加快速度？我读过一些地方，使用五边形数字也是一种帮助分区的方法。

现在我不需要返回这个问题的实际数字，但是，检查它是否能被 1000000 整除。

更新：我最终使用了五角数定理。我将尝试使用 Craig Citro 发布的 Hardy-Ramanujan 渐近公式。

4

1 回答 1

1

我最近没有亲自检查过这个事实，但是 Sage 中的实现可能仍然持有“最快分区算法”的称号。您可以在文档中看到它，或者更好的是直接跳到源代码。如果您正在寻找有关计算此数字的方法的讨论，那么导致此实现的原始线程肯定很有趣。实现本身的源文件以一些关于代码的有用注释开头。

于 2012-07-30T05:11:57.880 回答