排班问题算法

⑴ 题目5：排班系统 学校实验楼有7名保安人员：钱、赵、孙、李、周、吴、陈。由于工作需要进行轮休制度，一星

算法1：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Person
{
int cnDay;
int day[7]; //开的足够大,假设某个人可能7天都忙- -.
char pName[10];
};

char name[7][10]; //7个人,每人名字不超过10
Person p[7];//7个人的信息
bool isEmpty[7]={false}; //标记7天已占用情况

void setTable(int i)
{
if(i==7)
{
printf("星期一 星期二 星期三 星期四 星期五 星期六 星期日 \n");
for(int k=0;k<7;++k)
{
printf("%s ",name[k]);
}
printf("\n");
return;
}
int k=0;
for(;k<p[i].cnDay;++k)
{
if(isEmpty[p[i].day[k]]==false)
{
isEmpty[p[i].day[k]]=true;
strcpy(name[p[i].day[k]],p[i].pName);
setTable(i+1);
isEmpty[p[i].day[k]]=false;
}
}
}

int main()
{
int day;
int count;
for(int i=0;i<7;++i)
{
printf("输入第%d个人的名字,然后依次输入每个人的繁忙日,输入0结束此人信息录入！\n",i+1);
count=0;
scanf("%s",p[i].pName);
scanf("%d",&day);
while(day!=0)
{
p[i].day[count]=day-1;
++count;
scanf("%d",&day);
}
p[i].cnDay=count;
}
setTable(0);
return 0；
}
算法2：
#include <stdio.h>

int n = 0;
int rest[7][7];

void swap(int *a, int *b)
{
int m;
m = *a;
*a = *b;
*b = m;
}

void perm(int list[], int k, int m)
{
int i;
int j;
if(k > m)
{
for (i=0; i<7; i++)
{
for (j=0; j<7; j++)
{
if (rest[i][j] == -1)
return;
if (rest[i][j] != list[i])
continue;
if (rest[i][j] == list[i])
break;
}
}

n++;
printf("Solution: %d\n", n);
printf("赵 钱 孙 李 周 吴 陈\n");
printf("=============================================================\n");
for(i = 0; i <= m; i++)
{
switch (list[i])
{
case 1: printf("星期一 ");
break;
case 2: printf("星期二 ");
break;
case 3: printf("星期三 ");
break;
case 4: printf("星期四 ");
break;
case 5: printf("星期五 ");
break;
case 6: printf("星期六 ");
break;
case 7: printf("星期日 ");
break;
default:
break;
}
}
printf("\n\n\n");
}
else
{
for(i = k; i <= m; i++)
{
swap(&list[k], &list[i]);
perm(list, k + 1, m);
swap(&list[k], &list[i]);
}
}
}

int main()
{
int list[] = {1, 2, 3, 4, 5, 6, 7};
int i, j;
for(i = 0; i < 7; i++)
{
printf("Enter the day of %d people rests:\n", i+1);
for(j = 0; j < 7; j++)
{
scanf("%d", &rest[i][j]);
if(rest[i][j] == -1)
break;
}
}
printf("\n\n\n");
perm(list, 0, 6);
printf("total:%d\n", n);
getchar();
getchar();
return 0;
}

使用方法：首先输入每个人希望休息的日期，以-1结束。比如赵休息2，4，则输入：2回车4回车-1回车。输入完7人希望休息的日期后自动排班。
希望对你有所帮助。