Fork me on GitHub

大类分流软件设计

大类分流

基本思想是将6个文件模拟为一个按绩点顺序存放的队列,按排行和志愿顺序对队首元素分配专业。

将队首元素按志愿顺序映射为一个数组。对队首每个元素,如果当前志愿的专业人数达到人数限制,则判断下一个志愿。
如果所有志愿人数都已满,则放入另一个未处理学生的队列中,等一轮分配完再处理。下面是具体算法。


已知n个学生,每个学生最多5个志愿。已知6个专业的人数限制。

  1. 将6个专业对应的文件读入6个存放学生信息的队列中;
  2. 设计数器 count.每个队首的绩点排名等于count弹出,弹出的元素根据志愿顺序映射到长度为6的数组对应的位置,count加上弹出的学生的人数;绩点排行小于count说明已分配过。则直接弹出
  3. 根据数组顺序来分配专业。如果当前志愿人数未满,写入结果数组,对应专业当前人数+1;人数已满则判断下一个志愿;所有志愿人数都满则排入未处理学生的队列。
  4. 最后处理未处理学生的队列,将他们分配到当前专业人数未满的专业即可。

需要注意注意的是第二部分,有可能有绩点排行相同的情况,所做的处理是把弹出的数组处理为一个链表数组。排名相同的学生按专业顺序插入到对应数组对应位置的链表中去。处理时仍然按次序处理即可。

这个算法的关键是注意到6个文件本身是排好序的,所以并没有将所有文件合并为一个有序序列,而是通过处理来模拟达到队列的效果。


处理的关键是每次“只处理6个文件的一行中绩点最高的学生的分配”,提高效率的关键是将绩点最高的学生的信息按志愿顺序映射存储再分配,因为是按志愿顺序处理。这样排名靠前的学生处理效率将大大提高,排名靠后的学生如果是根据自身情况选择合适的志愿,处理效率也会提高。


这儿是测试得到的结果

项目已经托管到 GitHub,戳我

扫描二维码,拯救贫困山区大学生!
-------------本文结束感谢您的阅读-------------