课程设计用c设计一个排课程序

教务处排课系统建模精编W O R D版IBM system office room 【A0816H-A0912AAAHH-GX8Q8-GNTHHJ8】教务处排课系统建模摘要：为解决教务处排课系统选课问题，通过对问题的分析，设计解决问题的主要数据结构，再设计出算法程序，从时间、教师、周开课次数、冲突检测及解决等方面处理排课问题。

关键词：排课系统，数据结构，算法，冲突检测，建模。

每年开学时需要选课，有时排课系统会出现各种各样的问题，一部分是因为排课系统本身的算法问题。

设计一个合理算法对于学生选课方便至关重要，以下是一个排课系统的介绍。

1.排课系统的基本要求：1.必修课尽可能的排在上午；例如，数学、英语、专业课等安排在上午，而体育、计算机、实验等安排在下午。

2.一个教师如果上午连续上四节课，尽可能的将四节课都安排在一个教室；3.一周上多次的课程尽可能间隔至少一天，比如高数，如果一周上六节课，则尽可能安排周1、3、5上午上课；因此同一节的课程一周最多上六节课，且只能在周一、周三、周五。

4.同一专业的课程不能有冲突。

2. 问题的描述：根据排课的优先级，应该先将全校各个专业本学期的专业课安排好，再考虑教师的教学问题，即如果某一个教师某天上午或下午连续教四节课，确保后一节课的教室号与前一节相同。

判断同一课程一周上几次，一次则可以在五天中无课程的时间中随机抽取一天安排课程，两次则可以分为周一和周三、周二和周四、周三和周五三周时间来排课，三次则只能是周一、周三、周五一种排课时间。

3.基本算法的描述：设要安排的课程为{ C1 , C2 , ., Cn} ,课程总数为n , 而各门课程每周安排次数为{ N1 , N2 , ., Nn} ;每周教学日共5 天,即星期一～至星期五;每个教学日最多安排4 次课程教学,即1 ～ 2 节、3 ～ 4 节、5 ～ 6 节和7 ～ 8 节(以下分别称第1 、2 、3 、4 时间段) . 在这种假设下,显然每周的教学总时间段数为5 ×4 = 20 ,并存在以下约束关系: n ≤20 (1)N = 6n， i =1， Ni ≤20 (2)自动排课问题是:设计适当的数据结构和算法, 以确定{ C1 , C2 , ……, Cn } 中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.4. 主要数据结构对于每一门课程,分配2 个字节的“时间段分配字”(无符号整数) :{ T1 , T2 , ., Tn} . 其中任何一个时间段分配字(假设为Ti ) 都具有如下格式:Ti 的数据类型C为:unsigned int 。

《⾯向对象程序设计》课程设计教学⼤纲设计《⾯向对象程序设计》课程设计教学⼤纲适⽤专业：计算机科学与技术课程周数：2周⼀、⼤纲说明本⼤纲根据计算机科学与技术专业⼈才培养⽅案制订。

（⼀）课程设计性质课程设计是学⽣对课程所学知识的综合运⽤，它与课堂听讲、上机实验、课外练习、⾃学研究相辅相成，构成⼀个完整的课程教学体系。

（⼆）主要先修课程和后续课程1.先修课程：《C语⾔程序设计》2.后续课程：《Java程序设计》、《软件⼯程》⼆、课程设计⽬的及基本要求本课程全⾯系统的学习⾯向对象程序设计的基本概念，基本语法和编程⽅法。

正确理解掌握C++⾯向对象程序设计的基本特性：类，对象，继承与派⽣，多态，虚函数，模板，流类库等。

遵循软件过程的各个环节进⾏系统分析、设计、实现、集成、测试，并相应给出软件规格说明书等制品，了解当前常⽤的软件开发⼯具(Visual C++)，要求熟练掌握基于Win32 Console Application的程序设计，培养解决实际问题的能⼒。

三、课程设计容及安排1、有理数运算问题描述：有理数是⼀个可以化为⼀个分数的数，例如2/3，533/920，-12/49都是有理数，⽽就为⽆理数。

在C++中，并没有预先定义有理数，需要时可以定义⼀个有理数类，将有理数的分⼦和分母分别存放在两个整型变量中。

对有理数的各种操作都可以⽤重载运算符来实现。

基本要求：定义并实现⼀个有理数类，通过重载运算符+、-、*、/对有理数进⾏算术运算，通过重载运算符==实现判定两个有理数是否相等。

写⼀个优化函数，它的作⽤是使有理数约去公分母，也即是使保存的有理数分⼦和分母之间没有公约数（除去1以外）。

此外，还要定义⼀个将有理数转换为实数的函数，再加上构造函数和有理数输出函数。

测试数据：在应⽤程序中，创建若⼲有理数对象，通过带参数的构造函数使得各有理数对象值各不相同，然后分别进⾏各类运算，输出运算结果，检验其正确性。

实现提⽰：设有两个有理数a/b和c/d，则有：（1）有理数相加分⼦=a*d+b*c；分母=b*d（2）有理数相减分⼦=a*d-b*c；分母=b*d（3）有理数相乘分⼦=a*c；分母=b*d（4）有理数相除分⼦=a*d；分母=b*c优化函数在创建有理数对象时应执⾏，在执⾏其它各种运算之后也需执⾏它，这样可保证所存储的有理数随时都是最优的。

UML教务管理系统的课程设计一、引言在现代教育环境中，高效的教务管理系统是学校管理和教学工作的重要组成部分。

教务管理系统能够帮助学校管理课程、学生、教师等信息，提供学生选课、成绩查询、教师排课等功能，提高管理效率和教学质量。

本文针对这一问题，设计了一种基于UML的教务管理系统。

二、需求分析2.1 功能需求教务管理系统需要实现以下功能： 1. 学生管理：包括学生信息管理、学生选课、学生成绩查询等功能。

2. 教师管理：包括教师信息管理、课程安排、成绩录入等功能。

3. 课程管理：包括课程信息管理、课程安排、课程评价等功能。

4. 系统管理：包括用户权限管理、系统配置、日志管理等功能。

2.2 非功能需求教务管理系统还需要满足以下非功能需求： 1. 可靠性：系统应具有高可靠性，保证数据的完整性和一致性。

2. 安全性：系统应提供安全的用户认证和授权机制，保证数据的安全性。

3. 可扩展性：系统应具有良好的可扩展性，能够方便地扩展新的功能和模块。

4. 用户友好性：系统应具有良好的用户交互界面，易于使用。

三、系统设计3.1 概要设计教务管理系统的概要设计主要包括系统的整体架构和模块划分。

在整体架构上，可以采用三层架构，即表现层、业务逻辑层和数据访问层。

在模块划分上，可以包括学生管理模块、教师管理模块、课程管理模块和系统管理模块。

3.2 详细设计3.2.1 学生管理模块学生管理模块主要包括以下功能： - 学生信息管理：包括学生基本信息的录入、修改和查询等功能。

- 学生选课：包括学生选课的操作和选课结果的查询功能。

- 学生成绩查询：包括学生查询已修课程成绩的功能。

3.2.2 教师管理模块教师管理模块主要包括以下功能： - 教师信息管理：包括教师基本信息的录入、修改和查询等功能。

- 课程安排：包括教师课程的安排和修改等功能。

- 成绩录入：包括教师录入学生成绩等功能。

3.2.3 课程管理模块课程管理模块主要包括以下功能： - 课程信息管理：包括课程基本信息的录入、修改和查询等功能。

学生选课系统c 课程设计一、教学目标本课程旨在让学生掌握学生选课系统C的基本原理和使用方法。

知识目标包括了解学生选课系统的功能、结构和常用技术，理解面向对象设计的基本概念和方法。

技能目标包括能够使用学生选课系统C进行课程选择和排课，能够进行简单的系统设计和优化。

情感态度价值观目标包括培养学生对编程和计算机科学的兴趣和热情，提高学生解决问题的能力和创新精神。

二、教学内容本课程的教学内容主要包括学生选课系统C的基本原理、系统结构和常用技术，面向对象设计的基本概念和方法，以及学生选课系统C的实践应用。

具体包括以下几个部分：1.学生选课系统C的基本原理：介绍学生选课系统C的定义、功能和特点，让学生了解学生选课系统C的基本概念。

2.学生选课系统C的系统结构：讲解学生选课系统C的组成部分，包括数据库、服务器和客户端等，让学生了解学生选课系统C的架构和运行机制。

3.学生选课系统C的常用技术：介绍学生选课系统C中常用的技术，如SQL、Java等，让学生掌握学生选课系统C的开发和实现方法。

4.面向对象设计的基本概念和方法：讲解面向对象设计的基本原则和方法，如封装、继承和多态等，让学生掌握面向对象设计的思维方式和实际应用。

5.学生选课系统C的实践应用：通过实际操作，让学生学会使用学生选课系统C进行课程选择和排课，培养学生的实际操作能力。

三、教学方法为了提高教学效果，本课程将采用多种教学方法相结合的方式进行教学。

包括：1.讲授法：通过讲解学生选课系统C的基本原理、系统结构和常用技术，让学生掌握基本概念和知识。

2.讨论法：通过学生进行小组讨论，引导学生思考和探讨学生选课系统C的实际应用问题和解决方案。

3.案例分析法：通过分析典型案例，让学生了解学生选课系统C的实际应用场景和设计方法。

4.实验法：通过实际操作，让学生学会使用学生选课系统C进行课程选择和排课，培养学生的实际操作能力。

四、教学资源为了支持本课程的教学，我们将准备以下教学资源：1.教材：选择合适的教材，为学生提供系统的学习资料。

c++-顺序结构程序设计
C++是一种功能强大的编程语言，它支持顺序结构程序设计，这
意味着程序按照代码的顺序逐行执行。

在C++中，顺序结构程序设
计是基本的编程范例之一，它允许程序员按照自己的意愿编写代码，从而实现所需的功能。

顺序结构程序设计的关键在于控制程序的执行顺序。

当编写
C++程序时，我们可以按照自己的需求定义变量、执行算术运算、调
用函数等。

这些操作将按照代码的书写顺序依次执行，每一步的结
果都会影响到下一步的执行。

在实际的C++编程中，我们可以利用顺序结构来解决各种问题。

例如，我们可以编写一个简单的程序来计算两个数的和，首先定义
两个变量存储这两个数，然后进行加法运算，最后输出结果。

这个
过程就是一个典型的顺序结构程序设计的例子。

另外，顺序结构程序设计也可以与其他控制结构相结合，比如
条件语句和循环语句，从而实现更加复杂的功能。

这些结构可以帮
助我们根据不同的情况选择不同的执行路径或者重复执行某段代码，从而增强程序的灵活性和功能性。

总之，顺序结构程序设计是C++编程中的基础，它允许程序员按照自己的意愿编写代码，自由地控制程序的执行顺序，从而实现各种不同的功能。

掌握好顺序结构程序设计对于学习和应用C++编程语言都是非常重要的。

《高校教务管理系统》需求调研报告目录1 引言................................... 错误!未定义书签。

编写目的......................... 错误!未定义书签。

背景说明......................... 错误!未定义书签。

系统目标......................... 错误!未定义书签。

2 需求描述............................... 错误!未定义书签。

教学资源维护..................... 错误!未定义书签。

学年校历编排........................ 错误!未定义书签。

组织结构维护....................... 错误!未定义书签。

教室资源维护....................... 错误!未定义书签。

学籍维护......................... 错误!未定义书签。

学生基本信息维护................... 错误!未定义书签。

成绩信息........................... 错误!未定义书签。

考勤信息维护........................ 错误!未定义书签。

教学计划维护..................... 错误!未定义书签。

开课 /排课维护................... 错误!未定义书签。

开课管理：......................... 错误!未定义书签。

排课管理：......................... 错误!未定义书签。

选课管理......................... 错误!未定义书签。

学生网上选课平台（B/S结构）........ 错误!未定义书签。

教务员管理平台（C/S结构）：......... 错误!未定义书签。

考务管理维护（暂定）............. 错误!未定义书签。

机电技术 2012年12月172《C语言程序设计》教学改革的研究*冯 林 付志坚(东华理工大学,江西抚州 344000)摘 要:就如何提高C语言程序设计课程的教学质量,激发大学生在C语言教学中的兴趣,熟练掌握教学内容,开拓大学生的创新意识,文章从教学思想､教学内容､教学模式､教学方法､考核方式等几方面探究了C语言教学改革。

关键词:C语言;编程能力;教学方法;教学质量;教学改革中图分类号:TP312文献标识码:A 文章编号:1672-4801(2012)06-172-03C语言是贝尔实验室的Dennis Ritchie 在B 语言的基础上开发出来的,并逐渐被用于UNIX操作系统的系统软件和应用软件的开发。

不少高校不仅在计算机专业开设了C语言的课程,而且在非计算机专业也开设了C语言课程。

但是由于授课对象都是初次接触程序设计的大学低年级学生,大一上学期开设《大学计算机基础》,下学期就接着开设《C语言程序设计》。

在每学期都要召开期中教学质量检查座谈会上,了解到同一年级不同专业的大部分学生都认为C语言比较难。

根据多年的教学经验,本文分析问题存在的原因,从几个方面探究了改善C语言教学效果的方法,并通过改革取得了一定成效。

1 教学思想的改革传统的教育思想是以知识传承为中心,自然而然培养出的人才大多欠缺研究能力和创新能力,难以适应21世纪社会的需求。

在教学过程中,许多同学经常问:我学了以后到底有什么用呢?会不会过时呢?所以明确学习目的,培养学习兴趣,培养独立思考问题是头等要事,教师在第一堂课上要花一点时间说一说C语言的重要性:1)目前市场上各类工业及民用电子产品和测控系统及测试设备的基础设计与开发多以C/C++､Visual C++语言为工具。

2)DBASEⅢPLUS､DBASEⅣ､PC-DOS､UNIX操作系统､WORDSTAR､各类游戏软件､数据库､聊天室,编制PHOTOSHOP､FLASH､3DMAX等图像设计软件都采用C语言编写。

学校课程表制定流程一、需求收集与调研制定学校课程表的第一步是进行需求收集与调研。

教师、学生和家长的反馈和意见是决策的重要参考。

学校可以通过开展问卷调查、座谈会等形式，了解各方对课程安排的期望和需求。

二、课程设计与目标设定根据需求调研的结果，学校开始进行课程设计与目标设定。

根据教育部的课程标准，学校可以确定每个年级的课程要求和学习目标。

同时，学校还需考虑学生的兴趣爱好、发展需求以及学科的发展方向，合理安排各门学科的学习内容和难度。

三、教师资源评估学校在制定课程表时需要评估并调配教师资源。

根据教师的学科专长和教学能力，学校可以确定各门课程的教师编制和配置情况。

此外，学校还需考虑教师的工作负荷和师资培养等问题，以确保每门课程都能得到良好的教学保障。

四、时间安排与分配时间安排是课程表制定的重要环节。

学校需要确定每天上课的时间段和每节课的时长。

这涉及到课程的紧凑程度、学生的体力状况以及各门学科的学习特点等因素。

学校可以根据不同年级和学科的需要，采取不同的时间安排和分配策略。

五、课程组织与排课在课程表制定的过程中，学校还需要进行课程组织与排课工作。

根据课程的性质和要求，学校可以确定每门课程的课时数和上课频率。

此外，学校还需考虑课程之间的关联性和顺序，合理安排课程的先后顺序和节奏，以提高学生的学习效果。

六、选修课程及时间分配除了必修课程，学校还需要考虑选修课程的设置和时间分配。

选修课程可以提供学生个性化发展和兴趣培养的机会。

学校可以根据学生的需求和专长，设置不同类型的选修课程，并合理安排选修课程的时间和学时。

七、教材选用与配套资源在制定课程表的过程中，学校还需要进行教材选用与配套资源的工作。

学校可以根据教育部的教材标准和教学大纲，选择适合的教材。

同时，学校还需提供相应的教学辅助材料和资源，以丰富课堂教学内容，提高教学效果。

八、课程表的修订与更新课程表的制定并不是一次性的过程，学校还需进行定期的修订与更新。

学校可以根据学生的学习效果和学科的发展变化，及时调整课程表。

学生分层走班排课实施方案及管理制度（陈永林拟）改革背景：新的《普通高中课程方案》规定,高中生在学校除了要学习必修课程,还有总量超过必修课程的国家选修课程和一定数量的学校自主开发的校本选修课程。

学生可以根据自己喜好,选择自己喜欢的学科方向和教师,安排自己的课堂学习。

上世纪末，中共中央、国务院提出要“深化教育改革，全面推进素质教育”，新课改的目的就是要在21世纪构建起符合素质教育要求的基础教育课程体系。

由于高中教育已经基本普及，高中教育的功能也随之发生了变化：从只面向少数人的精英教育，转变为面向全体学生的大众教育，高中教育的目的和任务不再是只为大学输送合格新生。

当高中毕业生可能继续升学，也可能直接走向社会时，高中教育就应当转变为培养学生的“人生规划”能力、职业意识和创业精神，这些正是新课改所十分强调的。

一、分层走班制界定:学生根据自己已有的知识基础以及对各科的学习能力、兴趣、潜质和未来发展方向，分学科去对应层次班级上课的学习模式，传统行政班保持不变。

二、分层走班学习的优点：1. 学生主体地位彰显。

实行“走班制”后，任课教师按照学生的学习基础和接受能力、兴趣特长，确定教学活动。

学生也可有的放矢地选择、安排自己的课程结构，学会如何正确评价自己，正确估计自己的能力，并逐渐找到将来发展的方向。

2. 充分调动学生学习的主动性。

走班制学习组织方式充分赋予学生的主体地位，克服了传统的班级授课制度几百名学生读同一本书，上同样的课，做同样的练习，忽略学生自身成长中发展的差异性和不平衡性等缺陷，最大限度地让不同兴趣爱好、不同学习基础、不同学习能力的学生获得与自己最相适宜的发展环境。

3. 学生的自信心得以提升。

“走班制”学习组织方式条件下，学生按自己的学习水平，自我发展的需要，自身的兴趣、特长选班，能增强其自信心和成就感，尝试到成功的快乐，减轻了思想压力，始终保持乐观的情绪和平衡的心态，从而都能获得不同程度的发展。

4. 扩大了学生的交往范围，加大了同学间的相互影响，有利于增强同一层次学生之间的竞争意识和合作意识。

基于智能算法的校园自动化排课系统设计与实现校园自动化排课系统是一种基于智能算法的新一代教育管理工具，旨在帮助学校高效、准确地进行课程排定。

本文将介绍校园自动化排课系统的设计与实现，以及其所采用的智能算法。

一、系统设计1.需求分析在设计校园自动化排课系统之前，我们需要先进行需求分析。

该系统需要具备以下功能：- 自动识别学校的教学资源和班级数目，并能够根据学校的教学大纲自动生成课程表；- 能够考虑到师资的合理利用，根据教师的特长和排课偏好，分配教师给不同的班级和课程；- 能够处理课程冲突，避免同一时间段内安排了两门课；- 能够根据学生的选修课情况，合理调配教室和时间资源；- 提供灵活的排课参数设置，如考虑到体育课的时间、上课时间段的设置等等。

2.系统架构校园自动化排课系统的架构分为前端和后端两部分。

前端主要负责用户交互和展示，后端负责算法实现和数据处理。

前端采用现代化的Web技术，如HTML、CSS和JavaScript，以实现用户友好的界面；后端使用Java语言开发，并引入各种智能算法实现排课功能。

3.智能算法选择校园自动化排课系统需要选择适当的智能算法来进行排课。

目前，常用的智能算法包括遗传算法、模拟退火算法、禁忌搜索算法等。

在选择算法时，需要考虑到课程数量、教师和教室资源的规模以及排课的灵活性等因素。

针对不同的需求，可以选择合适的算法或者结合多种算法进行优化。

二、系统实现1.数据预处理在实现校园自动化排课系统之前，需要进行数据预处理。

这包括获取学校的教学资源、课程大纲、教师、班级和学生的信息，并进行整理和存储。

同时，也需要收集学生的选修课情况以及教师的排课偏好等额外信息。

2.算法实现基于智能算法的校园自动化排课系统的核心就是算法的实现。

以遗传算法为例，它可以通过模拟生物进化的方式，不断优化课程安排。

遗传算法主要包括初始化种群、评价种群适应度、选择优秀个体、交叉与变异等步骤。

在具体实现中，可以根据实际需求对算法进行调整和优化。

2004年3月内蒙古大学学报(自然科学版)M ar.2004第35卷第2期A cta Scientiarum N aturalium U niversitatis N ei M ongo l V o l.35N o.2 文章编号:1000-1638(2004)022*******课表的多指标数学模型及解决方法Ξ张春梅1,行　飞1,梁治安2(1.内蒙古大学理工学院,呼和浩特010021;2.上海财经大学应用数学系,上海200433)摘要:课程表问题又称时间表问题(ti m etable p roblem),是一个多指标的优化决策问题,也是组合规划中的典型问题.对已有的时间表问题进行探讨,并研究其数学模型及解决方法.关键词:时间表问题;遗传算法;多指标决策中图分类号:O221.7 文献标识码:A1　排课问题的提出 一所学校为了保证其正常的高水平教学质量,必须制定一套严密、规范的教学计划,并严格执行.课程安排在学校教学计划中又处于核心地位.合理准确的课程表对提高教学水平至关重要.2　排课问题的实质 课程表问题又称时间表问题.课表编排是一个多指标的优化决策问题,是组合规划中的典型问题.课程表的编排就是解决对时间和空间资源争夺而引起的冲突.70年代中期,S.Eveo等人论证了课表问题是N P完全类问题〔1〕,之后很多人尝试采用各种方法对此问题求解.但由于课表问题所涉及的信息较多,并且求课表问题最佳解的时间复杂性是课表规模的指数级,所以对于有一定规模的课表问题,一般采用求较佳解的算法.3　课表的数学模型及约束条件3.1　排课问题的形式化描述在课表编排问题中涉及到班级、教师、时间、课程、教室等五个相互制约的因素.分别用以下集合表示:课程集合　s={s1,s2,…,s n};时间集合　t={t1,t2,…,t n3};班级集合　c={c1,c2,…,c n1};教室集合　r={r1,r2,…,r n4};教师集合　p={p1,p2,…,p n2}时间和教室的笛卡尔积为:N=T×R={(t1,r1),(t1,r2),…(t n3,r n4)},N中的元素称为时间—教室对.课表问题的求解过程就是对任何s i=(i=1,…,n)∈S寻找一个合适的老师P j(j=1,2,…,n2)∈P和合适的时间—教室对(t1,r m)∈N(l=…n3,m=1,…n4),在安排时不能发生冲突,同时尽量满足经验常识.3.2　课表问题的冲突情况:1)同一时间,一个教师同时上一门以上课程;2)同一时间,一个班级同时上一门以上课程;3)同一时间,一个教室同时上一门以上课程;4)选课人数大于当前指定的教室的最大容量.3.3　须满足一些经验常识1)一门课在一周内分散安排,提供可引导性学习环境;2)保留一些特殊的时间,如户外活动;3)一周多学时的同一门课应尽量安排在一个教室(方便教师及学生);4)尽量安排在好的教学时间点(如上Ξ收稿日期:2003201220基金项目:国家自然科学基金资助项目(10261005);内蒙古大学青年科学基金资助项目(ND0204)作者简介:张春梅(1970～),女,内蒙古乌盟人,内蒙古大学理工学院硕士,讲师.041内蒙古大学学报(自然科学版)2004年午比下午好);5)安排到教室中的人数应尽量和教室的大小吻合,一方面资源合理利用,另外教学效果也好,因此一个好的时间表就是一个无冲突且能更多地满足经验常识的安排.4　已有的排课问题的解决方法4.1　基于人工智能原理李明〔2〕给出一个实用的大学课表编排模型,问题模型定义如下:定义1　排课表问题中基本时间表计划问题:设“可安排教学时”集H,“课程”集L( L =n L),“学生”集S( S =n S)组成小组{S i}(i=1,2,…,n l)(S=S1∪S2∪…∪S nl,S i∩S j不一定为空集),“教师”集T,对于每个学生S ij∈S i(教师t∈T),有一个“空闲时间”集A(s ij)ΑH(A(t)ΑH);对于每门课程l∈L,有一个“可安排时间”集A(l)ΑH,并且对于每一三元组(s i,t,l)∈{S i}×T×L,有一个“要求教学时间”数目R(s i,t,l)∈Z+0　(其中Z+0表示非负整数集),求完成所有课程的时间表,即求函数f:({s i}×T×L×H)→{0,1},(其中f(s i,t,l,h)=1表示学生组s i教师t在时间h内上课程l),使得:(1)仅当h∈(∩A(s ij))∩A(t)∩A(l)时,f(s i,t,l,h)=1;(2)对于每个h∈H和s i,t∈T,至多有一个l∈L满足f(s i,t,l,h)=1;(3)对于每个h∈H和s i,lt∈L,至多有一个t∈T满足f(s i,t, l,h)=1;(4)对于每个h∈H和t∈T,l∈L,至多有一个s i满足f(s i,t,l,h)=1;(5)对于每个三元组(s i,t,l)∈{S i}×T×L,恰好有R(s i,t,l)个h∈H满足f(s i,t,l,h)=1定义2　最小时间约束条件集:称定义1中条件(1)～(5)为排课表问题须满足的最小时间约束条件集.定义3　(教室)资源分配问题:设有“教室”集C,每个教室c∈C均满足一定条件A(c),且时间表已经安排好.要求:在一定的约束条件下为每个h∈H且满足f(s i,t,l,h)=1的所有三元组(s i,t,l)∈{S i}×T×L分配教室C.算法主要思想是通过引入一个规则库(知识库),来有效地处理各种复杂约束条件,并在这个规则库的指导下,搜索满足条件的时间集.由于搜索是在规则库的指导下进行的,所以称这个算法是基于智能的.安排好时间表后,进行教室资源的分配.洪力奋〔3〕等用人工智能的原理及专家系统知识构造出了类似的数学模型及有关编排算法,对排课的死锁问题进行了处理.主要设计了两个推理机,一个推理机是根据课程模式要求,根据既定规则找出合适的时间与教室.第二个推理机解决死锁问题而设置(所谓死锁即规则遍历完,仍存在时间冲突或教室冲突).4.2　利用集合的概念及其相关运算董艳云等人〔4～5〕在分析排课所遵循的基本原则和模糊性原则的基础上,定义了课元之间关于教师的相关关系和关于自然班的相关关系.提出以课元相关运算和候选时空片计算为核心的计算机排课算法,其算法描述如下:令C cou表示排课课元的集合,令T T EA,C CL A,R ROO和S SL I分别表示参与排课的教师、班级、教室和时间片的集合.此外,用C T Y={0,1,2,…}表示课元的课程类型集合,其中类型0的课元为必修课或必选课,对同一自然班,这类课的排课时间不允许与其它课冲突,其它类型的选修课按允许时间冲突的课元子集归类.1)课元的相关关系计算.假定用F T:C COU→T T EA描述课元任课教师集合,用F C:C COU→C CL A描述课元的自然班集合,则课元的相关关系定义如下:定义　课元关于教师的相关关系R T:C COU→C COU为{v} F T(u)∩F T(v)≠ (1)R T(u)=∪v∈C COU 课元关于自然班的相关关系R C:C COU→C COU为{v} F C(u)∩F C(v)≠ (2)R C(u)=∪v∈C COU式(1)和(2)中:u∈C COU,R T(u)的物理意义表示课元u的任课教师所担任的所有课程;R C(u)的物理意义表示课元u的上课班所上的所有课程.2)候选时空片计算.假定用F CT:C COU→C T Y描述课元的课程类型集合,用F CR:C COU→R T Y描述课元可选的教室类型集合,用F CS :C COU →C S I 描述课元所需的最小教室容量,用F R T :R ROO →R T Y 描述教室的类型,用F R S :R COU →R S I 描述教室容量,用F S :C COU →S SL I 表示课元已分配到的时间片集合,用F S R :C COU →S SL I ×R ROO 表示课元已分配到的时空片的集合.由排课的基本原则(1)和(2)可知,课元u ∈C COU 可选用的时间片取决于它的相关课元已分配到的时间片及课程类型,即A S (u )=S SL I -∪v ∈R T (u )F S (v )-∪v ∈R C (u )F S (v ) F CT (u )=0∨F CT (u )≠F CT (v )(3) 由排课的基本原则(3)可知,课元u ∈C COU 可选用的教室A R (u )取决于该课元所要求的教室类型和容量,即 A R (u )=∪r ∈R TRO{r } F R T (r )∈F CR (u )∧F CS c (u )ΦF RS (r )(4) 所以,课元u ∈C COU 可选用的时空片(候选时空片)A R (u )为A S R (u )=∪s ∈A s (u )r ∈A R (u )(s ,r )-∪v ∈C COU F S R (v )(5) 本算法最后通过关系数据库实现.课元数据库T EA CH .DB F ,班级数据库CLA SS .DB F ,教室数据库ROOM .DB F .按照上述排课算法及软件实现方法,已成功地开发出高校计算机排课软件.文献〔5〕提出的算法借鉴了资源管理的思想,使用以集合为元素的矩阵建立了问题的数学模型.时间模型定义如下:排课一般以一个学期作为一个独立的阶段,假定一个学期由Z 周组成(例如Z =18),每周可以使用的授课时间为S 个单位时间(如S =24),则一学期可以使用的总授课时间为N =S ×Z .这里S 和Z 可以作为系统参数.整个有效的时间域可以定义为集合K ={1,2,…,n -1,n },教师、班级和教室被占用的任何时间是K 的一个子集.算法的实现是以集合运算为基础的.该算法是动态、次优的,但时间和空间复杂性几乎和问题规模成正比.4.3　应用专家系统〔6〕文中将传统的数据库和专家系统结合起来,充分发挥各自的长处,达到优势互补的目的.系统将拥有的几方面的知识:教室、班级、课程、教师、时间等详细资料存入数据库中,将排课中的一些限制条件放入规则库中,为了便于规则的推理和编辑,所有的规则采用统一格式:对象 属性 属性值 要求 置信度对象有教师、班级、教室;教师的属性有编号、名称、职称,班级的属性有编号、年级、系别,教室的属性有编号、名称;要求包括时间或教室要求两种;置信度是一个0～1的数,等于1表示此规则是必须满足,大于0.5表示最好满足,等于0表示一定不能,小于0.5表示最好不能这样.专家系统使用排课专家的大量排课知识策略(这里的策略指把求解过程看成对一种与或图的搜索),通过查询数据库和进行规则推理,灵活的编排出符合要求的课表.4.4　分批与或图与匈牙利算法结合从前面课表的形式化描述中可看到,课表问题可看作匹配问题.其数学模型如下:把课表看成是有n 门课,怎样分配到n 个时间2教室对中的问题.需要系数矩阵,其元素c ij >0(i ,j =1,2,…,n ),表示指派第i 门课到第j 个时间2教室对时的期望值,该期望值反映教师、学生和学校根据教育的特点对该时间上某门课的观点;解题时还需引入变量x ij ,其取值只能是1或0,即x ij =1 (当指派第i 门课到第j 时间2教室对时)x ij =0 (当不指派第i 门课到第j 时间2教室对时)问题要求极小化时,数学模型为m in Z =6n i =16n j =1c ij x ij 约束条件为6n i =1x ij =1 (j =1,2,…,n );6n j =1x ij =1 (i =1,2,…,n );x ij =1或0(i ,j =1,2,…,n ) 该问题较好的解法是用匈牙利算法.该算法的主要思想是基于下面的定理:如果系数矩阵[c ij ]的每一行元素中分别减去(或加上)一个常数u i (称为该行的位势),从每一列元素中分别减去(或加上)一个常数v j (称为该列的位势),于是得到新的矩阵[b ij ],其中,第i 行第j 列141第2期张春梅等　课表的多指标数学模型及解决方法241内蒙古大学学报(自然科学版)2004年元素为b ij=c ij-u i-v j,则结果[b ij]的最优解等价于矩阵[c ij]的最优解.甘肃工业大学的魏平等人〔7〕采用分批与或图和分批优化的匈牙利算法相给合的方法实现.如把上课时间、场地、设备和连续上课时间超过两节的具有特殊要求的课程分为一批,采用搜索算法,且优先排课,然后对余下的课采用分批优化匈牙利算法和分批与或图搜索法相结合进行排课,一批中限制条件较多时采用匈牙利算法,其他采用分批与或图算法,从而提高编排效率.4.5　分组优化决策算法和定额匹配算法在课表的编排问题中,课程、时间、教室是三个相互制约的因素,1)课程定义:课程是由开课教学单位按教学任务书的要求指派讲员构成的一个教学班,课程的记录类型由下面字段定义:〈课程〉∷=〈课号〉〈课名〉〈讲员〉〈周学时〉〈人数〉〈班集合〉〈排课要求〉设L={l l-课程},L表示待排的课程任务集合.Πl1,l2∈L,若(l1〈讲员〉)=(l2〈讲员〉)或(〈班集合〉)∩(l2〈班集合〉)≠ ,称课程l1与l2相关,记作l1・l2=1,否则称无关,记作l1・l2=0.相关课程将争夺周课表上的时间.2)时间、时间模式定义　设T={t t—周课表上的时间}表示周课表上的时间集合,且若t={Ρ1,Ρ2,…,Ρn},叫做个数为n的时间组.若t中的时间个数n及Ρi在表上的时间间隔分布符合某种上课的学时机制,则称t为周学时为n的时间模板(或时间模式).下文中用t(l)表示课程的一个时间模板.若l1・l2=1,且t(l1)∩t(k2)≠ ,则称两个相关课程的时间模板冲突,记作t(l1)・t(l2)=1,否则,为不冲突,记作t(l1)・t(l2)=0.不相关课程的时间模板恒为t(l1)・t(l2)=0.3)教室、“时间教室”定义:教室的记录类型由下面字段定义:〈教室〉∷=〈教室名〉〈房间号〉〈人数〉〈功能〉.假定周课表上任何一个时间均有k个教室可供选用.即ΠΡi∈T则时间Ρi上的k个教室为r(Ρi) ={r1(Ρi),r2(Ρi),r3(Ρi),…,r k(Ρi)},用r j(Ρi)表示时间Ρi的第j个教室,通常,排课时总是先确定课程l的时间模板,再选教室,课程l的“时间教室”记为r(t(l)),其意义为:r(t(l))={r j(Ρi) Ρi∈t(l),i=1,2,…,n;n=(l〈周学时〉);r j(Ρi)∈r(Ρi)}其中t(l)为课程的合适的时间模板,并且每个r j(Ρi)均是在时间Ρi满足课程l的人数(区间)要求的某个教室.除非时间相连,且该课要求占用同一教室,否则时间教室中的r j(Ρi)与r j+1(Ρi+1)不必相同.l1,l2∈L,若t(l1)与t(l2)有相同的时间,且在这相同时间r(t(l1))与r(t(l2))存在相同的教室,则称课程的“时间教室”选择冲突,记作:r(t(l1))・r(t(l2))=1,否则为不冲突,记为r(t(l1))・r(t(l2))=0.无论l1,l2是否相关,均必须满足r(t(l1))・r(t(l2))=0.4)课程安排、课表定义:Πl∈L,选择l的不冲突时间模板(在课程相关的意义下时间模板不冲突)和分派不冲突“时间教室”,称为构造课程l的一个课表安排,记作l(l),l(l)也是记录类型:l(l)∷=〈l〉〈t(l)〉〈r(t(l))〉课程安排集合用D={l l=l(l),l∈L}表示.l1,l2∈D,l1=l(l1),l2=l(l2),在课程l1、l2相关意义下,保证t(l1)・t(l2)=0,并且还满足r(t(l1))・r(t(l2))=0,则称D为一个合适的排课集合.即D中的课程安排,两两教室必须不冲突;若课程两两相关,D中的课程安排还必须两两时间不冲突.王祜民等人〔8～9〕将课程集合中按优等级逐次分组,每组用优化决策方法排课,这是一种在启发式准则指导下,逐次的、向前的构造性排课过程.通过分组优化决策算法,先难后易逐组编排课表.那些学时多,班数多的大合班课是最难编排的课程,要先将这些课组编排到课表中去,形成称为D e的阶段课表.而定额匹配算法是解决某些特殊课程(组)的自动编排问题.所谓的特殊课,如体育课、按水平分班的外语课等,该种课程的班集合中的班数目大,因而排课难度与大合班课类似,但班级可任意组合在一起,排课时可动态挑选班组合,这使排课有更多的选择机会.4.6　作为满意约束问题处理把排课问题当作满意约束问题,对此已有多种解决方法,如图着色〔10〕,在图着色的示例中计算时间相当长,因为一旦指定的值失败就需做大量的反跟踪,原因是没有办法避开不可行解.4.7　启发式算法用启发式算法〔11〕如禁忌搜索〔12〕、模拟类似于自然界金属的退火过程的模拟退火〔13〕、类似于自然界种群遗传的遗传算法〔14,15〕;在算法的具体实现过程中,所采用的方法有用事先做好的特殊操作去产生一个可行解;也有的在适应度函数中并入惩罚;或采用修复程序过滤不可行基因;也可采取将问题中的一些约束条件消除或弱化的方法重新对问题给出表述等几种.A .co lo rn l 在高中课表的启发式算法中以特定的高中课表为例给出了模拟退火(SA )、禁忌搜索(T S )、遗传算法(GA )三种算法的比较结果〔16〕.他认为T S 是最好的算法,GA 产生的解比SA 好.但是最终用户相对于SA 和T S 更易接收GA .4.8　遗传算法意大利的A .co lo rn i 等人用遗传算法求解高中课表的安排问题〔16〕.文中将每位老师的活动作为基因,这些活动包括上课、休息、写论文等,分别用字符0、1…9、a 、b 、…p 表示.意大利高中每周上课30h ,以时间点为列,所有老师为行组成二维染色体,适应度函数定义为最小化总代价,其中组织代价指临时教学岗位没有安排老师,个人代价指不想休息时休息,教训代价指一周的几天内同一门课集中在一起;姚新的教室安排问题,主要优化的是教室的合理利用〔15〕;另日本的Sigeru .O 采用遗传算法中加入控制约束的方法解决大学课表安排问题〔14〕;用自适应的遗传算法求解大学课表安排问题〔17〕,根据大学课程安排的特点,将课程分为必修课P 、选修课Q 两类.并对两类课分别给出其染色体编码和适应度函数.在P 类课中适应度函数考虑了两点:第一点是要使所安排的课尽可能占用好的时间点,所以我们对一天的四个时段分别给出了期望值:8:00----12:00为12;10:00----12:00为8;2:00----4:00为4;4:00----6:00为1.在这种定义下我们所涉及的20个时间点的期望值如表1所示:表1　时间的期望值Table 1　preferences of ti m eslot时间点T 1T 2T 3T 4T 5T 6T 7T 8T 9T 10T 11T 12T 13T 14......T 20期望值128411284112841128 (1) 第二点如果某一门课多于1个时间片(4学时或多于4学时),或一个教师带两门以上的课,都希望能在时间上分散安排,这样从学生接收知识和教师的教学效果上都是很好的.我们用编号相同的两课的时间差来描述这种离散度并给出相应的期望值.如表3所示:表2　课程离散度期望值Table 2　preferences of i n terval degree of courese两课时间差1,192,3,17,184,5,15,166,7,13,148,9,10,11,12期望值0241016 所以定义适应度函数f (g )=6ni =1(g (t (S i ))+h (S i ))(g ),其中g (t (s i ))表示课程所占时间片的期望值,h (s i )表示课程离散度,f 即为所有课程时间期望值与课程离散度之和.在Q 类课中主要考虑的是让教室有效合理地得到利用.因此我们的适应度函数定义为:g (x )=A ×6n i =11l (r (S i ))-Q (S i ) +1(x ) 其中Q (s i )表示课程s i 的选课人数,表示课程s i 所在教室的大小.该式分母中加1是为了避免房间大小与选课人数正好相等的情况出现,从而产生O 分母.杂交概率和变异概率的选取在相当大程度上影响算法的收敛速度和近优解的质量,为加快GA 的搜索效率和有效地防止陷于局部最优解,本文采用自适应的杂交概P c 和变异概率P c =k 1sin (Π2×f m ax -f ′c f m ax -f avg )　f ′c Εf avg k 2 f ′c <f avgPm =k 3sin (Π2×f m ax -f m f m ax -f avg )　f m Εf avg k 4 f m <f avg 其中:0<k 1、k 2、k 3、k 4≤1是群体的最大适应度函数值,f avg 是群体的平均适应度函数值,f ′c 是进341第2期张春梅等　课表的多指标数学模型及解决方法441内蒙古大学学报(自然科学版)2004年行杂交的两个染色体串中适应度函数值较大者,f m是变异串的适应度函数值.由自适应的杂交概率和变异概率的定义可以看出,定义的形式满足:0ΦP cΦ1;0ΦP mΦ1,另外,当f′c=f m ax时,P c=0;f m=f m ax时,Pm=0.这表明当前代的最优个体不经过杂交操作和变异操作而直接进入到下一代.5　结束语 该文给出了排课问题的数学模型及解决方法,其思想和方法对解决类似的优化组合问题也有一定的借鉴作用.参考文献:[1]　Garey M R,Johnson D S.Co m p u te and Intractability:A Gu id e to the theory of N P co m p leteness[M].San fran2cisco:W.H,F reem an Co.,1979.[2]　李明.一个基于智能化搜索的排课表演算法及其client server实现[J].现代计算机,1997,59:21～22.[3]　洪力奋.基于人工智能原理的大学课表编排模型[J].合肥工业大学学报(自然科学版),1999,22(4),101～104.[4]　陈洁.学校教务部门排课问题的数学模型及算法[J].管理信息系统,1999,3:53～56.[5]　董艳云,钱晓群,张宇舒.基于课元相关运算的高校排课算法[J].甘肃交通大学学报,1998,33(6):670～673.[6]　周建新,王科俊等.课表编排专家系统[J].计算机应用,2000,20(5):76～78.[7]　魏平,熊伟清.计算机辅助课表编排技术的研究[J].甘肃工业大学学报,1997,23(4):76～81.[8]　王祜民,赵致格.排课表问题中的分组优化决策算法[J].控制与决策,1999,14(2):109～114.[9]　王祜民,赵致格.时间表问题中的定额匹配算法[J].清华大学学报,1998,38(6):8～11.[10]　W erra D de.A n Introducti on to T i m etabling[J].E u r.J.Op nl.R cs.S oc,1985,48(11):1178～1190.[11]　W righ t M.Schoo l T i m etabling using H euristic Search[J].J.Op nl.R cs.S oc,1996,47(3):347～357.[12]　H ertz A.F inding a feasible course schedule using tabu search[J].D iscrete A pp lied M athe m atics,1992,35(2):250～270.[13]　A bram son A.Constructing schoo l ti m etables using si m ulated annealing:Sequential and Parallel A lgo rithm s[J].M anag e m ent S cience,1991,37(1):98～113.[14]　Safaai D,Sigeru O.Inco rpo rating constraint p ropagati on in genetic algo rithm fo r university ti m etable p lanning[J].E ng ineering A pp lications of A rtif icial Intellig ence,1999,35(2):241～253.[15]　L uan F,Yao X.So lving real2w o rld lecture room assignm ent p roblem s by genetic algo rithm s,Comp lexity Inter2nati onal[J].A n E lectronic J ou rnal of Co m p lex S y ste m R esearch,1996,3:87～90.[16]　Co lo rni A,M arco.do rigo,M aniezzo V.M etaheuristics fo r h igh schoo l ti m etabling[J].Co m p u tational Op ti2m iz ation and A pp lications,1998,(9):275～298.[17]　张春梅,行飞.用自适应的遗传算求解大学课表安排问题[J].内蒙古大学学报(自然科学版),2002,33(4):459～464.(责任编委　孙　炯) T he M u lti2target M athem atical M odeland So lu ti on of T i m etab le P rob lemZHAN G Chun2m ei1,X I N G Fei1,L I AN G Zh i2an2(1.Colleg e of S ciences and T echnology,N ei M ong ol U n iversity,H ohhot010021,P R C;2.D ep a rt m en t of A pp lied M a the m a tics,S hang ha i F inance and E cono m ics U n iversity,S hang ha i200433,P R C) Abstract:T i m etab le p rob lem is a m u lti2target op ti m ized decisi on p rob lem and typ ical p rob lem in adm in istrati on and p lann ing.Som e ex isting m athem atical m odels and so lu ti on s of the ti m etab le p rob lem are discu ssed.Key words:ti m etab le p rob lem;genetic algo rithm s;m u lti2target decisi on。

排课问题课程设计一、课程目标知识目标：1. 让学生掌握排课的基本概念、原则和方法。

2. 让学生了解排课软件的功能及操作流程。

3. 让学生了解我国中小学课程设置及课时分配的相关规定。

技能目标：1. 培养学生运用排课原则和方法，设计合理的课程表。

2. 培养学生熟练操作排课软件，提高排课效率。

3. 培养学生分析课程设置、课时分配问题，并提出改进方案的能力。

情感态度价值观目标：1. 培养学生对教育事业的热爱，树立正确的教育观念。

2. 培养学生团队协作精神，学会在集体中共同解决问题。

3. 培养学生关注教育改革，积极参与教育实践，为提高教育质量贡献自己的力量。

课程性质：本课程为实用性课程，以解决实际排课问题为目标，结合理论教学与实践操作，使学生掌握排课技能。

学生特点：学生为中学教育专业高年级学生，具备一定的教育理论基础，对实际教育问题有一定了解，但可能缺乏实践经验。

教学要求：结合学生特点，注重理论与实践相结合，强调实际操作能力的培养，提高学生解决实际排课问题的能力。

通过本课程学习，使学生能够独立设计合理的课程表，为未来教育工作打下坚实基础。

二、教学内容1. 排课基本原理：介绍排课的目的、原则、影响因素等，使学生明确排课的重要性。

- 教材章节：第二章 排课的基本原理与要求- 内容列举：排课的目的、原则、课时分配、课程设置等。

2. 排课方法与策略：讲解常见的排课方法、技巧以及优化策略，提高学生排课能力。

- 教材章节：第三章 排课方法与策略- 内容列举：线性规划法、网络图法、遗传算法等排课方法；避免冲突、优化课时、合理分配教师资源等策略。

3. 排课软件应用：介绍排课软件的功能、操作方法，使学生能够熟练使用软件进行排课。

- 教材章节：第四章 排课软件及其应用- 内容列举：排课软件的功能模块、操作流程、注意事项等。

4. 实际案例分析：分析典型排课案例，让学生了解实际排课过程中可能遇到的问题及解决方案。

- 教材章节：第五章 排课案例分析- 内容列举：中小学课程表设计、课时冲突处理、特殊需求排课等案例。

2．1. 自动排课算法1 .问题的描述我们讨论的自动排课问题的简化描述如下:设要安排的课程为{ 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 ,并存在以下约束关系:n ≤20 , (1)N = 6n， i =1， Ni ≤20. (2)自动排课问题是:设计适当的数据结构和算法, 以确定{ C1 , C2 , ., Cn } 中每个课程的教学应占据的时间段,并且保证任何一个时间段仅由一门课程占据.2 .主要数据结构对于每一门课程,分配2 个字节的“时间段分配字”(无符号整数) :{ T1 , T2 , ., Tn} . 其中任何一个时间段分配字(假设为Ti ) 都具有如下格式:Ti 的数据类型C 语言格式定义为:unsigned int . Ti 的最高位是该课程目前是否是有效的标志,0 表示有效,1 表示无效(如停课等) ;其它各位称为课程分配位, 每个课程分配位占连续的3 个位(bit) ,表示某教学日(星期一～星期五) 安排该课程的时间段的值,0 表示当日未安排,1 ～ 4 表示所安排的相应的时间段(超过4 的值无效) .在这种设计下, 有效的时间段分配字的值应小于32 768 (十六进制8000) , 而大于等于32 768 的时间段分配字对应于那些当前无效的课程(既使课程分配位已设置好也如此) , 因此很容易实现停课/ 开课处理.3 .排课算法在上述假设下,自动排课算法的目标就是确定{ C1 , C2 , ., Cn} 所对应的{ T1 , T2 , ., Tn} .从安排的可能性上看,共有20 !/ (20 - N) !种排法( N 的含义见(2) 式) . 如果有4 门课,每门课一周上2 次,则N = 8 ,这8 次课可能的安排方法就会有20 !/ (20 - 8) ! = 5 079 110 400 ,即50 多亿种. 如果毫无原则地在其中选择一种方案,将会耗费巨大量的时间. 所以排课的前提是必须有一个确定的排课原则. 我们采用轮转分配法作为排课原则:从星期一第1 时间段开始按{ C1 , C2 , ., Cn} 中所列顺序安排完各门课程之后(每门课安排1 次) ,再按该顺序继续向后面的时间段进行安排,直到所有课程的开课次数符合{ N1 , N2 , ., Nn} 中给定的值为止. 在算法描述中将用{ C[1 ] , C[2 ] , ., C[ n ]} 表示{ C1 , C2 , ., Cn} , 对{ N1 , N2 , ., Nn}和{ T1 , T2 , ., Tn} 也采用同样的表示法.算法1 排课算法输入{ 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) 3 3～week 3 3 -1 位中N[c-index ]的值减1如果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) 式) , 而存储时间段分配字所用空间为2 n 个字节( n 为课程门数) .4 .冲突检测算法有时在自动排课完毕后,需要人工调整某些课程的安排时间,如把第i 门课程在人工干预下改成星期数为week 、时间段为segment 的位置,则根据上述数据结构需做如下运算:T [ i ] = T [ i ] &(～ (7 << (week - 1) * 3) ) + (segment << (week - 1)*3) ,其中&、～和n 分别为按位与、按位取反和按位左移运算符(下同) .问题是如何判断是否已有其它课程安排在同一个时间段上. 设人工调整的时间段分配字为T[1 ] ,则该问题描述为:判断时间段分配字T [1 ] 与{ T[2 ] , T [3 ] , ., T [ n ]} 中的某个分配字是否存在相同课程分配位上的相等的非零时间段值, 或者说{ T [2 ] , T [3 ] , .,T[ n ]} 中是否存在与T [1 ] 冲突的时间段分配字. 为简化起见,在以下算法描述中假设所有时间段分配字的最高位为0.算法2 冲突检测算法输入T1 和{ T2 , ., Tn} .输出与T1 冲突的{ T2 , ., Tn} 中的时间段分配字.①对c-index = 2 ,3 , ., n 做以下操作:初始化屏蔽字mask = 7对星期值week = 1 ,2 ,3 ,4 ,5 做以下操作:如果T[1] & mask 等于T[c-index] & mask ,而且二者不等于0则: T[ 1 ]与T[c-index ]相冲突,转①mask 左移3 位(或乘8)②算法结束本算法时间复杂度为O ( n) ( n 为课程门数)5.算法分析此算法以课程为中心，进行搜索匹配，取最先匹配的值；具有占有空间少，运算速度快的特点。