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=0i<7i++)
{
for (j=0j<7j++)
{
if (rest[i][j] == 0)
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 = 0i <= mi++)
{
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 = ki <= mi++)
{
swap(&list[k], &list[i])
perm(list, k + 1, m)
swap(&list[k], &list[i])
}
}
}
int main()
{
printf("\n")
printf("注意:\n")
printf("1.请按钱、赵、孙、李、周、吴、陈的顺序输入休息每个人的时间。\n")
printf("2.输入星期时,请直接输入数字,如要输入'星期一',就用'1'代替,以此类推。\n")
printf("3.星期与星期之间用空格隔开,每输入完一个人的休息日,在其后输入0,再按回车继续下一人。\n")
printf("\n")
int list[] = {1, 2, 3, 4, 5, 6, 7}
int i, j
for(i = 0i <7i++)
{
printf("请输入第 %d 个人的休息时间:\n", i+1)
for(j = 0j <7j++)
{
scanf("%d", &rest[i][j])
if(rest[i][j] == 0)
break
}
}
printf("\n\n\n")
perm(list, 0, 6)
getchar()
getchar()
printf("输出完毕,按回车键结束!\n")
return 0
}
我先说说思路:用一个7*7的二维数组pb存储一周中每天是谁休息,数组行标0-6表示人员(钱-陈),列标0-6表示星期(日-六),初始值存储为每人的休息日意愿,比如钱想休息周一、六,即置pb[0][1]和pb[0][6]为1,其余为0(表示不情愿休息),依次类推,初始化其他人员的休息意愿。接下来就对这个数组中为1的元素进行筛选修改,比如将pb[i][j]=1改为pb[i][j]=2,即表示让人员i在星期j休息,当然人员i不能又在其它天休息了,其他人员也不能在星期j这天休息了,也就是i行、j列都只能有一个为2的值,经过7次设置,即可得到一种方案。可以考虑用递归算法实现。
#include <stdio.h>#include <conio.h>
#define T 7 //排班周期
#define N 7 //人员数目
#define X 1 //每人每周期可以休息X天,X<T
#define Y 1 //每天最多可以有Y人休息,Y>=N*X/T
int total=0
void Print(int pb[][T]){
int i,j
printf("\nXiuXi FangAn %d:\n",++total)
for(i=0i<N++i){
printf("%d:",i)
for(j=0j<T++j){
if(pb[i][j]==2)printf("%d ",j)
}
printf("\n")
}
getch()
}
int KeXing(int pb[][T],int k,int j){//检验k人员在j日期休息是否可行
int s=0,i
for(i=0i<T++i)s+=(pb[k][i]==2)
if(s>X)return 0
for(s=0,i=0i<N++i)s+=(pb[i][j]==2)
if(s>Y)return 0
return 1
}
void PaiBan(int pb[][T],int k){//给第k位人员安排休息日
int i,j
for(j=0j<T++j){
if(pb[k][j]==1){//k人员愿意在j日期休息
pb[k][j]=2
if(KeXing(pb,k,j)){
if(k==N-1){//找到一个方案
Print(pb)//输出休息方案
}else{
PaiBan(pb,k+1)
}
}
pb[k][j]=1//准备更换下一个休息意愿日测试
}
}
}
int main(){
int i,j,pb[N][T]={0}
printf("====PaiBan XiTong====\n")
printf("XiuXi YiYuan i,j( RenYuan i=0~%d, RiQi j=0~%d, JieShu -1,-1 ):\n",N-1,T-1)
do{
scanf("%d,%d",&i,&j)
if(i>=0&&i<N&&j>=0&&j<T){
pb[i][j]=1
}else{
break
}
}while(1)
PaiBan(pb,0)
printf("\nGong You %d Zu FangAn.",total)
printf("\nFinished!\n")
getch()
return 0
}
根据你的休息意愿设置,可以得到4中方案。
给你个c++版本做参考:#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
int main(int argc,char *argv[])
{
std::vector<int>arr[7]
std::vector<std::vector<int>>resolution
for(int i=0i!=7++i)
{
int temp
std::cout<<"please input number "<<i+1
<<" person's all rest days he wanted(1-7):\n"
while(std::cin.peek()!='\n')
{
std::cin>>temp
arr[i].push_back(temp)
}
::getchar()
}
int arr1[]={1,2,3,4,5,6,7}
do
{
for(int i=0i!=7++i)
{
std::vector<int>::iterator iter=
std::find(arr[i].begin(),arr[i].end(),arr1[i])
if(iter==arr[i].end())
{
break
}
if(i==6)
{
std::vector<int>temp(arr1,arr1+7)
resolution.push_back(temp)
}
}
}while(std::next_permutation(arr1,arr1+7))
size_t cnt=resolution.size()
std::cout<<"可用的方案如下,按职员A-G的休息日排列:\n"
for(int i=0i!=cnt++i)
{
size_t temp=resolution[i].size()
std::cout<<"方案 "<<i+1<<":\n"
for(int j=0j!=temp++j)
std::cout<<resolution[i][j]<<" "
std::cout<<"\n"
}
::system("pause")
return 0
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)