提问人：Pedro Ye 提问时间：11/9/2023 最后编辑：Pedro Ye 更新时间：11/18/2023 访问量：36
执行多次求和
Perform multiple summation
问：
我正在尝试在代码 C++ 中执行多个求和，但我不知道如何编写代码来执行多个 for。 $$\sum_{S_1=\pm1}...\sum_{S_N=\pm1}（\Pi_{i=1}^{N-1}e^{S_iS_{i+1}）}$$ 正如你所看到的，如果我尝试手动实现这一点，我应该写 N for's，再写 1 个大 pi，那么我怎样才能减少 N for's，因为我只需要 3，一个表示我要重复的 for 的数量，另一个表示求和，最后一个表示乘法。 请帮忙
我脑海中唯一想到的是： 对于 S1 = [-1,1] 对于 S2 = [-1,1] . . . . 对于 SN = [-1,1]
答：
0赞
Simon Goater
11/10/2023
#1
虽然这不是你真正要求的，但你可以简化
\Pi_{i=1}^{N-1}e^{S_iS_{i+1})
自
e^(\sum_{i=1}^{N-1} S_iS_{i+1})
因此，您只需对每组S_i值执行一次幂。
我认为您的问题与具有可变数量的嵌套 for 循环有关。处理这个问题的一种幼稚方法是为 N 的每个可能值编写一个函数，但这很冗长，容易受到批评。
我将如何解决这个问题，即使用无符号整数 U 的位以下列方式表示有符号S_i。我还没有测试过这个，所以它没有保修，但希望你能明白它的要点。
S_i = (U & (1 << i)) >> i // Get the ith bit
S_i = 2*S_i - 1 // Convert to -1, 1
这样你只需要 2 个 for 循环。
bigsum = 0
for (U = 0; U < (1 << N); U++)
exponent = 0
for (i=1; i<N; i++)
exponent += S_iS_{i+1}
bigsum += e^exponent
您将需要使用超过 maxN 位的整数类型。
评论
0赞
Simon Goater
11/10/2023
我怀疑有一种更快的方法可以用不同的算法获得结果，但我认为这就是你要找的方法。
0赞
Dillon Davis
11/11/2023
#2
正如 Simon 所指出的：
\Pi_{i=1}^{N-1}e^{S_iS_{i+1})
可以表示为：
e^(\sum_{i=1}^{N-1} S_iS_{i+1})
我们正在对所有 i 的每个可能分配进行评估，并对结果求和。请注意，总和表示序列中匹配的连续值数减去不匹配的连续值数。例如，生成 .有一个匹配的连续对和两个不匹配的连续对和，产生相同的结果。S_i\sum_{i=1}^{N-1} S_iS_{i+1}S_i[1, 1, -1, 1](1*1 + 1*-1 + -1*1) = -1(1, 1)(1, -1)(-1, 1)1 - 2 = -1
给定序列中匹配的连续对数可以从不匹配的数目中计算得出：。这意味着我们可以计算指数的值： 。ABA = N - 1 - BBA - B = N - 1 - 2*B
该值只能采用区间中的值。因此，与其遍历所有可能的任务，计算每个任务，不如尝试做一些更聪明的事情。我们可以尝试计算有多少赋值产生给定的赋值，迭代每个可能的值，并跳过实际赋值。请注意，每个不匹配对的相对位置无关紧要，连续匹配对的数量也无关紧要。例如：具有相同数量的匹配/不匹配，因此与 和 的总和相同。我们能做的是将连续匹配分组到块中： .每个具有不匹配的连续对的序列都可以像这样划分为统一的部分。B[0, N)BBB[1, 1, -1, 1, -1][-1, 1, -1, 1, 1][1, -1, 1, 1, -1]S_i[(1, 1), (-1), (1), (-1)]S_iB = k-1k
现在我们需要计算 ，有多少种方法可以创建统一有序的 k 分区，因为 in .这是标准的星条组合问题;我们只需要从 .需要完全清楚的是：Nk[1, N)k-1N-2
x choose y = nck(x, y) = x! / ((x-y)! * y!)
我们不能忘记一个小细节：在这些分区中的每一个中，我们声称有连续的 s 或 s 的统一部分。假设两个相邻的部分不能同时包含 s 或同时包含 s，例如，第一个部分的值选择决定了其余部分的赋值。这意味着第一部分提供了我们唯一的度自由度，对于任何分区，我们都必须考虑两个选项：一个以部分开头，另一个以 .因此，实际上，具有不匹配的连续对（部分）的赋值计数将为 。-111-1[(1, 1, 1), (1, 1)]1-1BB+12 * nck(N-2, B)
现在，对于 的每个值，我们可以计算相应赋值的数量，乘以指数，并计算整体表达式的值。B
2*\sum_{B=0}^{N-2}nck(N-2, B)e^(N-1-2*B)
通过构建上一次循环迭代的计算，可以及时完成计算，仅使用一次乘法和除法来计算新值。同样的策略也可用于指数的计算。这意味着整个计算可以及时完成。nck(N-2, B)O(1)O(n)
更新
在反思这个问题之后，我发现有一个更干净、更快速的封闭式解决方案。从上面的最后一步中求和，我们可以简化使用二项式公式，并得出：
2*e^{3-N}*(1+e^2)^{N-2}
然后，可以使用平方的幂在对数时间中对其进行评估，从而得出整体时间解决方案。O(log(n))
评论