黑马程序员技术交流社区

标题: 一个安排比赛的程序 [打印本页]

---

作者: 怀念黑海岸    时间: 2014-9-15 23:12
标题: 一个安排比赛的程序
     看算法的时候遇到一个题目：
        两个乒乓球队进行比赛，各出三人。A队为a,b,c三人，B队为x,y,z三人。
        已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队  赛手的名单。 现在把自己写好的代码发上来，看大家有没有更好的建议和意见。
package com.codeWrite;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class FindOpponent {
        /**
        两个乒乓球队进行比赛，各出三人。甲队为a,b,c三人，乙队为x,y,z三人。
        已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比，c说他不和x,z比，请编程序找出三队赛手的名单。
         */
        List<TeamA> teamA =new ArrayList<TeamA>();  //用来存放A组的列表
        List<TeamB> teamB =new ArrayList<TeamB>();  //用来存放B组的列表
        List<Team> team =new ArrayList<Team>();     //所有队员的列表
        Map<TeamA,TeamB> map =new HashMap<TeamA,TeamB>();//用来存放比赛对阵名单
       
        public void arrangeMatch(){
                /*如何安排比赛的判断条件就是：在不违反当前队员的比赛条件前提下，同时与其他有比赛条件的队员之间不能发生冲突而且应该从限制条件多的队员开始进行考虑，因为限制越多其能选择的对手就越少，所以优先考虑。
                */
                while(team.size()>0){
                        if(team.get(0) instanceof TeamA){//从队员列表的第一个队员开始遍历
                                TeamA eachA =(TeamA)team.get(0);
                                if(eachA.list!=null){// 如果这个队员有限制条件的话
                                        List<TeamB> copyTeamB=cloneList(teamB);  //将B组的队员列表复制一份
                                        teamB.removeAll(eachA.list);//将B组中不符合当前队员的条件剔除掉
                                        for(TeamB eachB:teamB){ //进行互斥判断
                                                if(canArrange(eachA,eachB)){//如果两者可以互为对手的话
                                                        eachA.t=eachB;    //相互为对手
                                                        eachB.t=eachA;
                                                        teamA.remove(eachA);  //安排好的队员将被删除
                                                        copyTeamB.remove(eachB); //将复制过去的列表中删除掉选中队员
                                                        teamB =copyTeamB;  //并将修改后的列表重新复制给teamB
                                                        team.remove(eachA);//并将队员列表中已经安排好的队员去掉
                                                        team.remove(eachB);
                                                        map.put(eachA, eachB);
                                                }
                                        }
                                }
                        }
                        /*更科学的写法这儿应该还有个对B组队员的比赛安排，如果B组队员也有限制条件的话那么队员 列表中的队员顺序就应该是不同组的队员混乱排列
                         */
                }
        }

        public void initial(){  //该方法对参赛队员和限制条件进行初始化
                TeamA a =new TeamA();
                TeamA b =new TeamA();
                TeamA c =new TeamA();
                TeamB x =new TeamB();
                TeamB y =new TeamB();
                TeamB z =new TeamB();
                a.name="a";
                b.name="b";
                c.name="c";
                x.name="x";
                y.name="y";
                z.name="z";
                a.list.add(x);
                c.list.add(x);
                c.list.add(z);
                //这儿最好有个能对限制条件的多少进行降序排序的过程，因为分析所得，需要对限制条件多的队友优先进行比赛的安排
                teamA.add(c);
                teamA.add(a);
                teamA.add(b);
                teamB.add(x);
                teamB.add(y);
                teamB.add(z);
                team.addAll(teamA);
                team.addAll(teamB);
        }
       
        public List<TeamB> cloneList(List<TeamB> list){ //复制一个数组中的元素到另外一个临时数组中
                List<TeamB> newList =new ArrayList<TeamB>();
                for(int i=0;i<list.size();i++){
                        newList.add(list.get(i));
                }
                return newList;
        }  
        public boolean canArrange(TeamA a,TeamB b){   //对两名队员进行互斥判定，是否能够互为对手
                boolean aVSb =false;
                boolean bVSa =false;
                if(a.list!=null){
                        a.list.contains(b);
                                aVSb=true;
                }
                if(b.list!=null){
                        b.list.contains(a);
                                bVSa=true;
                }
                if(aVSb&bVSa){
                        return true;
                }else{
                        return false;
                }
        }
        public void iteMap(Map<TeamA,TeamB> map){  //打印对阵表
                Set<Map.Entry<TeamA,TeamB>> set =map.entrySet();
                for(Map.Entry<TeamA, TeamB> each: set){
                        System.out.print(each.getKey().name+"对阵"+each.getValue().name+'\n');
                }
        }
        public static void main(String[] args) {
                FindOpponent fo =new FindOpponent();
                fo.initial();
                fo.arrangeMatch();
                fo.iteMap(fo.map);
        }
}
interface Team{
}
class TeamA implements Team{
        String name;  //队员名字
        TeamB t;  //对手
        List<TeamB> list=new ArrayList<TeamB>();//用来存放不与之比赛的对手列表
}
class TeamB implements Team{
        String name;
        TeamA t;
        List<TeamA> list=new ArrayList<TeamA>();
}

---

作者: 15579171087    时间: 2014-9-15 23:44
这么长。。。

---

作者: 怀念黑海岸    时间: 2014-9-16 00:12

15579171087 发表于 2014-9-15 23:44
这么长。。。

    其实主要的判断就是安排比赛的那个方法，其他的基本上都是初始化、队员类的代码。

---

作者: 我为你着迷    时间: 2014-9-16 00:17
还不睡{:3_55:}

---

作者: fantacyleo    时间: 2014-9-16 02:04

1. public static void main(String[] args) {
   
2.                 char[] teamB = {'x', 'y', 'z'};
   
3.                 for (int a = 0; a < 3; a++)
   
4.                         for (int b = 0; b < 3; b++)
   
5.                                 for (int c = 0; c < 3; c++)
   
6.                                         if (a != b  && b != c && a != c &&
   
7.                                         teamB[a] != 'x' && teamB[c] != 'x' && teamB[c] != 'z') {
   
8.                                                 System.out.println("a VS " + teamB[a]);
   
9.                                                 System.out.println("b VS " + teamB[b]);
   
10.                                                 System.out.println("c VS " + teamB[c]);
    
11.                                         }
    
12.         }

复制代码

---

作者: 怀念黑海岸    时间: 2014-9-17 11:54

fantacyleo 发表于 2014-9-16 02:04

那如果比赛条件变了呢？a说他不和x比，c说他不和x,z比改成：c不和x比，a说不和x、z比呢？  你又要去该运行代码了。

---

作者: fantacyleo    时间: 2014-9-17 12:07

怀念黑海岸 发表于 2014-9-17 11:54
那如果比赛条件变了呢？a说他不和x比，c说他不和x,z比改成：c不和x比，a说不和x、z比呢？  你又要去该运 ...

你的也要改啊，而且局限性不比我小多少。

---

作者: 怀念黑海岸    时间: 2014-9-17 12:29

fantacyleo 发表于 2014-9-17 12:07
你的也要改啊，而且局限性不比我小多少。

我只需该初始化的代码就行了，不需要改实际的逻辑运行代码。。。

---

作者: fantacyleo    时间: 2014-9-17 12:52

怀念黑海岸 发表于 2014-9-17 12:29
我只需该初始化的代码就行了，不需要改实际的逻辑运行代码。。。

我的代码就几行，还分什么初始化、逻辑运行啊;P  设计就不谈了，你我的代码都是面向过程，和OOD的原则都差着一大截呢

---

作者: 怀念黑海岸    时间: 2014-9-17 20:46

fantacyleo 发表于 2014-9-17 12:52
我的代码就几行，还分什么初始化、逻辑运行啊  设计就不谈了，你我的代码都是面向过程，和OOD的原则都 ...

   我的基础不好，但是我尽量会按照我当前的能力去写好代码。仅此而已。再说了这跟OOD原则有什么关系吗，类似这种问题不能人为的具体确定程序每一步该怎么运行，而是要让程序根据限制条件自己决定怎么怎么运行。这才叫让程序解决问题。

---

作者: 玥夜    时间: 2014-9-18 14:12
你有来了。。。  居然还有时间上论坛

---

作者: 怀念黑海岸    时间: 2014-9-19 13:00

玥夜 发表于 2014-9-18 14:12
你有来了。。。  居然还有时间上论坛

。。。你很忙吗？？最近家里路由器老是出问题，时能联网时不能联的，所以上的时间不多哦。。

---

作者: 玥夜    时间: 2014-9-19 13:02

怀念黑海岸 发表于 2014-9-19 13:00
。。。你很忙吗？？最近家里路由器老是出问题，时能联网时不能联的，所以上的时间不多哦。。 ...

我以为你都去黑马了呢  肿么还在家呢  两点面试啊 有点小忐忑。。。

---

作者: 玥夜    时间: 2014-9-19 15:15

玥夜 发表于 2014-9-19 13:02
我以为你都去黑马了呢  肿么还在家呢  两点面试啊 有点小忐忑。。。

我报48期  0.0 搞定了  

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2