2020-5-13递归练习 六人参加竞赛
一、题目
Java编程：**从A、B、C、D、E、F六位同学中挑选一些人去参加某项竞赛活动。根据竞赛规则，参赛人员须满足下列要求：
- （1）A、B两人中至少去一个人；
- （2）A、D两人不能同时去；
- （3）A、E、F三人中要选两人去；
- （4）B、C两人都去或者都不去；
- （5）C、D两人中去一个人；
- （6）若D不去，则E也不去。
选中参赛的人是（ ）
二、思路：
- 用boolean数组来表示，这六个人去不去。
- 用六个boolean表示，六个条件。
- 递归暴力搜。
- 用递归，就不用了六个for循环了。
三、代码
static boolean[] b = new boolean[6];
static char[] c = { 'A', 'B', 'C', 'D', 'E', 'F' };
public static void main(String[] args) {
f(0);
for (int i = 0; i < b.length; i++) {
if (b[i]) {
System.out.print(c[i]+" ");
}
}
}
// static int count = 0;
private static boolean flag = false;
static void f(int x) {
// 百度了一下非运算，优先级太高了，得加括号
boolean tf1 = b[0] || b[1];// ab至少去一个人,可以都去.或运算
boolean tf2 = !(b[0] && b[3]); // ad不能同时去，可以都不去 先且运算，同时去，然后非运算
boolean tf3 = !(b[0] ^ b[4] ^ b[5]) && ((b[0] || b[4] || b[5])); // aef选两个，异或选出两个加上全都不选，在通过或排除
boolean tf4 = !(b[1] ^ b[2]); // bc都去或都不去。异或
boolean tf5 = b[2] ^ b[3]; // cd去一个人，二选一
boolean tf6 = b[3] || !(b[3] ^ b[4]); // d不去，e不去，d去，e可不去。
if (tf1 && tf2 && tf3 && tf4 && tf5 && tf6) {
flag = true;
return;
} else {
for (int i = x; i < b.length; i++) {
b[i] = true;
// count++;
f(x + 1);
if (flag)
return;
b[i] = false;
}
}
}
用int来代替，在操作更秀一点，判断起来容易一点。
参见：
引用的第一个种方式，用了六个for，用递归可以少写一些for。数字相加的结果表示去了几个人........
第二种，二进制进行计算。只用一个for循环就行。每个人有两种状态就是2^6 中状态，从1循环加到2^6，来判断就行。
我的递归代码很烂。还得多练练。
四、总结
以上三种方法，都是暴力操作，不知道有没有大佬有更秀的方法。