1.2　统计分析法的实验范例

在一时得不到事物的特征机理的情况下，我们可先通过手算或编程等方法测试得到一些数据（即问题的部分解），再利用数理统计知识对数据进行处理，从而得到最终的数学模型。

图1.2-1给出了统计分析法的大致流程：先从Ad Hoc问题的原型出发，通过手工或简单的程序得到问题的部分解（即解集A），然后运用数理统计方法，通过部分解得到问题原型的主要属性（大部分属性是规律性的东西），从而建立数学模型，最后通过算法设计和编程得到问题的全部解（即全集I）。这里需要注意的是：
1）因为有时候根本无法求出问题的部分解，或者无法用数理统计知识分析部分解，所以求部分解的过程和对部分解进行数理统计的过程画的是虚线，表示不是每个信息原型都能用统计分析法建模。
2）所有模型对应的算法是将盲目搜索排除在外的。因为盲目搜索是从全集I出发求解集A的，这违背了建模的目的。我们所讨论的统计分析法，是在对全解集I的子集A进行数理统计的基础上建立数学模型，所以盲目搜索不属于统计分析法的范畴。
3）一般来说，我们可以先采用机理分析法进行分析；如果机理分析进行不下去，再考虑使用统计分析法。当然，如果问题容易找到部分简单解，我们亦可优先考虑统计分析法。事实上，机理分析所得出的某些结论，往往可有效地运用于统计分析法；而统计分析法得出的某些规律，最终需要通过机理分析验证其准确性。所以这两者彼此并不是孤立的。我们在建模的时候完全可以两者兼用。
【1.2.1　Ants】
【问题描述】
一支蚂蚁军队在长度为l厘米的横竿上走，每只蚂蚁的速度恒定，为1厘米/秒。当一只行走的蚂蚁到达横竿终点的时候，它就立即掉了下去；当两只蚂蚁相遇的时候，它们就调转头，并开始往相反的方向走。我们知道蚂蚁在横竿上原来的位置，但不知道蚂蚁行走的方向。请计算所有蚂蚁从横竿上掉下去的最早可能的时间和最晚可能的时间。
输入：
输入的第一行给出一个整数，表示测试用例个数。每个测试用例首先给出两个整数：横竿的长度（以厘米为单位）和在横竿上的蚂蚁的数量n。接下来给出n个整数，表示每只蚂蚁在横竿上从左端测量过来的位置，没有特定的次序。所有输入数据不大于1000000，数据间用空格分隔。
输出：
对于输入的每个测试用例，输出用一个空格分隔的两个数，第一个数是所有的蚂蚁掉下横竿的最早可能的时间（如果它们的行走方向选择合适），第二个数是所有的蚂蚁掉下横竿的最晚可能的时间。

试题来源：Waterloo local 2004.09.19

在线测试地址：POJ 1852，ZOJ 2376，UVA 10714
试题解析
蚂蚁数的上限为1000000，爬行方向共有21000000种,这是一个天文数字，因此不可能真的去逐一枚举蚂蚁的方向。
我们先研究蚂蚁少的时候的一些情况（见图1.2-2）。
显然，蚂蚁愈多变化愈多，情况愈复杂。其实解题的瓶颈就是蚂蚁相遇的情况。假如我们拘泥于“对于相遇如何处理”这个细节，将陷入无从着手的窘境。
假如出现这样一种情况：蚂蚁永远不会相遇（即所有向左走的蚂蚁都在向右走的蚂蚁的左边），那么很容易找出O(n)的算法。
我们回过头观察前面给出的那个例子。我们发现相遇只会发生在出现“”时，相遇后就变成了“”，这就相当于忽略了“相遇”这一事件。也就是说，我们可以假设这些蚂蚁即使相遇了也不理睬对方而继续走自己的路。对于问题来说，所有的蚂蚁都是一样的，并无相异之处，因此这个假设是合理的。这样，每只蚂蚁掉落所用时间就只有两个取值：一个是向左走用的时间，一个是向右走用的时间。全部掉落的最早时间就是每只蚂蚁尽快掉落用时的最大值，因为这些蚂蚁现在互不干扰。同理，全部掉落的最迟时间就是每只蚂蚁尽量慢掉落用时的最大值。由此得出算法，设
li为蚂蚁i在横竿上从左端过来测量的位置（1≤i≤n）；little为N只蚂蚁掉下横竿的最早可能时间；big为N只蚂蚁掉下横竿的最晚可能的时间。
本题从最简单的情况入手，通过分析发现所有蚂蚁的等价性，将“相遇后转向”转变为“相遇互不干扰”，从而简化了问题，可以轻而易举地计算出答案。
程序清单

#include <stdio.h>
int c,big,little,L,i,j,k,n;　　　　　　　　　　　　// 测试用例数为c；big、little分别为最晚时间
// 和最早时间；横竿长度为L；竿上的蚂蚁数为n
main(){
scanf("%d",&c);// 输入测试用例数
while (c-- && (2 == scanf("%d%d",&L,&n))) {// 输入横竿长度和横竿上的蚂蚁数
big = little = 0;// 最晚时间和最早时间初始化
for (i=0;i<n;i++) {// 输入每只蚂蚁的测量位置
scanf("%d",&k);
if (k > big) big = k;// 根据k的左方长度和右方长度调整最晚时间
if (L-k > big) big = L-k;
if (k > L-k) k = L-k;// 由k左右方长度的最小值调整最早时间
if (k > little) little = k;
}
printf("%d %d＼n",little,big);// 输出所有蚂蚁掉下横竿的最早时间和最晚时间
}
if (c !=-1) printf("missing input＼n");
}

【1.2.2　Matches Game】
【问题描述】
有一个简单的游戏。在这个游戏中，有若干堆火柴和两个玩家。两个玩家一轮一轮地玩。在每一轮中，一个玩家可以选择一个堆，并从该堆取走任意根火柴（当然，取走火柴的数量不可能为0，也不可能大于所选的火柴的数量）。如果一个玩家取了火柴后，没有火柴留下，那么这个玩家就赢了。假设两个玩家非常聪明，请告诉大家是否先玩的玩家会赢。
输入：
输入由若干行组成，每行一个测试用例。每行开始首先给出整数M(1≤M≤20)，表示火柴堆的堆数；然后给出M个不超过10000000的正整数，表示每个火柴堆的火柴数量。
输出：
对每个测试用例，如果是先手的玩家赢，则在一行中输出"Yes"；否则输出"No"。

试题来源：POJ Monthly,readchild
在线测试地址：POJ 2234
试题解析
先考查最简单的情况：
1）如果游戏开始时只有一堆火柴，则游戏人Ⅰ通过取走所有的火柴而获胜。
2）如果游戏开始时有两堆火柴，且火柴数量分别为N1和N2。
游戏人取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。
若N1≠N2，则游戏人Ⅰ从大堆中取走火柴使得两堆火柴数量相等，于是游戏人Ⅰ以后每次取子的数量与游戏人Ⅱ相等而最终获胜。
若N1=N2，则游戏人Ⅱ只要按着游戏人Ⅰ取子的数量在另一堆中取相等数量的火柴，最终获胜者将会是游戏人Ⅱ。
这样，两堆的取子获胜策略就已经找到了。现在的问题是，如何从两堆的取子策略扩展到任意堆数中呢？
3）任意堆数。
首先来回忆一下，每个正整数都有一个对应的二进制数，例如：57(10)=111001(2)，即57(10)=25+24+23+20。于是，我们可以认为每一堆火柴数由2的幂数的子堆组成。这样，含有57枚火柴的大堆就能看成是分别由数量为25、24、23、20的4个子堆组成。
现在考虑各大堆大小分别为N1，N2，…，Nk的取子游戏。将每一个数Ni表示为其二进制数（数的位数相等，不等时在前面补0）：N1=as…a1a0
N2=bs…b1b0
　　…
Nk=ms…m1m0如果每一种大小的子堆数都是偶数，我们就称取子游戏是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此取子游戏是平衡的，当且仅当as+bs+…+ms是偶数
…　
a1+b1+…+m1是偶数
a0+b0+…+m0是偶数这里之所以提出取子游戏平衡的概念，是因为当一方处于平衡状态（非平衡状态）时，对方总能够通过下一轮取子使之变成非平衡状态（平衡状态）。而赢方的最后状态是s+1位都为平衡位（全0）。于是，我们猜想出一个获胜策略：
游戏人Ⅰ能够在非平衡取子游戏中取胜，而游戏人Ⅱ能够在平衡的取子游戏中取胜。
下面通过统计分析方法证明上述猜想。先以一个两堆火柴的取子游戏作为试验：
设游戏开始时游戏处于非平衡状态。这样，游戏人Ⅰ就能通过一种取子方式(见下面的归纳)使得他取子后留给游戏人Ⅱ的是一个平衡状态下的游戏，接着无论游戏人Ⅱ如何取子，再留给游戏人Ⅰ的一定是一个非平衡状态下的游戏(只有二进制情形下能达到这种必然的转变，因为任何取子均会改变一个或多个位置上的比特值，而任何一个比特值的改变要么是0变1要么是1变0，这都会改变奇偶性。但是在多进制情形下，某一位置上2变0或3变1就不会改变平衡性。换句话说，平衡性只在二进制下定义，定义多进制下的平衡性没有意义)，如此反复进行，当游戏人Ⅱ在最后一次平衡状态下取子后，游戏人Ⅰ便能一次性取走所有的火柴而获胜。而如果游戏开始时游戏处于平衡状态，那根据上述方式取子，最终游戏人Ⅱ能获胜。
接下来，应用此获胜策略来考虑4堆火柴的取子游戏。其中各堆的大小分别为7，9，12，15枚火柴，用二进制表示各数分别为：0111，1001，1100和1111，于是可得到表1.2-1。

由取子游戏的平衡条件可知，此游戏是一个非平衡状态的取子游戏，因此，游戏人Ⅰ在按获胜策略进行取子游戏下将一定能够取得最终的胜利。具体做法有多种，游戏人Ⅰ可以从大小为12的堆中取走11枚火柴，使得游戏达到平衡（如表1.2-2）。

游戏人Ⅰ将非平衡状态转为平衡状态的方法是：将某一行的非平衡位取反并使得取反之后该行的值小于取反之前的值。取子个数为取反前后数值之差。
之后，无论游戏人Ⅱ如何取子，游戏人Ⅰ在取子后仍使得游戏达到平衡。
同样的道理，游戏人Ⅰ也可以选择大小为9的堆并取走5枚火柴而剩下4枚，或者游戏人Ⅰ从大小为15的堆中取走13枚而留下2枚。
归根结底，取子游戏的关键在于游戏开始时游戏处于何种状态（平衡或非平衡）和第一个游戏人是否能够按照取子游戏的获胜策略来进行游戏。由此得出算法：
n堆火柴数量对应的n个二进制数，连续进行n-1次异或运算。若结果非0，则说明存在非平衡位，先手的玩家赢；若结果为0，则说明所有位平衡，后手的玩家赢。
程序清单

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <string>
# include <cmath>
# include <algorithm>
using namespace std;

int main(){
int n;
while(~scanf("%d",&n)){　　　　　　// 输入火柴堆数
int a=0,b;// 结果a初始化，当前堆的火柴数为b
for(int i=0;i<n;i++){// 输入每堆火柴的数量
scanf("%d",&b);
a^=b;// 异或当前堆的火柴数
}
printf("%s＼n",a?"Yes":"No");// 若a出现非平衡位，则先手的玩家赢；若a的所有位平衡，
// 则后手的玩家赢
}
return 0;
}