排班問題演算法

⑴ 題目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人希望休息的日期後自動排班。
希望對你有所幫助。