C/C++ 中 Bertrand 投票定理的应用
cc++server side programmingprogramming
在 Bertrand 的原始论文中，他解释了一个依赖于实现递归关系的有利序列数量的通用公式的证明。
示例
假设有 5 名选民，其中 3 名投票给候选人 A，2 名投票给候选人 B(因此 p = 3 和 q = 2)。投票顺序有十种可能性 −
AAABB
AABAB
ABAAB
BAAAB
AABBA
ABABA
BAABA
ABBAA
BABAA
BBAAA
对于顺序 AABAB，选举过程中的投票结果如下所示 −
| 候选人 | A | A | B | A | B |
|---|---|---|---|---|---|
| A | 1 | 2 | 2 | 3 | 3 |
| B | 0 | 0 | 1 | 1 | 2 |
对于每一列，A 的票数始终大于 B 的票数，因此 A 始终严格领先于 B。对于顺序 AABBA，选举过程中的投票结果如下 −
| 候选人 | A | A | B | B | A |
|---|---|---|---|---|---|
| A | 1 | 2 | 2 | 2 | 3 |
| B | 0 | 0 | 1 | 2 | 2 |
就此顺序而言，B 在第四次投票后与 A 持平，因此 A 并不总是严格领先于 B。在 10 个可能的顺序中，只有在 AAABB 的情况下 A 才始终领先于 B，并且AABAB。因此，A 总是领先于其他人的概率是 2/10=1/5，这确实等于定理所预测的 3-2 / 3+2。
