最近再次遇到一个很久以前就见过的一个编程题。当然，题目是非常简单的，很多参加算法竞赛的同学应该都见过这个问题。
事情是这样的，在一个阳光还算明媚的下午，肖导给我发来一张图片。如下：
原来是肖导受到了关爱，要求写这样的一个程序。这个题目看上去就很简单，分成三个步骤：
枚举所有可能的参赛组合情况
对每一个组合情况进行上诉判断
如果通过所有的判断则输出当前组合去参赛的同学名称
但是可达鸭眉头一皱，觉得问题并不简单。
问题描述
A、B、C、D、E、F、G、H、I、J十名同学有可能参加本次竞赛，也有可能不参加。因为某种原因，他们是否参赛收到下列条件的约束：
- 如果 A 参加，B 也参加；
- 如果 C 不参加， D 也不参加；
- A 和 C 中只能有一人可以参加；
- B 和 D 有且只有一个人可以参加；
- D 、E 、F 、G 、H 五个人中至少有两个人参加；
- C 和 G 或者都参加，或者都不参加；
- C 、 E 、 G 、 I 中至多只能有两人参加；
- 如果 E 参加，那么 F 和 G 也都参加；
- 如果 F 参加，G 和 H 就不能参加；
- 如果 I 和 J 都不参加，那么 H 必须参加。
请编程实现判断这些同学哪些会参加本次竞赛，如果有多种可能，则输出所有可能情况。每种情况占一行。参赛同学按字母升序排列，之间用空格隔开。
问题分析
如上述分析，只需三步。那么笔者觉得问题并不简单的考虑在于，如果按照上述方式来编写代码，其实很容易实现，但是写出来的代码可读性非常差。随手翻看了一下网上找到的几篇博客写的代码
https://blog.csdn.net/u013091087/article/details/43793545
https://blog.csdn.net/wang263334857/article/details/9191215
http://bbs.bccn.net/thread-341841-1-1.html
当然我这里并不是打算去 diss 谁，或者说是批评这些代码写得如何如何不好。
首先，分析一下遍历的过程，我大概看到最多的遍历就是 for 循环一层套一层，如下所示：
for (int a = 0; a <= 1; a++) {
for (int b = 0; b <= 1; b++) {
for (int c = 0; c <= 1; c++) {
for (int d = 0; d <= 1; d++) {
...
}
}
}
}
还有就是通过 DFS（Depth-First Search，深度优先搜索）的方式进行遍历所有的组合，如下所示：
void dfs(int cur) {
if (cur == 10) {
Test();
return ;
}
a[cur] = 1;
dfs(cur+1);
a[cur] = 0;
dfs(cur + 1);
}
都是可以实现的， 第一种方式通过层层 for 嵌套带来的问题就是代码太长，而且使用大量的变量；第二种方式通过 DFS 遍历带来的问题在于可读性会变差，而且这里还使用了全局变量。
在编写程序时，需要尽量不使用全局变量，因为全局变量可能会带来变量冲突的问题。
那么通过分析发现，其实这里每一位同学的参赛情况就是两种状态：参加、不参加。而十位同学的所有参赛状态组合，正好就是十位二进制的所有数字，即：数字0 ～ 数字1023的二进制表示。
于是对于遍历就可以非常简单的变为：for (int val = 0; val <= 1023; val++) 然后只需要将 val 展开成每位同学的参赛情况即可。
展开代码如下：
void extract_data(int val, bool data[]) {
for (int i = 0; i < STU_CNT; i++) {
data[i] = val % 2;
val /= 2;
}
}
其次，约束判断的写法也有考虑，通过对问题的分析发现所有的约束条件都可以写成：如果 p ，那么 q. 这样的形式。也就是说在 p 发生的条件下，q 必须要满足。言下之意，如果 p 不发生，那么就不需要去考虑 q 是否成立。
于是笔者封装了如下函数：
bool if_then (bool if_case, bool then_case) {
if (if_case && !then_case) {
return false;
}
return true;
}
至于判断是否满足约束时，则只需要设置好十个条件，一次判断并计数通过判断的个数，最后如果通过判断个数的计数器等于 10 ，则表明通过了所有的判断。
最后，输出参加比赛的学生列表。这里比较简单，就不过多去说了。
void print_students(bool data[]) {
for (int i = 0; i < STU_CNT; i++) {
if (data[i]) {
printf("%C ", 'A' + i);
}
}
printf("\n");
}
完整代码
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
#define J 9
#define STU_CNT 10
#define MAX_VAL (1<<STU_CNT)-1
void extract_data(int val, bool data[]) {
for (int i = 0; i < STU_CNT; i++) {
data[i] = val % 2;
val /= 2;
}
}
bool if_then (bool if_case, bool then_case) {
if (if_case && !then_case) {
return false;
}
return true;
}
bool test_func (const bool data[]) {
int passed = 0;
/* 1. 如果A参加，B也参加 */
passed += if_then(data[A], data[B]);
/* 2. 如果C不参加，D也不参加 */
passed += if_then(!data[C], !data[D]);
/* 3. A和C中只能有一人可以参加 */
passed += if_then(true, data[A] + data[C] < 2);
/* 4. B和D有且只有一个人可以参加 */
passed += if_then(true, data[B] + data[D] == 1);
/* 5. D、E、F、G、H五个人中至少有两个人参加 */
passed += if_then(true, data[D] + data[E] + data[F] + data[G] + data[H] >= 2);
/* 6. C与G或者都参加，或者都不参加 */
passed += if_then(true, data[C] + data[G] == 2 || data[C] + data[G] == 0);
/* 7. C、E、G、I中至多只能有两人都参加 */
passed += if_then(true, data[C] + data[E] + data[G] + data[I] <= 2);
/* 8. 如果E参加，那么F和G也都参加 */
passed += if_then(data[E], data[F] && data[G]);
/* 9. 如果F参加，G和H就不能参加 */
passed += if_then(data[F], !data[G] && !data[H]);
/* 10. 如果I和J都不参加，那么H必须参加 */
passed += if_then(!data[I] && !data[J], data[H]);
if (passed < 10) {
return false;
}
return true;
}
void print_students(bool data[]) {
for (int i = 0; i < STU_CNT; i++) {
if (data[i]) {
printf("%C ", 'A' + i);
}
}
printf("\n");
}
int main() {
bool *data = (bool*) malloc(sizeof(bool) * STU_CNT);
for (int val = 0; val <= MAX_VAL; val++) { /* 1. 遍历 */
extract_data(val, data); /* 2. 展开 */
if (test_func(data)) { /* 3. 约束判断 */
print_students(data); /* 4. 输出 */
}
}
return 0;
}
总结
- 完整代码中宏定义是一个增强代码可读性的一个方法，通过宏定义设置
A同学占用data[0]，依此类推。 - 通过函数封装提高代码的可读性
- 出现多个同属性的数据时应该考虑使用数组进行存储，如这里的十位同学是否参赛的数据。