title: 某保密单位机要人员-解题报告
date: 2016-03-27 16:12:39
tags: 算法
categories: 算法
某保密单位机要人员 A，B，C，D，E 每周需要工作5天，休息2天。
上级要求每个人每周的工作日和休息日安排必须是固定的，不能在周间变更。
此外，由于工作需要，还有如下要求：
1. 所有人的连续工作日不能多于3天（注意：周日连到下周一也是连续）。
2. 一周中，至少有3天所有人都是上班的。
3. 任何一天，必须保证 A B C D 中至少有2人上班。
4. B D E 在周日那天必须休息。
5. A E 周三必须上班。
6. A C 一周中必须至少有4天能见面（即同时上班）。
你的任务是：编写程序，列出ABCDE所有可能的一周排班情况。工作日记为1，休息日记为0
A B C D E 每人占用1行记录，从星期一开始。
【输入、输出格式要求】
程序没有输入，要求输出所有可能的方案。
每个方案是7x5的矩阵。只有1和0组成。
矩阵中的列表示星期几，从星期一开始。
矩阵的行分别表示A，B，C，D，E的作息时间表。
多个矩阵间用空行分隔开。
例如，如下的矩阵就是一个合格的解。请编程输出所有解(多个解的前后顺序不重要)。
0110111
1101110
0110111
1101110
1110110
【注意】
请仔细调试！您的程序只有能运行出正确结果的时候才有机会得分！
在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。
请把所有函数写在同一个文件中，调试好后，拷贝到【考生文件夹】下对应题号的“解答.txt”中即可。
相关的工程文件不要拷入。
源代码中不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。
允许使用STL类库，但不能使用MFC或ATL等非ANSI c++标准的类库。
例如，不能使用CString类型（属于MFC类库），不能使用randomize, random函数（不属于ANSI C++标准）
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int peo[30][7];
int temp[7];
int count = 0;
int judge()
{
int min=100,max=0;
for(int i=0;i<7;i++)
{
if(temp[i] == 0)
{
if(min>i)
min = i;
if(max<i)
max = i;
}
}
if((max-min)%6 == 3||(max-min)%6 == 4)
return 1;
else
return 0;
}
int dfs(int depth)
{
if(depth == 7)
{
int num = 0;
for(int i=0;i<7;i++)
{
if(temp[i] == 1)
{
num++;
}
}
if(num == 5)
{
// *peo[count] = *temp;
if(judge())
{
memcpy(peo[count],temp,sizeof(temp));
count++;
}
}
}
else
{
for(int i=0;i<2;i++)
{
temp[depth] = i;
dfs(depth+1);
}
}
}
int fun(int i,int j,int k,int m,int n)
{
int count = 0;
for(int a=0;a<7;a++)
{
if(peo[i][a]+peo[j][a]+peo[k][a]+peo[m][a]+peo[n][a]==5)
{
count++;
}
}
if(count>=3)
return 1;
else
return 0;
}
int funa(int i,int j,int k,int m)
{
int count = 0;
for(int a=0;a<7;a++)
{
if(peo[i][a]+peo[j][a]+peo[k][a]+peo[m][a] >=2)
{
count++;
}
}
if(count >= 7)
{
return 1;
}
else
{
return 0;
}
}
int funb(int i,int k)
{
int count = 0;
for(int a=0;a<7;a++)
{
if(peo[i][a]+peo[k][a] == 2)
{
count++;
}
}
if(count>=4)
{
return 1;
}
else
return 0;
}
void func(int i)
{
for(int a=0;a<7;a++)
{
cout<<peo[i][a]<<" ";
}
cout<<endl;
}
int main()
{
dfs(0);
for(int i=0;i<count;i++)
{
for(int j=0;j<count;j++)
{
for(int k=0;k<count;k++)
{
for(int m=0;m<count;m++)
{
for(int n=0;n<count;n++)
{
if(fun(i,j,k,m,n))
{
if(funa(i,j,k,m))
{
if(peo[j][6]+peo[m][6]+peo[n][6] == 0)
{
if(peo[i][2] + peo[n][2] == 2)
{
if(funb(i,k))
{
func(i);
func(j);
func(k);
func(m);
func(n);
//cout<<"================================================================="<<endl;
cout<<endl;
}
}
}
}
}
}
}
}
}
}
}
