CSP.rar_csp

#include <stdio.h> #include <stdlib.h> #include <memory> struct Course { unsigned char teacher; unsigned char classlist; unsigned char classroom; unsigned char time; }; int many(unsigned char bit) { int i = 0; while(bit > 0) { if(bit%2 > 0) i++; bit = bit/2; } return i; } unsigned char timetable(unsigned char time) { unsigned char temp = time; unsigned char result = 0; int i = 0; int counter = 0; while(counter < 5) { if(temp%2 == 0) { i++; result = result | (1<<counter); } temp = temp/2; counter++; if(i == 2) return result; } return 0; } main() { Course course[3]; int i,j; for(i = 0; i < 3; i++) memset(&course[i],0,sizeof(Course)); // memset(&course1,0,sizeof(Course)); // memset(&course2,0,sizeof(Course)); // memset(&course3,0,sizeof(Course)); course[1].teacher = 0x01;//任课教师编号为1 course[1].classlist = 0x01;//所教班级编号为1 course[0].teacher = 0x06;//任课教师编号为2、3 course[0].classlist = 0x03;//所教班级编号为1、2 course[2].teacher = 0x04;//任课教师编号为3 course[2].classlist = 0x04;//所教班级编号为3 for(i = 0; i < 3; i++)//从排课任务中取出排课任务，有限挑选约束条件多的排课任务 { j = many(course[i].classlist);//所需要教室数量 if(j == 1) { //获得教室 for(int k = 0; k < 3; k++) { unsigned char temp = 1<<k; course[i].classroom = temp; unsigned char time = 0; for(int r = 0; r < 3; r++) { if(r != i)//判断约束条件 { if((course[r].teacher&course[i].teacher)!=0 || (course[r].classroom &course[i].classroom)!=0 ||(course[r].classlist&course[i].classlist)!=0) time = time | course[r].time; } } if(timetable(time) != 0)//是否还有剩余的时间片 { course[i].time = timetable(time); goto OK; } course[i].classroom = 0; } printf("无解\n"); exit(1); } else if(j == 2) { for(int k = 0; k < 3; k++) for(int l = k+1; l < 3; l++) { unsigned char temp = (1<<k)|(1<<l); course[i].classroom = temp; unsigned char time = 0; for(int r = 0; r < 3; r++) { if(r != i) { if((course[r].teacher&course[i].teacher)!=0 || (course[r].classroom &course[i].classroom)!=0 ||(course[r].classlist&course[i].classlist)!=0) time = time | course[r].time; } } if(timetable(time) != 0) { course[i].time = timetable(time); goto OK; } course[i].classroom = 0; } printf("无解\n"); exit(1); } OK:; } // printf("%d\t%d\t%d\t%d\n",course1.teacher,course1.classlist,course1.classroom,course1.time); for(i = 0; i < 5; i++) { for(j = 0; j < 3; j++) { if((course[j].time&(1<<i)) != 0) printf("time%d\tcourse%d class%d classroom%d\t",i,j,course[j].classlist,course[j].classroom); printf("\n"); } } return 0; }