时间戳

首页 > 解决方案 > Project Euler 78 - 硬币分区

python - Project Euler 78 - 硬币分区

问题描述

问题陈述：

让p(n)表示n硬币可以分成几堆的不同方式的数量。例如，五枚硬币可以用七种不同的方式分成一堆，所以p(5)=7

找出能被一百万整除的最小值n。p(n)

所以这是我使用递归来解决这个问题的代码。我知道这不是最佳方法，但应该给我正确的答案......但由于某种原因，我不明白它让我知道 n = 2301 有 ap(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()

标签： pythonpython-3.xrecursion

解决方案

np.zeroes我相信您声明中使用的 NumPy 数据类型是一个受限而不是无限的数量。2301 的分区数实际上是 17022871133751761754598643267756804218108498650480 而不是 17022871133751703055227888846952967314604032000000，你可以看到如果你运行你的（正确的表声明）

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

然后适当地叫到桌子上。

推荐阅读