python - 欧拉计划 78 - 硬币分区

Question

问题陈述:

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7

Find the least value of n for which p(n) is divisible by one million.

这就是我使用递归来解决这个问题的代码。我知道这不是最佳方法，但应该给我正确的答案......但出于某种原因我不明白它让我回到 n = 2301 有一个 p(n) = 17022871133751703055227888846952967314604032000000，它可以被 1,000,000 整除并且是至少要做到这一点。那么为什么这不是正确的答案呢？我检查了 n<20，它匹配。那么我的代码有什么问题吗？

import numpy as np
import sys

sys.setrecursionlimit(3000)

table = np.zeros((10000,10000))

def partition(sum, largestNumber):
    if (largestNumber == 0):
        return 0

    if (sum == 0):
        return 1

    if (sum < 0):
        return 0

    if (table[sum,largestNumber] != 0):
        return table[sum,largestNumber]

    table[sum,largestNumber] = partition(sum,largestNumber-1) + partition(sum-largestNumber,largestNumber)
    return table[sum,largestNumber]



def main():
    result = 0
    sum = 0
    largestNumber = 0
    while (result == 0 or result%1000000 != 0):
        sum += 1
        largestNumber += 1
        result = int(partition(sum,largestNumber))
        print("n = {}, resultado = {}".format(sum,result))

    return 0

if __name__ == '__main__':
    main()

Answer 1

我相信您的 np.zeroes 声明中使用的 NumPy 数据类型是 a restricted rather than unlimited number . 2301 的分区数实际上是 17022871133751761754598643267756804218108498650480 而不是 17022871133751703055227888846952967314604032000000，如果你运行你的常规表声明，你可以看到它

table = [10000 * [0] for i in xrange(10000)]

然后适本地调用表。