首页 > 其他 > 详细

一道竞赛题

时间:2014-07-28 19:08:14      阅读:358      评论:0      收藏:0      [点我收藏+]

/**

* A、B、C、D、E、F、G、H、I、J 共10名学生有可能参加本次计算机竞赛,也可能不参加。因为某种原因,他们是否参赛受到下列条件的约束
* 1. 如果A参加,B也参加;
* 2. 如果C不参加,D也不参加;
* 3. A和C中只能有一个人参加;
* 4. B和D中有且仅有一个人参加;
* 5. D、E、F、G、H 中至少有2人参加;
* 6. C和G或者都参加,或者都不参加;
* 7. C、E、G、I中至多只能2人参加

* 8. 如果E参加,那么F和G也都参加。 

* 9. 如果F参加,G、H就不能参加
* 10. 如果I、J都不参加,H必须参加

* 打印所有满足条件的情况~

*/

我的思路是:

10名同学,每人要么参加,要么不参加,所以一共有2的10次方即1024种的可能性,

那么我们可以用0到1024的二进制表示所有可能,如11 1111 1111 表示所有同学都参加了,

我们然后遍历所有可能,进行筛选,最后将结果转换成字符

 

代码如下:

 

public static void main(String[]args){
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<1024;i++){    
            if(((i>>9)&1)==1&&((i>>8)&1)!=1){
                continue;
            }
            if(((i>>7)&1)==0&&((i>>6)&1)!=0){
                continue;
            }
            if(((i>>9)&1)*((i>>7)&1)==1){
                continue;
            }
            if((((i>>8)&1)+((i>>6)&1))==0||(((i>>8)&1)+((i>>6)&1))==2){
                continue;
            }
            if((((i>>6)&1)+((i>>5)&1)+((i>>4)&1)+((i>>3)&1)+((i>>2)&1))<2){
                continue;
            }
            if((((i>>7)&1)+((i>>3)&1))==1){
                continue;
            }
            if(((i>>5)&1)==1&&(((i>>4)&1)==0||((i>>3)&1)==0)){
                continue;
            }
            if(((i>>4)&1)==1&&(((i>>3)&1)==1|((i>>2)&1)==1)){
                continue;
            }
            if(((i>>6)&1)==0&&((i>>6)&1)==0&&((i>>6)&1)==0){
                continue;
            }
            list.add(i);
            
        }
        System.out.println("size()======"+list.size());
        for(int i=0;i<list.size();i++){
            String s = Integer.toBinaryString((Integer) list.get(i));
            for(int j=9;j>-1;j--){
                if(((list.get(i)>>j)&1)==1){
                    System.out.print((char)(‘I‘-j+1));
                }
            }
            System.out.println();
        }    
    }

 

 运行结果:

size()======8
CDG
CDGJ
CDGI
CDGIJ
CDGH
CDGHJ
CDGHI
CDGHIJ

 

如果有其他好方法,欢迎分享~

 

一道竞赛题,布布扣,bubuko.com

一道竞赛题

原文:http://www.cnblogs.com/asongaaa/p/3873108.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!