弱组合、循环不变量与流程图追踪
引入| English | 释义 | 拼音 |
|---|---|---|
| stars and bars/stɑːz ænd bɑːz/ | 隔板法 | gé bǎn fǎ |
| complement/ˈkɒmplɪmənt/ | 补集 | bǔ jí |
| invariant/ɪnˈveərɪənt/ | 不变量 | bù biàn liàng |
相同令牌与命名盒子
- 将十一个相同的奖励令牌放入四个命名盒子中,无容量限制且允许空盒。结果仅记录四个计数值。这不属于 $4^{11}$ 情形:后者会区分各个令牌。
- 我们将使用隔板法、补集原理及精确空盒计数,并追踪平方和算法。循环不变量将追踪中的数值与每一轮遍历的证明联系起来。
首先陈述分配模型
- 设 $n\ge0$ 和 $k\ge1$ 为整数。在 $k$ 个命名盒子中的相同物体对应于非负整数计数 $x_1+\cdots+x_k=n$。盒子内部无顺序之分,对于基础公式而言也无上限容量。
- 若物体互不相同,进入某盒子的具体物体会改变结果。若盒子未命名或施加了容量限制,基础计数也会发生变化。在选择公式前,需先确定何种情况视为不同结果。
为何隔板法构成双射
- 在一行中放置 $n$ 颗星和 $k-1$ 条竖线。从左至右读取时,竖线将盒子 1 至 $k$ 的计数分隔开。允许末尾竖线或相邻竖线出现:它们表示空盒。
- 对于六个令牌放入四个盒子的情形,
***||**|*代表 $(3,0,2,1)$。反之,每个允许的计数元组恰好构建出这样一行排列。因此,从 $n+k-1$ 个位置中选择竖线的位置即可计算不重复的分配方案数。
统计非负整数解
- 弱组合数为 $\binom{n+k-1}{k-1}$。针对原始 $x_1+x_2+x_3=8$,需在十个位置中选两个竖线位置:$\binom{10}{2}=45$。对于十一个令牌放入四个盒子,计数为 $\binom{14}{3}=364$。
- 边界情况至关重要。若无令牌,则有一种分配方式,所有计数均为零。若仅有一个盒子,也有一种分配方式,所有令牌都在其中。公式在这两种情况下均成立;它并不要求每个盒子都必须被使用。
How many non-negative integer solutions does $x_1 + x_2 + x_3 = 8$ have?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Stars and bars: 8 stars and 2 bars, so C(8 + 2, 2) = C(10, 2) = 45 non-negative solutions.
How many allocations put zero identical tokens into four named boxes, with empty boxes allowed?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
There is exactly one tuple: (0,0,0,0). The stars-and-bars count is C(3,3)=1.
通过代换消除下界
- 若每个 $x_i\ge1$ 均需满足条件,设 $z_i=x_i-1\ge0$。当 $n\ge k$ 时,剩余总数为 $n-k$,计数为 $\binom{n-1}{k-1}$。若 $n<k$,则不存在此类分配。原问题中四个正整数之和为 9,对应 $\binom83=56$ 种解。
- 更一般地,对于整数下界$x_i\ge\ell_i\ge0$,首先减去所有下界。针对$x_1+x_2+x_3=8$及其上下界2,1与0的残差总和为5,从而得到$\binom72=21$。若残差为负数,则无解。
How many positive integer solutions does $x_1+x_2+x_3+x_4=9$ have?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Set yᵢ = xᵢ − 1 ≥ 0, so y₁ + … + y₄ = 5. Stars and bars: C(5 + 3, 3) = C(8, 3) = 56.
Count integer solutions of $x_1+x_2+x_3=8$ with $x_1\ge2$, $x_2\ge1$, $x_3\ge0$.
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Subtract lower bounds 2,1,0, leaving three nonnegative counts totaling 5. The count is C(7,2)=21.
利用补集处理至少一个空盒的情况
- 在所有分配方案中,“至少有一个盒子为空”的补集是“每个盒子都非空”。对于十一个标记物和四个有标号盒子,全正分配数为$\binom{10}{3}=120$。
- 因此,$364-120=244$种分配方案导致至少有一个盒子为空。使用补集法减去一次即可;若分别减去四种单盒为空的情况,会错误处理多个盒子同时为空的分配。
恰好r个空盒是一个不同的事件
- 对于$n>0$和恰好$r$个空盒,首先从$\binom kr$种方式中选择这些空盒。将正数计数放入其余$k-r$个盒子中。若$1\le k-r\le n$,则计数为$\binom kr\binom{n-1}{k-r-1}$;否则为零。
- 当有十一个标记物和四个盒子时,恰好两个空盒对应$\binom42\binom{10}{1}=60$。零、一、二、三个空盒的计数分别为120、180、60和4,总和为364。对于$n=0$,在唯一一种分配中所有$k$个盒子均为空。
Eleven identical tokens go into four named boxes. How many allocations have exactly two empty boxes?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Choose the two empty boxes in C(4,2)=6 ways. Split 11 positively between the remaining two in C(10,1)=10 ways. Multiply to obtain 60.
Twelve identical tokens go into four named boxes, each receiving at least two. Count all such allocations, then count those with at least one box receiving exactly two.
在比较答案之前,请检查分配条件或精确的循环检查点。
上界需要重叠修正
- 计算包含$x_1+x_2+x_3=8$且满足$0\le x_i\le3$的方案。从45种无限制分配开始。对于指定的违反条件$x_i\ge4$,从该坐标中减去4:共有$\binom62=15$种此类分配。
- 减去$3\cdot15$后,成对违反被重复计算了两次。在三对组合中,每对有两个计数至少为4,剩余为零,因此需加回一种分配。不存在三重违反情况,故答案为$45-45+3=3$:即$(3,3,2)$的三种排列。
How many integer solutions of $x_1+x_2+x_3=8$ satisfy $0\le x_i\le3$ for every i?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
Only the three permutations of (3,3,2) fit. Inclusion-exclusion gives C(10,2)-3C(6,2)+3C(2,2)=45-45+3=3.
Count integer solutions of $x_1+x_2+x_3=7$ with $0\le x_i\le3$. Use overlap counting and check by listing the possible count patterns.
在比较答案之前,请检查分配条件或精确的循环检查点。
不同对象使用独立选择
- 对于$n$个不同对象和$k$个有标号接收者,若无容量限制且接收者内部收集物无序,则每个对象选择一个接收者。总数为$k^n$。将五本不同的书分给三名学生,共有$3^5=243$种分配。
- 此方法统计的是每位学生获得哪些书,而非发放顺序。若要求每位学生必须得书,则排除空学生事件并加回其两两重叠部分:$3^5-3\cdot2^5+3=150$。正整数星条法不适用于这些不同书籍。
哪种计数模型符合所述条件?
使用对象标识和分配约束,而不仅仅是熟悉公式。
Five different books are given to 3 students (a student may get none). How many ways?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Each distinct book picks a student.
指定奇数和循环
- 设输入$N$为非负整数。使用精确整数运算和预测试循环:在第一轮之前及每次后续迭代前测试条件。此处$m$记录已完成加法次数,$B$存储下一个奇数加数。
S ← 0
m ← 0
B ← 1
WHILE S < N
S ← S + B
m ← m + 1
B ← B + 2
ENDWHILE
- 赋值语句按书写顺序执行。每条语句右侧使用的是该语句运行时可用的值;这是顺序更新,而非所有三个变量的同时替换。
逐条追踪语句
- 对于$N=10$,初始状态为$(S,m,B)=(0,0,1)$且条件为真。第一轮使状态发生如下变化;某值在未对其赋值的语句执行前保持不变。
| 已执行语句 | S | m | B |
|---|---|---|---|
S ← S + B |
1 | 0 | 1 |
m ← m + 1 |
1 | 1 | 1 |
B ← B + 2 |
1 | 1 | 3 |
- 关系$S=m^2$在第一次赋值后暂时失效,此时$S=1$与$m=0$不匹配。我们将在循环头部(初始化或完整一轮之后)断言其成立,而非在每个单独语句之后。
总结已完成轮次
- 原始表格显示循环头部状态,即将测试条件。对于$N=10$,累加和分别为0、1、4、9、16;仅前四个状态进入下一轮。退出时,$S=16$、$m=4$和$B=9$。
- 对于原始阈值 $N=30$,循环在五次累加后达到 25,然后加上 11 达到 36。它以 $S=36$、$m=6$ 和 $B=13$ 退出。请保持下一个加数与最后一个使用的加数分离。
Use the stated pre-test odd-sum loop with $S=0$, $m=0$, $B=1$ and threshold $N=30$. What is $S$ at exit?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
The loop-head sums are 0,1,4,9,16,25,36. Since 25<30≤36, it exits after six additions with S=36, m=6 and next addend B=13.
建立并维持不变量
- 在每个循环头处,不变量为 $S=m^2$ 和 $B=2m+1$,其中 $m\ge0$ 为整数。初始化给出 $S=0=0^2$ 和 $B=1$。这些事实不依赖于阈值。
- 假设旧计数为 $m$。一次完整遍历将总和设为 $m^2+(2m+1)=(m+1)^2$,计数设为 $m+1$,下一个加数设为 $2m+3$。因此,这两个关系在下一个循环头处再次成立。这是维持性,而非终止证明。
证明循环停止
- 令 $q=\lceil\sqrt N\rceil$ 仅用于证明。在具有真守卫的循环头处,$m^2<N$,因此 $m<q$。每次遍历使 $m$ 恰好增加一,从而使非负整数 $q-m$ 减少一。经过 $q$ 次遍历后,守卫变为假。
- 这证明了终止性和确切遍历次数 $q$,包括 $N=0$ 的零次遍历。仅仅说一个量增加是不够的:递增序列可以保持在阈值以下。此处不变量给出了具体的平方增长。
在退出时使用不变量
- 对于 $N>0$,最后的真守卫和第一个假守卫给出 $(m-1)^2<N\le m^2$。因此 $S$ 是 不小于 N 的最小完全平方数。若 $S=N$,则输入是完全平方数;若 $S>N$,则不是。对于 $N=0$,初始状态直接给出正确的平方数 0。
- 退出测试提供 $S\ge N$;不变量提供 $S=m^2$。单独任一事实都无法证明完整结论。将
<替换为≤则会返回严格大于 $N$ 的最小平方数,因此守卫是规范的一部分。
这是奇数和证明的哪一部分?
分别处理初始化、保持不变性、终止及退出时的推理。
A loop invariant shows what is true when a loop ends, but termination needs a separate argument.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
An established and preserved invariant, combined with a false guard, proves the exit claim if the loop stops. A separate argument, such as the decreasing nonnegative integer ceil(sqrt(N))-m here, proves that it does stop.
Use the stated pre-test odd-sum loop with threshold $N=0$. What is $S$ at exit?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
The initial guard 0<0 is false, so the body runs zero times and S stays zero.
For the stated pre-test odd-sum loop, give S, m and B at exit for N=50 and for N=49. Justify both the pass count and the square test.
在比较答案之前,请检查分配条件或精确的循环检查点。
更改更新顺序会改变序列
- 若
B ← B + 2移至S ← S + B之前,第一项加数变为3。保持初始值不变,求和序列变为3、8、15、…,当$m$越过新关系时,新关系变为$S=m(m+2)$。 - 该关系源于对$3+5+\cdots+(2m+1)$求和,但并非原始不变量。在套用熟悉公式前,请追踪实际赋值过程;针对某一循环的有效证明不能保证重排后的循环正确。
Moving B ← B+2 before S ← S+B preserves the original loop-head invariant $S=m^2$ with the same initialization.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The first complete pass then gives S=3, m=1, B=3. The original equation S=m² already fails; the new sum is m(m+2).
重置每次新运行中使用的所有状态
- 为独立处理阈值 2 和 5,请将 全部三个 初始化置于外层循环内、每个奇数累加循环之前。两次运行分别返回 4 和 9。仅重置 $S$ 会使旧的下一个加数和计数保留原位。
- 若 $m=0,B=1$ 仅初始化一次,第一次运行结束于 $(S,m,B)=(4,2,5)$。仅重置 $S$ 以处理阈值 5,下一次加法为 5:第二次运行返回 5,而非 9。原始不变量不再匹配重置后的状态。
Reset S=0, m=0 and B=1 before each run of the stated odd-sum loop. Which outputs correspond to thresholds 2 and 5?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The first squares at least 2 and 5 are 4 and 9. The output 5 on the second run would result from retaining B=5 after resetting only S.
Process thresholds 2, 5 and 10 in order. Compare outputs when all three state variables reset before each run with outputs when m=0 and B=1 are initialized once and only S resets between runs. Explain the difference.
在比较答案之前,请检查分配条件或精确的循环检查点。
总结:建模与检查点
- 统计预期结果:检查对象标识、方框标签、下界和容量。对于循环,需指定初始化、守卫和更新顺序,然后证明初始化、维持性、终止性以及陈述检查点处的退出结论。
- stars and bars(星号与竖线法):一种双射计数方法,用于计算将相同物体分配给有标签的盒子且无上限容量时的非负整数方案数。
- complement(补集):指定全集内不属于当前所考虑事件的结果集合。
- invariant(不变量):在循环开始前的指定检查点及每次完整迭代后均保持成立的性质。