排日程问题，某保密单位机要人员 A，B，C，D，E 每周需要工作5天，休息2天。

Question

某保密单位机要人员 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的作息时间表。
多个矩阵间用空行分隔开。
例如，如下的矩阵就是一个合格的解。请编程输出所有解(多个解的前后顺序不重要)。
01101111101110
0110111
1101110
1110110
用C语言编写

Answer 1

// 某保密单位机要人员 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
// 用C语言编写
#include "stdlib.h"
int getOnes( int val )
{
int counts = 0;
int i = 0;
for( i = 0 ; i < 8*sizeof(val) ; i++ ){
counts += ((1<<i)&val)>0?1:0;
}
return counts;
}
void printSchedule( char* info, int schedule, int size )
{
int i;
printf("%s: %02X (", info,schedule );
for(i = size*8-1; i >= 0 ; --i){
printf("%d", ((1<<i)&schedule)>0?1:0 );
}
printf(")\n");
}
void printResult( unsigned char schedule )
{
int i;
for(i = 6; i >= 0 ; --i){
printf("%d", ((1<<i)&schedule)>0?1:0 );
}
printf("\n");
}
int main(int argc, char const *argv[])
{
// result
int schedule_a = 0;
int schedule_b = 0;
int schedule_c = 0;
int schedule_d = 0;
int schedule_e = 0;
// possible schedules
unsigned char pos_schedules[0xFF] = {0};
int pos_schedules_count = 0;
int free_day_one = 0;
int free_day_two = 0;
unsigned char schedule;
// rule 1
unsigned short rule_1 = 0x000F;
unsigned short rule_1_checker = 0;
unsigned short rule_1_result = 0;
// rule 2
unsigned char rule_2 = 0;
// rule 3
unsigned char rule_3 = 0;
unsigned char rule_3_result = 0;
// rule 4
unsigned char rule_4 = 0;
// rule 5
unsigned char rule_5 = 0;
// rule 5
unsigned char rule_6 = 0;
// helpers
int i;
int total_schedules = 0;
// search for the possible schedules
for(free_day_one = 0; free_day_one < 7; ++free_day_one){
for(free_day_two = free_day_one; free_day_two < 7; ++free_day_two){
// rule 0, 每周需要工作5天，休息2天
if( free_day_one != free_day_two ){
// get a schedule
schedule = (~(1<<free_day_one)) & (~(1<<free_day_two)) & 0x7F;
// rule 1, 所有人的连续工作日不能多于3天
// （注意：周日连到下周一也是连续）
// expand schedule 7 days (8 bits) to 14 days ( 16 bits )
rule_1_checker = schedule;
rule_1_checker <<= 7;
rule_1_checker |= schedule;
rule_1 = 0x000F;
rule_1_result = 1;
for(i = 0; i < 14-3; ++i){
rule_1_result = rule_1_result
&& ((rule_1_checker&rule_1)!=rule_1);
rule_1 <<= 1;
}
if( rule_1_result ){
pos_schedules[pos_schedules_count++] = schedule;
// printSchedule("schedule",schedule,sizeof(schedule) );
// printf("day1:%d day2:%d\n", free_day_one,free_day_two);
}
}
}
}
// get candler
for (schedule_a = 0; schedule_a < pos_schedules_count; ++schedule_a){
for (schedule_b = 0; schedule_b < pos_schedules_count; ++schedule_b){
for (schedule_c = 0; schedule_c < pos_schedules_count; ++schedule_c){
for (schedule_d = 0; schedule_d < pos_schedules_count; ++schedule_d){
for (schedule_e = 0; schedule_e < pos_schedules_count; ++schedule_e){
// rule 2, 一周中，至少有3天所有人都是上班的。
rule_2 = pos_schedules[schedule_a] &
pos_schedules[schedule_b] &
pos_schedules[schedule_c] &
pos_schedules[schedule_d] &
pos_schedules[schedule_e] ;
if( getOnes(rule_2) < 3 ){
continue;
}
// rule 3, 任何一天，必须保证 A B C D 中至少有2人上班。
rule_3_result = 1;
for (i = 0; i < 7; ++i){
rule_3 = (pos_schedules[schedule_a]&(1<<i))>0?1:0;
rule_3 <<= 1;
rule_3 |= (pos_schedules[schedule_b]&(1<<i))>0?1:0;
rule_3 <<= 1;
rule_3 |= (pos_schedules[schedule_c]&(1<<i))>0?1:0;
rule_3 <<= 1;
rule_3 |= (pos_schedules[schedule_d]&(1<<i))>0?1:0;
rule_3_result = rule_3_result && (getOnes(rule_3)>=2);
}
if( ! rule_3_result ){
continue;
}
// rule 4, B D E 在周日那天必须休息。
rule_4 = 1;
rule_4 = rule_4 && ((pos_schedules[schedule_b]&0x01)==0);
rule_4 = rule_4 && ((pos_schedules[schedule_d]&0x01)==0);
rule_4 = rule_4 && ((pos_schedules[schedule_e]&0x01)==0);
if ( ! rule_4 ){
continue;
}
// rule 5, A E 周三必须上班。
rule_5 = 1;
rule_5 = rule_5 && ((pos_schedules[schedule_a]&0x10)>0);
rule_5 = rule_5 && ((pos_schedules[schedule_e]&0x10)>0);
if ( ! rule_5 ){
continue;
}
// rule 6, A C 一周中必须至少有4天能见面（即同时上班）。
rule_6 = pos_schedules[schedule_a] & pos_schedules[schedule_c];
if( getOnes(rule_6) < 4 ){
continue;
}

// passed all rules
// printf("result\n");
// printSchedule("schedule_a",pos_schedules[schedule_a],
// sizeof(pos_schedules[schedule_a]) );
// printSchedule("schedule_b",pos_schedules[schedule_b],
// sizeof(pos_schedules[schedule_b]) );
// printSchedule("schedule_c",pos_schedules[schedule_c],
// sizeof(pos_schedules[schedule_c]) );
// printSchedule("schedule_d",pos_schedules[schedule_d],
// sizeof(pos_schedules[schedule_d]) );
// printSchedule("schedule_e",pos_schedules[schedule_e],
// sizeof(pos_schedules[schedule_e]) );

printResult(pos_schedules[schedule_a]);
printResult(pos_schedules[schedule_b]);
printResult(pos_schedules[schedule_c]);
printResult(pos_schedules[schedule_d]);
printResult(pos_schedules[schedule_e]);
printf("\n");

total_schedules++;
} } } } }
// printf("total counts %d\n", total_schedules);
return 0;
}