6

我正在尝试解决Project Euler 问题 240：

有多少种方法可以掷出 20 个 12 面骰子（面数为 1 到 12），从而使前十名的总和为 70？

我想出了解决这个问题的代码。但是计算起来确实需要很多时间。我知道这种方法很糟糕。有人可以建议我如何修复此代码以更好地执行吗？

import itertools
def check(a,b):   # check all the elements in a list a, are lesser than or equal to value b
    chk=0
    for x in a:
        if x<=b:
            chk=1
    return chk

lst=[]
count=0
for x in itertools.product(range(1,13),repeat=20):
    a=sorted([x[y] for y in range(20)])
    if sum(a[-10:])==70 and check(a[:10],min(a[-10:])):
        count+=1

下面的代码是针对问题描述中定义的问题。它完美地工作并给出了确切的解决方案....

import itertools
def check(a,b):
     chk=1
     for x in a:
         if x>b:
             chk=0
             break
     return chk


count=0
for x in itertools.product(range(1,7),repeat=5):
    a=sorted([x[y] for y in range(5)])
    if sum(a[-3:])==15 and check(a[:2],min(a[-3:])):
        count+=1
4

2 回答 2

12

迭代所有可能性并不好，因为有 12 20 = 3833759992447475122176 种方法可以掷出 20 个十二面骰子，例如每秒掷一百万次，这需要数百万年才能完成。

解决这类问题的方法是使用动态规划。想办法把你的问题分解成几个小问题的总和，并为这些子问题建立一个答案表，直到你可以计算出你需要的结果。

例如，让 T( n , d , k , t ) 是掷n d面骰子的方式数，以使它们中的前k个总和为t。我们如何将其分解为子问题？好吧，我们可以考虑精确地掷出d的骰子数量i 。有n C i种方式来选择这些i骰子，并且有 T( n  − i , d − 1, ...) 种方式来选择最多必须掷d的剩余n  − i个骰子− 1.（对于我已经省略的k和t的一些合适的参数选择。）

取这些的乘积，并总结所有合适的i值，你就完成了。（好吧，还没有完成：您必须指定基本情况，但这应该很容易。）

您需要计算的子问题的数量最多为 ( n + 1)( d + 1)( k + 1)( t + 1)，在 Project Euler 的情况下 ( n = 20, d = 12 , k = 10, t = 70) 最多为 213213。（实际上，它比这要少得多，因为树的许多分支很快就达到了基本情况：在我的实现中，结果证明只有 791 个子问题的答案足以计算答案。）

要编写动态程序，通常最容易递归地表达它并使用记忆化来避免重新计算子问题的答案。在 Python 中，您可以使用@functools.lru_cache装饰器。

所以你的程序的骨架可能看起来像这样。我已将关键细节替换为，???以免剥夺您自己解决问题的乐趣。在尝试更大的情况之前，使用小示例（例如“两个 6 面骰子，其中的前 1 个总和为 6”）来检查您的逻辑是否正确。

def combinations(n, k):
    """Return C(n, k), the number of combinations of k out of n."""
    c = 1
    k = min(k, n - k)
    for i in range(1, k + 1):
        c *= (n - k + i)
        c //= i
    return c

@lru_cache(maxsize=None)
def T(n, d, k, t):
    """Return the number of ways n distinguishable d-sided dice can be
    rolled so that the top k dice sum to t.

    """
    # Base cases
    if ???: return 1
    if ???: return 0

    # Divide and conquer. Let N be the maximum number of dice that
    # can roll exactly d.
    N = ???
    return sum(combinations(n, i)
               * T(n - i, d - 1, ???)
               for i in range(N + 1))

有了适当的选择???，这回答了几毫秒的项目Euler问题：

>>> from timeit import timeit
>>> timeit(lambda:T(20, 12, 10, 70), number=1)
0.008017531014047563
>>> T.cache_info()
CacheInfo(hits=1844, misses=791, maxsize=None, currsize=791)
于 2012-12-12T11:59:35.260 回答
0

该解决方案应该可以工作-不确定您的系统需要多长时间。

from itertools import product

lg = (p for p in product(xrange(1,13,1),repeat=10) if sum(p) == 70)

results = {}
for l in lg:
    results[l] = [p for p in product(xrange(1,min(l),1),repeat=10)]

它所做的是首先创建“前十名”。然后向每个“前十”添加一个可能的“下十”项目的列表，其中最大值被限制为“前十”中的最小项目

results 是一个字典，其中 thekey是“前十个”，值是可能的“下一个十个”的列表

解决方案（符合要求的组合数量）将计算所有结果字典中的列表数量，如下所示：

count = 0
for k, v in results.items():    
    count += len(v)

然后count将是结果。

更新

好的，我想到了一种更好的方法。

from itertools import product
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_count = dict((n, math.pow(n, dice-top)) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

因为我只计算“下一个十”的长度，所以我想我会预先计算“前十”中每个“最低”数字的选项数量，所以我创建了一个字典来做到这一点。上面的代码运行起来会更流畅，因为它只包含一个小字典、一个计数器和一个生成器。正如你可以想象的那样，它可能仍然需要很长时间......但我在不到 1 分钟的时间内运行了它以获得前 100 万个结果。所以我确信它在可行的范围内。

祝你好运 ：）

更新 2

在你的另一条评论之后，我明白我做错了什么并试图纠正它。

from itertools import product, combinations_with_replacement, permutations
import math

def calc_ways(dice, sides, top, total):
    top_dice = (p for p in product(xrange(1,sides+1,1),repeat=top) if sum(p) == total)
    n_dice = dice-top
    n_sets = len(set([p for p in permutations(range(n_dice)+['x']*top)]))
    n_count = dict((n, n_sets*len([p for p in combinations_with_replacement(range(1,n+1,1),n_dice)])) for n in xrange(1,sides+1,1))

    count = 0
    for l in top_dice:
        count += n_count[min(l)]

    return count

正如你可以想象的那样，这是一场灾难，甚至没有给出正确的答案。我想我要把这个留给数学家。因为我解决这个问题的方法很简单：

def calc_ways1(dice, sides, top, total):
    return len([p for p in product(xrange(1,sides+1,1),repeat=dice) if sum(sorted(p)[-top:]) == total])

这是一个优雅的 1 行解决方案，并提供了正确的答案，calc_ways1(5,6,3,15)但需要永远解决这个calc_ways1(20,12,10,70)问题。

无论如何，数学似乎是解决这个问题的方法，而不是我的愚蠢想法。

于 2012-12-12T11:15:33.997 回答