开发者社区> 哈沙给> 正文

蓝桥杯(受约束的10人参赛问题)

简介: 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也都参加。
+关注继续查看

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名同学中参赛者名单。如果有多种可能,则输出所有的可能

情况。每种情况占一行。参赛同学按字母升序排列,用空格分隔。

比如:

C D G J

就是一种可能的情况。

 

 1 //该题的关键还在于如何枚举10个数,可以10重for循环,也可以类似素数环进行回溯,或者二进制枚举 
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int vis[11] = {0};
 7 
 8 //vis若是bool 变不可写成两数相加减 
 9 bool judge()
10 {
11      //a推出(蕴含)b,等价于(非a或b);或者a ==1&&b==1||a==0,等价于a==0||b==1,此次用到了短路表达式的性质 
12      bool t1 = (vis[0]== 0||vis[1] == 1);
13      //类似第一个;或者c==0&&d==0||c=1 
14      bool t2 =( vis[2] == 1||vis[3] == 0);
15      //从第四个条件可以看出这个包含都不参加的情况,等价于都不参加或者只参加一个人,反面是两个人都参加,再取反 !(a==1&&c==1)等价于a==0||c==0,转化为a+c<=1
16      bool t3 = ((vis[0] + vis[2])<=1);//或者等于0 
17      //反面是同时参加或者同时不参加,再取反!(b==d),等价于b+d ==1
18      bool t4 = (vis[1] + vis[3]==1);
19      bool t5 = ((vis[3] + vis[4] + vis[5] + vis[6] + vis[7]) >=2);
20      //c==g,可化为就、相加为0或者2 
21      bool t6 = (vis[2] == vis[6]);
22      bool t7 = ((vis[2]+vis[4]+vis[6]+vis[8])<=2);
23      //类似第一个 
24      bool t8 = (vis[4] == 0||(vis[5] + vis[6] == 2));
25      bool t9 = vis[5]==0||(vis[6]+vis[7]==0);
26      //(i ==0&&j==0)&&h==1||(ij至少一人参加),等价于(i==1||j==1)||h==1 
27      bool t10 = (vis[8]+vis[9]>0)||vis[7]==1;
28      return t1&&t2&&t3&&t4&&t5&&t6&&t7&&t8&&t9&&t10;
29 }
30 void print()
31 {
32      int i,j,k;
33      for(i=0; i<10; i++)
34           if(vis[i]>0)//若vis是bool,所以不可写成vis[i]>0 
35           {
36                char ch = i + 'A';
37                cout<<ch<<" ";
38           }
39 }
40 int main()
41 {
42      int i,j,k;
43      //二进制枚举比递归回溯好理解 
44      //二进制枚举,两数的与或疑惑分别表示集合的交并对称差 
45      int total = 0;//
46      memset(vis,0,sizeof(vis));
47      while(total<1024)//用total的前十位表示参加状态,1024并不是来自1<<10,而是十个1表示(1<<10-1) 
48      {
49           total++;//不可能全都不参加,所以先自增了
50           for(i=0; i<10; i++)//用total的底10为表示状态,或者total按求余法求的底十位 
51           {
52                int temp = (1<<i);
53                int tag = (temp & total);
            // 也可以用临时变量先存储total,然后total每次右移,与1求与,刘汝佳课本上不是这种方法 
54 if(tag) 55 { 56 //cout<<"*******"<<endl; 57 vis[i] = 1;//把赋值号写成了等号 58 } 59 else 60 vis[i] = 0; 61 } 62 bool flag = judge(); 63 //cout<<flag<<endl; 64 if(flag) 65 { 66 print(); 67 cout<<endl; 68 } 69 } 70 cout<<"----"<<endl; //结果没输出,看看是否执行到了这一步 71 cout<<endl; 72 while(1); 73 return 0; 74 } 75 //把给的例子带入发现正确,说明judge函数没问题,那么就是while循环有问题了 ,结果发现vis全为0 ,再以发现把赋值号写成了等号 76 77
 1 //递归回溯 
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int vis[11] = {0};
 7 
 8 //vis若是bool 变不可写成两数相加减 
 9 bool judge()
10 {
11      //a推出(蕴含)b,等价于(非a或b);或者a ==1&&b==1||a==0,等价于a==0||b==1,此次用到了短路表达式的性质 
12      bool t1 = (vis[0]== 0||vis[1] == 1);
13      //类似第一个;或者c==0&&d==0||c=1 
14      bool t2 =( vis[2] == 1||vis[3] == 0);
15      //从第四个条件可以看出这个包含都不参加的情况,等价于都不参加或者只参加一个人,反面是两个人都参加,再取反 !(a==1&&c==1)等价于a==0||c==0,转化为a+c<=1
16      bool t3 = ((vis[0] + vis[2])<=1);//或者等于0 
17      //反面是同时参加或者同时不参加,再取反!(b==d),等价于b+d ==1
18      bool t4 = (vis[1] + vis[3]==1);
19      bool t5 = ((vis[3] + vis[4] + vis[5] + vis[6] + vis[7]) >=2);
20      //c==g,可化为就、相加为0或者2 
21      bool t6 = (vis[2] == vis[6]);
22      bool t7 = ((vis[2]+vis[4]+vis[6]+vis[8])<=2);
23      //类似第一个 
24      bool t8 = (vis[4] == 0||(vis[5] + vis[6] == 2));
25      bool t9 = vis[5]==0||(vis[6]+vis[7]==0);
26      //(i ==0&&j==0)&&h==1||(ij至少一人参加),等价于(i==1||j==1)||h==1 
27      bool t10 = (vis[8]+vis[9]>0)||vis[7]==1;
28      return t1&&t2&&t3&&t4&&t5&&t6&&t7&&t8&&t9&&t10;
29 }
30 
31 void print()
32 {
33      int i,j,k;
34      for(i=0; i<10; i++)
35           if(vis[i]>0)//若vis是bool,所以不可写成vis[i]>0 
36           {
37                char ch = i + 'A';
38                cout<<ch<<" ";
39           }
40 }
41 
42 void dfs(int n)
43 {
44      if(n>=10)
45      {
46           if(judge())
47           {
48                print();
49                cout<<endl;
50           }
51           return ;
52      }
53      vis[n] = 0;
54      dfs(n+1);
55      vis[n] = 1;
56      dfs(n+1);
57 }
58 
59 int main()
60 {
61      int i,j,k;
62      int total = 0;//
63      memset(vis,0,sizeof(vis));
64      dfs(0);
65      cout<<"----"<<endl; //结果没输出,看看是否执行到了这一步      
66      cout<<endl;
67      while(1);
68      return 0;
69 }
70 //把给的例子带入发现正确,说明judge函数没问题,那么就是while循环有问题了 ,结果发现vis全为0 ,再以发现把赋值号写成了等号 
71      
72      


看视频加上写代码和注释共约4个小时,还是相当有成就感的。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23533 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22242 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
14211 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18720 0
windows server 2008阿里云ECS服务器安全设置
最近我们Sinesafe安全公司在为客户使用阿里云ecs服务器做安全的过程中,发现服务器基础安全性都没有做。为了为站长们提供更加有效的安全基础解决方案,我们Sinesafe将对阿里云服务器win2008 系统进行基础安全部署实战过程! 比较重要的几部分 1.
11975 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22007 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36361 0
+关注
哈沙给
渣渣一枚
1101
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载