人 - Apple Puzzle [受客户端拼图协议启发]

Question

我正在学习客户端拼图协议，我有一个关于寻找解决方案可能性的问题。下面是一个场景，而不是进入枯燥的协议事实：

假设我有 x 个人，我有 y 个苹果：

每人至少要有1个苹果
每人最多拥有z个苹果。

是否有计算场景数量的公式？

示例： 4 个人 [x]、6 个苹果 [y]、15 个 MAX 苹果 [z]

没有。手工计算的场景数：10.

如果我的数字很大，我希望用公式计算。

感谢您的帮助。

Answer 1

您的问题等同于 "finds the number of ways you can get x by adding together z numbers, each of which lies between min and max." 示例 Python 实施：

def possible_sums(x, z, min, max):
    if min*z > x or max*z < x:
        return 0
    if z == 1:
        if x >= min and x <= max:
            return 1
        else:
            return 0
    total = 0
    #iterate from min, up to and including max
    for i in range(min, max+1):
        total += possible_sums(x-i, z-1, min, max)
    return total

print possible_sums(6, 4, 1, 15)

结果：

此函数在调用大量数字时会变得相当昂贵，但可以通过 memoization 改进运行时间。如何实现这一点取决于语言，但传统的 Python 方法是将先前计算的值存储在字典中。

def memoize(fn):
    results = {}
    def f(*args):
        if args not in results:
            results[args] = fn(*args)
        return results[args]
    return f


@memoize
def possible_sums(x, z, min, max):
    #rest of code goes here

现在print possible_sums(60, 40, 1, 150)，本来要计算很久的，returns 2794563003870330瞬间

Answer 2

有多种数学方法可以做到这一点。这类似于询问有多少种方法可以在 3 个 6 面骰子（x=3，y=10，z=6）上掷出总共 10。您可以通过几种不同的方式实现它。

一种方法是使用包含-排除。将 y 写成 x 个没有最大值的正数之和的方法数是 y-1 通过 stars-and-bars argument. You can calculate the number of ways to write y as a sum of x positive numbers so that a particular set of s of them are at least z+1: 0 if y-x-sz is negative, and y-1-s z choose x-1 if it is nonnegative. Then you can use inclusion-exclusion 选择 x-1 将计数写成 s 的非负值之和，这样 y-x-sz 是(-1)^s 的非负数（x 选择 s）（y-1-sz 选择 x-1）。

您可以使用生成函数。您可以让某个变量（比如 t）的幂保留总数，而系数表示该总数有多少种组合。然后你要求 (t+t^2+...+t^z)^x 中 t^y 的系数。您可以通过几种方式进行计算。

一种方法是使用动态规划，计算 (t+t^2+...+t^z)^k 的系数，直到 x。天真的方法可能足够快：您可以计算 k=1, 2, 3, ..., x。使用重复平方之类的方法会更快一些，例如，计算 87 次方，您可以将 87 以二进制形式展开为 64+16+4+2+1=0b1010111（写为二进制文字）。您可以通过对这些进行平方和相乘来计算 1 次、2 次、4 次、16 次和 64 次方，或者您可以通过 squaring and multiplying 计算 0b1、0b10、0b101、0b1010、0b10101、0b101011 和 0b1010111 次方以节省很少 space。

另一种方法是两次使用二项式定理。

(t+t^2+...+t^z)^x = t^x ((t^z-1)/(t-1))^x 
                  = t^x (t^z-1)^x (t-1)^-x.

指数 x 的二项式定理让我们将 (t^z-1)^x 重写为 (-1)^s t^(z(x-s))(x 选择 s) 的总和，其中 s 的范围为 0到 x。它还让我们可以将 (t-1)^-x 重写为 (r+x-1 choose x-1)t^r 对非负 r 的无穷和。然后我们可以挑选出对 t^y (r = y-x-sz) 系数有贡献的有限项集，我们得到与上面包含 - 排除相同的总和。

例如，假设我们有 x=1000，y=1100，z=30。值为

=1.29 x 10^144.

人 - Apple Puzzle [受客户端拼图协议启发]

People - Apple Puzzle [Inspired by client-puzzle protocol]

math

probability

puzzle