某学院10名博士生（B1～B10）选修6门课程（A～F）的情况如表18-7

某学院10名博士生（B1～B10）选修6门课程（A～F）的情况如表18-7所示（用√表示选修）。现需要安排这6门课程的考试，要求是：（1）每天上、下午各安排一门课程考试，计划连续3天考完。（2）每个博士生每天只能参加一门课程考试，在这3天内考完全部选修课。（3）在遵循上述两条的基础上，各课程的考试时间应尽量按字母升序做先后顺序安排（字母升序意味着课程难度逐步增加）。为此，各门课程考试的安排顺序应是（）

AAE，BD，CF
BAC，BF，DE
CAF，BC，DE
DAE，BC，DF

参考答案

参考解析：

首先，我们直接从来考虑问题。可以根据试题的限制条件：“每个博士生每天只能参加一门课程考试，在这3天内考完全部选修课”，来进行判断各选项是否满足。如果按照A选项，第2天考BD，则因为B1同时选修了这2门课程，将违反“每个博士生每天只能参加一门课程考试”的约束。如果按照B选项，第1天考AC，则因为B2同时选修了这2门课程，将违反“每个博士生每天只能参加一门课程考试”的约束。如果按照c选项，第1天考AF，则因为B3同时选修了这2门课程，将违反“每个博士生每天只能参加一门课程考试”的约束。因此，只有选项D符合要求。下面再介绍另外一种解法（图示法）。将6门课程作为6个结点画出，如图18-14所示。我们可以在两个课程结点之间画连线表示他们不可以在同一天安排考试，那么，每个博士生的各门选修课程之间都应画出连线。例如，B1博士生选修了A、B、D三门课程，则ABD之间都应有连线，表示这三门课中的任何二门都不能安排在同一天。从图18-14可以看出，能够安排在同一天考试的课程（结点之间没有连线）有AE、BC、DE、DF。因此，课程A必须与课程E安排在同一天。课程B必须与课程C安排在同一天，余下的课程D只能与课程F安排在同一天。

分类：应用数学题库,高级系统架构师题库