【代码思维锻炼】关于一个简单逻辑题编码实现的思考,该怎么处理
【代码思维锻炼】关于一个简单逻辑题编码实现的思考
题目:两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比,请编程序找出三队赛手的名单。
这是个简单的逻辑题,寻常小学生也能分分钟做出来,但是“编程序”实现,却让我为之一愣。
这个简单问题代表了一类问题:在有限的集合以及有限的条件限定下,求一组解。
让我愣神的原因主要有如下几点:
1. 给出的规则只是客观陈述,没有什么规律性可供总结
2. 程序具有重复性、客观性,不会像人那样有择优的思考倾向,本题没有什么重复性可言
3. 如何通过代码实现规则,让这个问题能解决,却又不局限于这一种场景(假设队员多了,或者限定条件多了)
由这个题目,又想到前两天百度百科看到的八皇后问题的java源码。短短四五十行代码,就实现了,让我这个写了几百行都没实现好的人,为之汗颜。现在想来,它之所以精简,一方面明确判定条件,另一方面是因为他把问题抽象的好,不慌不忙,很清晰的知道自己要实现什么。有的时候,同样一个算法,能够很好的抽象出问题的本质,会大大精简代码。而我碰到比较“麻烦的问题”时,常常会头皮一炸,然后东戳一下,西搞一下,思路不清晰,结果总是不那么理想。
废话了那么多,这里就是想针对这么个简单的乒乓球问题,看看大家伙是怎么个思路实现的,如果问题扩展了(例如队员数增多,或条件多了),对代码冲击大不大。大家一起讨论讨论,学习学习,看看有没有比较好的思路。
(我的一个实现已经写好了,和大家探讨一下再拿出来看看吧)
大家可以文字描述自己的建模思路,或算法描述,也可以直接上代码(代码关键步骤最好稍微带点注释说明),一起讨论各自思路、算法、代码的可行性、合理性。
月底结贴。
【2013-12-20】
这边也给出一个之前的代码实现,欢迎指正,欢迎大家继续讨论~
题目:两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比,请编程序找出三队赛手的名单。
这是个简单的逻辑题,寻常小学生也能分分钟做出来,但是“编程序”实现,却让我为之一愣。
这个简单问题代表了一类问题:在有限的集合以及有限的条件限定下,求一组解。
让我愣神的原因主要有如下几点:
1. 给出的规则只是客观陈述,没有什么规律性可供总结
2. 程序具有重复性、客观性,不会像人那样有择优的思考倾向,本题没有什么重复性可言
3. 如何通过代码实现规则,让这个问题能解决,却又不局限于这一种场景(假设队员多了,或者限定条件多了)
由这个题目,又想到前两天百度百科看到的八皇后问题的java源码。短短四五十行代码,就实现了,让我这个写了几百行都没实现好的人,为之汗颜。现在想来,它之所以精简,一方面明确判定条件,另一方面是因为他把问题抽象的好,不慌不忙,很清晰的知道自己要实现什么。有的时候,同样一个算法,能够很好的抽象出问题的本质,会大大精简代码。而我碰到比较“麻烦的问题”时,常常会头皮一炸,然后东戳一下,西搞一下,思路不清晰,结果总是不那么理想。
废话了那么多,这里就是想针对这么个简单的乒乓球问题,看看大家伙是怎么个思路实现的,如果问题扩展了(例如队员数增多,或条件多了),对代码冲击大不大。大家一起讨论讨论,学习学习,看看有没有比较好的思路。
(我的一个实现已经写好了,和大家探讨一下再拿出来看看吧)
大家可以文字描述自己的建模思路,或算法描述,也可以直接上代码(代码关键步骤最好稍微带点注释说明),一起讨论各自思路、算法、代码的可行性、合理性。
月底结贴。
【2013-12-20】
这边也给出一个之前的代码实现,欢迎指正,欢迎大家继续讨论~
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PingpongGame {
// 选手集
private static final List<String> teamA = new ArrayList<String>();
private static final List<String> teamB = new ArrayList<String>();
// 结果集:teamA队员为key,teamB队员为value
private static final Map<String, String> result = new HashMap<String, String>();
// 规则集:不允许集,teamA某个队员为key,不允许的对手名单列表为value
private static final Map<String, List<String>> noMap = new HashMap<String, List<String>>();
// 规则集初始化
static {
// 队员初始化
teamA.add("a");
teamA.add("b");
teamA.add("c");
teamB.add("x");
teamB.add("y");
teamB.add("z");
// a说他不和x比
List<String> aNoList = new ArrayList<String>();
aNoList.add("x");
noMap.put("a", aNoList);
// b的对手任意
List<String> bNoList = new ArrayList<String>();
noMap.put("b", bNoList);
// c说他不和x,z比
List<String> cNoList = new ArrayList<String>();
cNoList.add("x");
cNoList.add("z");
noMap.put("c", cNoList);
}
public static void main(String[] args) {
// 最终要得到的结果,是三队比赛场次的输出
for (;;) {
// 跳出循环的条件:形成三组对抗
if (result.size() == teamA.size()) {
break;
}
// 遍历A组学员
for (String member : teamA) {
// 若当前队员已经有对手,则跳过本次循环
if (null != result.get(member)) {
continue;
}
// 判断当前成员的不可能对手集,若teamB去掉此集合后,仅剩下一个队员,则录入结果集
checkNoListAnd(member, noMap.get(member));
}
}
// 打印结果
for (Map.Entry<String, String> entry : result.entrySet()) {