用程序去判断每个人说话的真假 - 写给新手的枚举介绍

背景

我们在以前的数学题中一定遇到过这样的问题：

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(){
<span class="hljs-keyword">int</span> n = <span class="hljs-number">5</span>;
<span class="hljs-keyword">for</span> ( <span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=<span class="hljs-number">120</span>;i++){
    invKT(n, i, score+<span class="hljs-number">1</span>);
    <span class="hljs-keyword">for</span> ( <span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;=n;j++) rank[score[j]] = j;

    <span class="hljs-keyword">if</span> (guess(rank[<span class="hljs-number">1</span>]) &amp;&amp; guess(rank[<span class="hljs-number">2</span>]) 
        &amp;&amp; guess(rank[<span class="hljs-number">3</span>])==<span class="hljs-number">0</span> &amp;&amp; guess(rank[<span class="hljs-number">4</span>])==<span class="hljs-number">0</span> 
        &amp;&amp; guess(rank[<span class="hljs-number">5</span>])==<span class="hljs-number">0</span> 
        &amp;&amp; score[<span class="hljs-number">5</span>]!=<span class="hljs-number">2</span> &amp;&amp; score[<span class="hljs-number">5</span>]!=<span class="hljs-number">3</span>) {
            <span class="hljs-keyword">for</span> ( <span class="hljs-keyword">int</span> j=<span class="hljs-number">1</span>;j&lt;=n;j++){
                <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%c：第%d名\n"</span>, <span class="hljs-string">'A'</span>+j-<span class="hljs-number">1</span>, score[j]);
            }
    }
}
<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;

}
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];
}
}