逻辑推断
时间: 1ms 内存:128M
描述:
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
就是一种可能的情况。多种情况的前后顺序不重要
输入:
输出:
示例输入:
示例输出:
C D G J
C D G H
C D G H J
B C G H
B C G H J
提示:
参考答案(内存最优[1088]):
#include<cstdio>
int a[13];
void judge()
{
if(a[1]+a[2]==2||!a[1])
{
if(!a[3]&&!a[4]||a[3])
{
if(a[1]+a[3]<=1&&a[2]+a[4]==1&&a[4]+a[5]+a[6]+a[7]+a[8]>=2)
{
if(a[3]+a[7]==2||a[3]+a[7]==0)
{
if(a[3]+a[5]+a[7]+a[9]<=2)
{
if(a[5]&&a[6]+a[7]==2||!a[5])
{
if(a[6]&&a[7]+a[8]==0||!a[6])
{
if(a[9]+a[10]==0&&a[8]||a[9]+a[10]>=1)
{
for(int i=1;i<11;i++)
if(a[i]==1)
printf("%c ",'A'+i-1);
printf("\n");
}
}
}
}
}
}
}
}
}
void dfs(int k)
{
if(k==11)
{
judge();
return;
}
for(int i=0;i<=1;i++)
{
a[k]=i;
dfs(k+1);
}
}
int main()
{
dfs(1);
return 0;
}
参考答案(时间最优[0]):
#include <iostream>
#include <cmath>
#include <cstring>
#define PEOPLE 10
#define A (i&p[0])
#define B (i&p[1])
#define C (i&p[2])
#define D (i&p[3])
#define E (i&p[4])
#define F (i&p[5])
#define G (i&p[6])
#define H (i&p[7])
#define I (i&p[8])
#define J (i&p[9])
using namespace std;
int main()
{
int i,j;
int a[10];
int p[PEOPLE];
char end[10][PEOPLE];
char temp[PEOPLE];
int k=0;
for(i=0;i<PEOPLE;i++)
{
p[i]=pow(2,i);
}
for(i=pow(2,PEOPLE)-1;i>=0;i--)
{
if(B||(!A))
{
if(C||(!D))
{
if((A>0)+(C>0)<=1)
{
if((B>0)+(D>0)==1)
{
if((D>0)+(E>0)+(F>0)+(G>0)+(H>0)>=2)
{
if((C>0)+(G>0)!=1)
{
if((C>0)+(E>0)+(G>0)+(I>0)<=2)
{
if((!E)||(F&&G))
{
if(!F||((!G)&&(!H)))
{
if((I||J)||H)
{
a[k++]=i;
}
}
}
}
}
}
}
}
}
}
}
int count;
int s;
for(i=0;i<k;i++)
{
s=0;
count=0;
while(a[i])
{
if(a[i]&1)
{
end[i][s++]=count+'A';
}
count++;
a[i]>>=1;
}
end[i][s]='\0';
}
for(i=0;i<k-1;i++)
{
for(j=i+1;j<k;j++)
{
if(strcmp(end[i],end[j])<0)
{
strcpy(temp,end[i]);
strcpy(end[i],end[j]);
strcpy(end[j],temp);
}
}
}
for(i=0;i<k;i++)
{
if(strlen(end[i])>strlen(end[i+1]))
{
i++;
cout<<end[i][0];
for(j=1;j<strlen(end[i]);j++)
{
cout<<' '<<end[i][j];
}
cout<<endl;
i--;
cout<<end[i][0];
for(j=1;j<strlen(end[i]);j++)
{
cout<<' '<<end[i][j];
}
cout<<endl;
i++;
}
else
{
cout<<end[i][0];
for(j=1;j<strlen(end[i]);j++)
{
cout<<' '<<end[i][j];
}
cout<<endl;
}
}
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。