目前流行地几种排课算法地介绍.doc

:设要安排的课程为{C1,C2,.,Cn},课程总数为n,而各门课程每周安排次数(每次为连续的2学时>为{N1,N2,.,Nn}。每周教案日共5天,即星期一~星期五。每个教案日最多安排4次课程教案,即1~2节、3~4节、5~6节和7~8节(以下分别称第1、2、3、4时间段>.在这种假设下,显然每周的教案总时间段数为5×4=20,并存在以下约束关系:b5E2RGbCAP n≤20,(1> N=6n,i=1,Ni≤20.(2>自动排课问题是:设计适当的数据结构和算法,以确定{C1,C2,.,Cn}中每个课程的教案应占据的时间段,,分配2个字节的“时间段分配字”(无符号整数>:{T1,T2,.,Tn}.其中任何一个时间段分配字(假设为Ti>都具有如下格式:DXDiTa9E3dTi的数据类型C语言格式定义为:,0表示有效,1表示无效(如停课等>。其它各位称为课程分配位,每个课程分配位占连续的3个位(bit>,表示某教案日(星期一~星期五>安排该课程的时间段的值,0表示当日未安排,1~4表示所安排的相应的时间段(超过4的值无效>.RTCrpUDGiT在这种设计下,有效的时间段分配字的值应小于32768(十六进制8000>,而大于等于32768的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此>,因此很容易实现停课/,自动排课算法的目标就是确定{C1,C2,.,Cn}所对应的{T1,T2,.,Tn}.jLBHrnAILg从安排的可能性上看,共有20!/(20-N>!种排法(N的含义见(2>式>.如果有4门课,每门课一周上2次,则N=8,这8次课可能的安排方法就会有20!/(20-8>!=5079110400,,:从星期一第1时间段开始按{C1,C2,.,Cn}中所列顺序安排完各门课程之后(每门课安排1次>,再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合{N1,N2,.,Nn}{C[1],C[2],.,C[n]}表示{C1,C2,.,Cn},对{N1,N2,.,Nn}xHAQX74J0X和{T1,T2,.,Tn} 排课算法输入{C1,C2,.,Cn}、{N1,N2,.,Nn}.输出{T1,T2,.,Tn}.①初始化: 星期值week=1 时间段值segment=1 {T[1],T[2],.,T[n]}中各时间段分配字清零②新一轮扫描课程: 置继续处理标志flag=0 对课程索引值c-index=1,2,.,n进行以下操作: 如果N[c-index]>0,则做以下操作: 把segment的值写入T[c-index]的第(week-1>33~week33-1位中 N[c-index]的值减1LDAYtRyKfE 如果N[c-index]>0,则置flag=1 如果week=5并且segment=4 则:置flag=1并转③否则:如果segment=4 则:置segment=1且week增1 否则:segment增1 检测是否已全部安排完毕: 如果flag=1 则:转②否则:转③③检测是否成功: 如果flag=1 则:开课次数过多否则:课程安排成功④算法结束显然,本算法的时间复杂度为O(N>(N为每周总开课次数,见(2>式>,而存储时间段分配字所用空间为2n个字节(n为课程门数>.,需要人工调整某些课程的安排时间,如把第i门课程在人工干预下改成星期数为week、时间段为segment的位置,则根据上述数据结构需做如下运算:dvzfvkwMI1 T[i]=T[i]&(~(7<<(week-1>*3>>+(segment<<(week-1>*3>,rqyn14ZNXI其中&、~和n分别为按位与、按位取反和按位左移运算符(下同>.[1],则该问题描述为:判断时间段分配字T[1]与{T[2],T[3],.,T[n]}中的某个分配字是否存在相同课程分配位上的相等的非零时间段值,或者说{T[2],T[3],.,T[n]}中是否存在与T[1],在以下算法描述中假设所