背景
我们在以前的数学题中一定遇到过这样的问题：
A说xxxx B说xxx C说xxx
然后给一些条件，让你判断每个人说话的真假
这个题目是这样的：
计算机学院准备组织院篮球赛，某班有ABCDE五个同学商量组队参加，他们在讨论谁来打前锋的时候发生了争执，于是他们请了另一个班的同学J当评委，五个人PK百米速度，谁的速度最快就由谁来当前锋，其实五个同学速度相当，比赛结束时，J让他们猜猜排名情况
- A说：“E一定是第一名”
- B说：“我可能是第二名”
- C说：“A最慢”
- D说：“C不是最快的”
- E说：“D应该是第一名”
J最后说：“E肯定不是第二名或者第三名，你们几个只有获得第一名和第二名的人猜对了，你们应该知道谁最快了吧？” 编程给出五个同学的排名。
算法
习惯了通过表达式去计算一个结果的人，很难去用枚举的思维方式来处理问题。尤其对于枚举的模型很难把握。
枚举算法求解这类问题其实很简单，我尝试用以下三句话来说明：
- 把每个人说的话用一个逻辑表达式表示出来
- 枚举解空间内所有可能出现的情况
- 按照题中条件，筛选合法解
建立说话内容（断言）的模型
可以很容易想到，上述问题中A的内容“E是第一名”可以写成：
Score['E'] == 1;
关键在于，如何描述“A说”的这个过程。很容易想到，这个过程实际上是一个从字符到表达式的映射。表达式在C语言中如何作为一个变量来使用？当然是函数指针，于是可以写出下面的代码：
int guessA(){
return Score['E'] == 1;
}
int guessB(){
return Score['B'] == 2;
}
...
int (*guess[256])(); // 定义一个函数指针的数组
guess['A'] = guessA;
guess['B'] = guessB;
...
这样的话，就可以用guess['A']()来表示A猜得正确与否
枚举解空间
这个题目较为简单，5个人的排名当然有5!种情况，可以用C++提供的全排列的库实现，也可以用深搜自己实现。这里使用康托展开逆运算得到（每次计算的时间复杂度为O(1)）
// 生成1~n的全排列中得第k项，返回值在ret中
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
void invKT(int n, int k, int ret[]){
k--;
int vst[8]={0}, j;
for ( int i=0; i<n; i++){
int t = k/fac[n-i-1];
for (j=1; j<=n; j++){
if (!vst[j]){
if (t==0) break;
t--;
}
}
ret[i] = j;
vst[j] = 1;
k %= fac[n-i-1];
}
}
我们可以枚举得到每次的结果：
int score[N]; // score[i]表示('A'+i)排第几名
int rank[N]; // rank[i]表示第i名是谁
for ( int i=1; i<=fac[n]; i++) {
invKT(n, i, score);
for ( int j=0; j<n; j++) rank[score[i]] = 'A'+i;
}
筛选
有了以上的准备工作，筛选就非常容易了。
只有第一名和第二名说的正确：
if (
guess[ rank[1] ]() == 1 &&
guess[ rank[2] ]() == 1 &&
guess[ rank[3] ]() == 0 &&
guess[ rank[4] ]() == 0 &&
guess[ rank[5] ]() == 0
)
E不是第二和第三：
if ( score['E'-'A'] != 2 && score['E'-'A'] != 3 )
总代码
实际的代码为了偷懒，在一些细节上跟上面的分析不太一样，仅供参考。
#include <cstdio>
#include <cstdlib>
int score[6]; // i排第几
int rank[6]; // 第i名是谁
void invKT(int n, int k, int ret[]);
int guess(int i);
int main(){
int n = 5;
for ( int i=1;i<=120;i++){
invKT(n, i, score+1);
for ( int j=1;j<=n;j++) rank[score[j]] = j;
if (guess(rank[1]) && guess(rank[2])
&& guess(rank[3])==0 && guess(rank[4])==0
&& guess(rank[5])==0
&& score[5]!=2 && score[5]!=3) {
for ( int j=1;j<=n;j++){
printf("%c：第%d名\n", 'A'+j-1, score[j]);
}
}
}
return 0;
}
int guess(int i){
return (i==1)*(score[5]==1)
|| (i==2)*(score[2]==2)
|| (i==3)*(score[1]==5)
|| (i==4)*(score[3]!=1)
|| (i==5)*(score[4]==1);
}
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
void invKT(int n, int k, int ret[]){
k--;
int vst[8]={0}, j;
for ( int i=0; i<n; i++){
int t = k/fac[n-i-1];
for (j=1; j<=n; j++){
if (!vst[j]){
if (t==0) break;
t--;
}
}
ret[i] = j;
vst[j] = 1;
k %= fac[n-i-1];
}
}
