网站建设 排名下拉,社交网站实名备案,重庆建网站哪家售后服务比较好,商城类网站主要分为哪些模块队列的应用1.基于队列的医院挂号模拟系统2.队列的运用1.基于队列的医院挂号模拟系统
代码实现分享
2.队列的运用
问题描述#xff1a;某运动会设立N个比赛项目#xff0c;每个运动成员可以参加1~3个项目。试问如何安排比赛日程#xff0c;既可以使同一运动员参加的项目不…
队列的应用1.基于队列的医院挂号模拟系统2.队列的运用1.基于队列的医院挂号模拟系统
代码实现分享
2.队列的运用
问题描述某运动会设立N个比赛项目每个运动成员可以参加1~3个项目。试问如何安排比赛日程既可以使同一运动员参加的项目不安排在同一时间进行又可以使总的竞赛项目日程最短。 若将此问题抽象成数学模型则归属于“划分子集问题”即将集合A划分成k个不想交的子集A1,A2…,AkKn使得同一子集中的元素均无冲突关系并要求划分子集数目尽可能地少。 也可以把这个问题表述为同一子集的项目为可以同时进行的项目并且希望运动会的日程尽可能的短。 解决划分子集问题可利用“过筛”的方法。从第一个元素考虑起凡不和第一个元素发生冲突的元素都可以和它分在同一子集中然后再“过筛”出一批互补冲突的元素为第二子集依此类推直至所有元素都进入某个子集为止。
为了更好地描述用“过筛”的方法划分子集用队列保存待选项目编号用一维数组case保存待选项编号与已入选子集的项目编号的冲突情况。排在队头的项目编号i是当前的待选项目能否入选由case[i]的值来决定值为0表示与当前子集的项目无冲突i出队并加入子集反之则有冲突i出队并重新排队等待下一个子集的筛选。
下面给出划分第1个子集A1的主要步骤。 1将项目编号0~8依次进队列。将队头的项目编号0出队放入子集A1中将冲突数组与项目0对应的行取出放入一维数组case中。此时case中的每个元素的值表示元素下标的项目与项目0的冲突情况。 2当前队头是项目1项目1能否加入子集A1由case[1]的值来决定。当前case[1]是1表示项目1与子集A1中的项目0有冲突项目1不能加入子集A1出队后直接入队。 3当前队头是项目2项目2能否加入子集A1由case[2]的值来决定。当前case[2]是0表明项目2与子集A1中的已有项目没有冲突项目2出队后加入子集A1。现在A1中已经有了2个项目后来入选的项目必须与A1中的2个项目都没有冲突为此将冲突表中与刚入选的项目2对应的行按下标与case数组相加用两者的和更新case数组此时的case数组是后续待选项目能否入选的依据。 4当前队头是项目3项目3能否加入子集A1由case[3]的值来决定。当前case[3]是0表明项目3与子集A1中的已有项目没有冲突项目3出队后加入子集A1。现在A1中已经有3个项目后来入选的项目必须与A1中的3个项目都没有冲突为此将冲突表中与刚入选的项目3对应的行按小标与case数组相加用两者的和更新case数组。此时的case数组是后续待选项目能否入选的依据。 5当前队头是项目4项目4能否加入子集A1由case[4]的值来决定。当前case[4]是1表明项目4与子集A1中的已有项目有冲突项目不能加入子集A1出队后直接进队。 6当前队头是项目5项目5能否加入子集A1由case[5]的值来决定。当前case[5]是2表明项目5与子集A1中的已有项目冲突项目5不能加入子集A1出队后直接入队。 7当前队头是项目6项目6能否加入子集A1由case[6]的值来决定。当前是1表明6与子集A1中的已有项目冲突项目6不能加入子集A1出队后直接入队。 8当前的队头是项目7项目7能否加入子集A1由case[7]的值来决定。当前case[7]是0与子集A1中的已有项目没有冲突项目7出队后放入子集A1。现在A1中已经有4个项目后来的项目必须与A1中的4个项目都没有冲突为此将冲突表中与刚入选的项目7对应的行按下标与case数组相加用两者的和更新case数组此时的case数组后续待选项能否入选的依据。 9当前队头是项目8项目8能否加入子集A1由case[8]的值来决定。当前case[8]是1表明项目8与子集A1中的已有项目有冲突项目8不能加入子集A1出队后直接入队。
当排在队头的项目编号小于刚加入子集的项目编号时表示队列中的所有项目都被“过筛”一遍第一个子集划分完成。用同样的方法划分其他子集直到队列为空。
划分子集算法的基本思想如下。 pre n组号 0//n为数据元素的个数 全体成员入栈 while(队列不能为空) { //队头元素i出队列 if(ipre)//开辟新的组 { 组号 case 数组初始化 } if(i能入组//i与该组的元素没有冲突 { i入组记下序号为i的元素所属组号 修改case数组 } else i重新入队列 prei//前一个出队列的元素序号 }
