逻辑推断

逻辑推断

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注