最近再次遇到一个很久以前就见过的一个编程题。当然,题目是非常简单的,很多参加算法竞赛的同学应该都见过这个问题。

事情是这样的,在一个阳光还算明媚的下午,肖导给我发来一张图片。如下:

img

原来是肖导受到了关爱,要求写这样的一个程序。这个题目看上去就很简单,分成三个步骤:

  1. 枚举所有可能的参赛组合情况

  2. 对每一个组合情况进行上诉判断

  3. 如果通过所有的判断则输出当前组合去参赛的同学名称

但是可达鸭眉头一皱,觉得问题并不简单。

问题描述

A、B、C、D、E、F、G、H、I、J十名同学有可能参加本次竞赛,也有可能不参加。因为某种原因,他们是否参赛收到下列条件的约束:

  1. 如果 A 参加,B 也参加;
  2. 如果 C 不参加, D 也不参加;
  3. A 和 C 中只能有一人可以参加;
  4. B 和 D 有且只有一个人可以参加;
  5. D 、E 、F 、G 、H 五个人中至少有两个人参加;
  6. C 和 G 或者都参加,或者都不参加;
  7. C 、 E 、 G 、 I 中至多只能有两人参加;
  8. 如果 E 参加,那么 F 和 G 也都参加;
  9. 如果 F 参加,G 和 H 就不能参加;
  10. 如果 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 循环一层套一层,如下所示:

1
2
3
4
5
6
7
8
9
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,深度优先搜索)的方式进行遍历所有的组合,如下所示:

1
2
3
4
5
6
7
8
9
10
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 展开成每位同学的参赛情况即可。

展开代码如下:

1
2
3
4
5
6
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 是否成立。

于是笔者封装了如下函数:

1
2
3
4
5
6
bool if_then (bool if_case, bool then_case) {
if (if_case && !then_case) {
return false;
}
return true;
}

至于判断是否满足约束时,则只需要设置好十个条件,一次判断并计数通过判断的个数,最后如果通过判断个数的计数器等于 10 ,则表明通过了所有的判断。

最后,输出参加比赛的学生列表。这里比较简单,就不过多去说了。

1
2
3
4
5
6
7
8
void print_students(bool data[]) {
for (int i = 0; i < STU_CNT; i++) {
if (data[i]) {
printf("%C ", 'A' + i);
}
}
printf("\n");
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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;
}

总结

  1. 完整代码中宏定义是一个增强代码可读性的一个方法,通过宏定义设置 A 同学占用 data[0] ,依此类推。
  2. 通过函数封装提高代码的可读性
  3. 出现多个同属性的数据时应该考虑使用数组进行存储,如这里的十位同学是否参赛的数据。