T.11 · Komposisi lemah, invarian loop, dan pelacakan bagan alir
GRE Subject Test · GRE Mathematics Topik 26 7:36 Narasi bahasa Inggris · Subtitle bahasa Inggris + 中文 disematkan langsung
Bab-bab
Transkrip
Prerequisites: Binomial coefficients, complements and assignment tracing.
课程 T.11：弱组合、循环不变量与流程图追踪。 第2页，范围与先修知识。 先修知识：二项式系数、补集与赋值追踪。
Count indistinguishable allocations with nonnegative or positive constraints.
计算具有非负或正约束的不可区分分配。
Trace a flowchart in statement order with correct reset behaviour.
按语句顺序追踪流程图，并正确处理重置行为。
Use a loop invariant and a progress measure to justify an algorithm.
使用循环不变量和进度度量来论证算法的正确性。
weak composition: An ordered allocation of a total into nonnegative integer parts.
弱组合分拆：将一个总数按非负整数部分进行有序分配。
loop invariant: A property preserved before and after each iteration of a loop.
循环不变量：在循环的每次迭代前后都保持成立的性质。
The number of nonnegative integer solutions of x sub 1 plus ellipsis plus x sub k equals n is C of n plus k minus 1, choose k minus 1, for n greater than or equal to 0 and k greater than or equal to 1.
方程 x₁ + … + xₖ = n 的非负整数解的个数为 C(n+k−1, k−1)，其中 n ≥ 0 且 k ≥ 1。
Represent n identical stars separated into k named boxes by k minus 1 bars. Adjacent bars and end bars allow zero entries.
将 n 个相同的星号用 k−1 条竖线分隔放入 k 个有名称的盒子中；相邻竖线和首尾竖线允许零项。
Boxes are distinguishable, objects are not.
盒子是可区分的，对象是不可区分的。
Counting distinct tokens would instead assign each token independently, giving k to the power of n before other constraints.
若计算的是可区分标记物，则每个标记物独立分配，在考虑其他约束之前结果为 kⁿ。
Decide the model from what the objects and recipients represent, not from a familiar-looking binomial coefficient.
应根据对象和接收者的实际含义选择模型，而非仅凭熟悉的二项式系数形式。
For positive allocations x sub i greater than or equal to 1, put z sub i equals x sub i minus 1.
对于满足 x_i ≥ 1 的正整数分配，令 z_i = x_i − 1。
The remaining total is n minus k, giving C of n minus 1, k minus 1 when n is greater than or equal to k.
剩余总和为 n − k，当 n ≥ k 时，方案数为 C(n−1, k−1)。
More general lower bounds x sub i greater than or equal to a sub i are handled by subtracting each a sub i.
更一般的下界 x_i ≥ a_i 可通过减去每个 a_i 来处理。
At least one zero is the complement of every entry positive: subtract C of n minus 1, k minus 1 from the nonnegative total.
“至少有一个零”是“所有项均为正”的补集：从非负分配的总数中减去 C(n−1, k−1)。
Overlapping cases such as exactly two empty boxes need a different count. Subtracting each empty-box case independently double-counts their intersections.
重叠情况（例如恰好两个空盒）需要不同的计数方法；若独立地减去每个空盒情况，会重复计算它们的交集。
Trace a flowchart one executed statement at a time, recording variables in a table.
逐条追踪流程图，并在表格中记录变量。
Distinguish assignment from a mathematical equality test; the right side of an assignment uses the old value before replacement.
区分赋值与数学等式测试；赋值号右侧使用的是替换前的旧值。
Record which branch executes next and which variables reset.
记录接下来执行的是哪个分支以及哪些变量被重置。
A new outer-loop candidate may reset an inner sum without resetting the candidate itself.
新的外层循环候选者可能会重置内层求和，但不会重置候选者本身。
For a process that adds 1, 3, 5 and so on to S from zero, after m additions S equals m squared and the next addend is 2 m plus 1.
对于一个从0开始向S累加1、3、5……的过程，经过m次累加后，S等于m的平方，下一个加数是2m加1。
A loop invariant is true before and after each iteration.
循环不变量在每次迭代前后均为真。
The square-sum invariant holds initially at m equals zero and is preserved because m squared plus two m plus one equals m plus one squared.
平方和不变量在 m 等于零时初始成立，且因 m 的平方加两 m 加一等于 m 加一的平方而得以保持。
An invariant alone does not prove termination.
仅凭不变量本身无法证明终止性。
To test whether an integer N greater than or equal to zero is a square by adding odd numbers until S is greater than or equal to N, S grows without bound.
若要测试一个大于或等于零的整数 N 是否为完全平方数，可通过累加奇数直至 S 大于或等于 N 来实现；此时 S 会无界增长。
Equivalently, m increases and must reach a bound such as N.
等价地，m 递增并最终必须达到如 N 这样的上界。
At exit, equality means square and overshoot means non-square.
退出时，相等表示为完全平方数，超出则表示非完全平方数。
A printed value must be reached on an actual execution path.
打印出的值必须在实际执行路径上可达。
A plausible numerical pattern alone is not a trace.
仅凭合理的数值模式并不构成有效追踪。
Distribute 11 identical tokens among 4 named boxes.
把 11 个相同的标记分到 4 个有名字的盒子中。
Nonnegative allocations number 14 choose 3, which is 364; all-positive allocations number 10 choose 3, which is 120.
非负分配数为从 14 个中选 3 个，即 364；全为正的分配数为从 10 个中选 3 个，即 120。
Therefore 244 allocations have at least one empty box.
因此有 244 种分配至少有一个空盒。
For the odd-sum test with N equal to 10, S progresses 0, 1, 4, 9, 16; it overshoots and rejects 10.
对于 N 等于 10 的奇数和测试，S 依次为 0、1、4、9、16；它超过目标并拒绝 10。
For N equal to 9 it exits at S equal to 9 after three additions.
对于 N 等于 9，三次加法后在 S 等于 9 时退出。
The next addends are 1, 3, 5, 7, 9; the sum and next-addend columns must not be confused.
接下来的加数为 1、3、5、7、9；不要混淆和与下一个加数这两列。
The loop adds the odd numbers in turn.
这个循环依次加上奇数。
After m iterations the sum S is m squared and the next addend B is 2m plus 1: 0, 1, 4, 9, 16.
经过 m 次迭代后，和 S 等于 m 的平方，下一个加数 B 等于 2m 加 1：0、1、4、9、16。
That pair of facts is the loop invariant.
这两条性质就是循环不变式。
Identical objects and distinct objects use different models.
相同对象与不同对象使用不同的模型。
At least one empty box is not the same as exactly one.
至少一个空盒子并不等同于恰好一个。
In a flowchart, preserve update order and reset only variables that the executed path actually resets.
在流程图中，需保持更新顺序，且仅重置实际执行路径所重置的变量。
Pause and attempt this original task before advancing.
请先暂停，完成这道原创练习再继续。
Count nonnegative solutions of a plus b plus c equals 8, with a greater than or equal to 2.
求满足 a 加 b 加 c 等于 8 且 a 大于等于 2 的非负整数解的个数。
How many also have b greater than or equal to 1 and c greater than or equal to 1?
其中有多少个同时满足 b 大于等于 1 且 c 大于等于 1？
How many of the first set have at least one of b or c equal to zero?
在第一组解中，有多少个至少有一个 b 或 c 等于零？
Put u equals a minus 2.
令 u 等于 a 减 2。
Then u plus b plus c equals 6 has 8 choose 2, which is 28, nonnegative solutions.
则 u 加 b 加 c 等于 6 有 8 选 2，即 28 个非负解。
Requiring b and c positive and subtracting one from each gives total four in three nonnegative variables, counted by 6 choose 2, which is 15.
要求 b 和 c 为正数并各减去 1，得到三个非负变量之和为 4，其计数为 6 选 2，即 15。
The complement count is 28 minus 15, which is 13.
补集计数为 28 减 15，即 13。
Directly, b equals 0 gives seven, c equals 0 gives seven, and both zero is counted twice, giving 7 plus 7 minus 1, which is 13.
直接地，b 等于 0 给出 7 个，c 等于 0 给出 7 个，且两者同时为零被重复计算了一次，故结果为 7 加 7 减 1，即 13。
Pause and attempt this original task before advancing.
请先暂停，完成这道原创练习再继续。
Trace this algorithm for N equals 15 and N equals 16. Initialize S equals 0, k equals 1. While S is less than N, execute S equals S plus k, then k equals k plus 2.
对 N 等于 15 和 N 等于 16 分别追踪该算法：初始化 S 等于 0，k 等于 1；当 S 小于 N 时，执行 S 等于 S 加 k，然后 k 等于 k 加 2；报告 S 是否等于 N。
Report whether S equals N. State an invariant, and justify termination for integer N greater than or equal to 0.
陈述一个不变量，并证明对于整数 N 大于等于 0 时算法终止。
After m iterations, S equals m squared and k equals 2m plus 1.
经过 m 次迭代后，S 等于 m 的平方，k 等于 2m 加 1。
The trace pairs S, k are 0 comma 1, 1 comma 3, 4 comma 5, 9 comma 7, and 16 comma 9.
追踪对 (S, k) 依次为 (0, 1)、(1, 3)、(4, 5)、(9, 7) 和 (16, 9)。
Thus, 15 is rejected by overshoot and 16 accepted.
因此，15 因超出范围而被拒绝，16 被接受。
The invariant holds initially and is preserved since m squared plus 2m plus 1 equals m plus 1 squared.
该不变量在初始时成立，且由于 m 的平方加 2m 加 1 等于 (m+1) 的平方，故保持不变。
The sum grows without bound, so it eventually reaches or exceeds N; for example, m equals N suffices when N is positive.
总和无界增长，因此最终会达到或超过 N；例如当 N 为正数时，取 m 等于 N 即可满足条件。
For N equals 0, the loop is skipped and equality holds.
当 N 等于 0 时，循环被跳过，等式成立。
An invariant alone would not establish termination.
仅凭不变量本身无法证明终止性。
Close the solution and reconstruct the method.
关闭答案并重建方法。
Trace this algorithm for N equals 15 and N equals 16.
对 N 等于 15 和 N 等于 16 追踪此算法。
Initialize S equals 0, k equals 1.
初始化 S 等于 0，k 等于 1。
While S is less than N, execute S equals S plus k, then k equals k plus 2.
当 S 小于 N 时，执行 S 等于 S 加 k，然后 k 等于 k 加 2。
Report whether S equals N.
报告 S 是否等于 N。
State an invariant, and justify termination for integer N greater than or equal to 0.
陈述一个不变量，并为整数 N 大于或等于 0 证明终止性。