【算法】座位排序算法

小咪咪 2022-06-13 13:58 126阅读 0赞

# 一、前言 #

在这里，小编想向大家说明一下需求，在很多的系统中，比如电影院的选座系统、飞机取登机牌选座系统等，都有一个选座位的功能。可见，选座位在我们的生活中还是很常用的。

小编就在最近的考试系统中，带领团队研究了一个考场分配座位的系统——电子准考证。下面小编就从两种分配方式来介绍一下。

# 二、需求说明 #

这里得说一下全局观，首先呢，每个考场会在不同的日期、不同的时间段安排学生参加考试。考生可以通过微信平台提前查询自己的考试信息，包括考试科目、考试时间、考试地点、考试座位号。通过不同的排座位的算法，达到：

*  可以使得一个考场的人随机分配座位
 *  使得一个考场的学生按照班级分配座位
 *  跳过不能使用的座位

# 三、全场随机抽取座位 #

随机抽取座位业务流程图：

![这里写图片描述][SouthEast]

这里的核心技术点就是建立一个bool数组，数组的大小和本场考试的学生个数相同，然后获取已经分配了的作为，把分配了的座位打上标记。然后随机产生一个数，判断这个座位的是否有人。如果有人就不分配，如果没有人就分配。就是这么简单。

这个操作也同样在考试的题库抽题中适用。

#region 随机不重复座位号-王雷-2017年6月18日10:32:44
            /// <summary>
            /// 随机不重复座位号-王雷-2017年6月18日10:32:44
            /// </summary>
            /// <returns></returns>
            public string RandSeatNum(StudentExamInfoEntity seie)
            {
                //获取考场号，日期，时间
                string examPlace = seie.ExamPlace.Split('-')[0];
                string ExamDate = seie.ExamDate;
                string startTime = seie.StartTime;
                //实例化D层
                RandSeatNumHelper randSeatNumHelper = new RandSeatNumHelper();
                //根据考场号，日期，时间从基础库中查出这一场有多少人，获得max的值
                int max = randSeatNumHelper.SelectPopulationInExam(examPlace, ExamDate, startTime);
                //根据考场号，日期，时间从本地库中查已经分配的座位号
                DataTable dt = randSeatNumHelper.SelectSeat(examPlace, ExamDate, startTime);
                //生成随机数
                //实例化bool数组
                bool[] flag = new bool[max + 1];
                //把已经分配过的座位号标记成true
                for (int i = 0; i < dt.Rows.Count; i++)
                {
                    int seat = Convert.ToInt32(dt.Rows[i][0]);
                    flag[seat] = true;
                }
                //生成随机数
                for (int j = 1; j <= max; j++)
                {
                    Random rm = new Random();
                    int newSeat = rm.Next(1, max + 1);
                    if (!flag[newSeat])
                    {
                        return newSeat.ToString();
                    }
                }
                return null;
            }
            #endregion

# 四、全场按班级学号分组排序 #

时序流程图：

![这里写图片描述][SouthEast 1]

在这里，用到的代码核心就是当a

#region 获取座位号-王雷-2017年6月23日15:03:09
            /// <summary>
            /// 获取座位号-王雷-2017年6月23日15:03:09
            /// </summary>
            /// <param name="seie"></param>
            /// <returns></returns>
            public int QueryStudentSeatNum(StudentExamInfoEntity seie)
            {
                //获取考场号，日期，时间
                string examPlace = seie.ExamPlace.Split('-')[0];
                string ExamDate = seie.ExamDate;
                string startTime = seie.StartTime;
                string studentNo = seie.StudentNo;
                //实例化D层
                RandSeatNumHelper randSeatNumHelper = new RandSeatNumHelper();
                int seatNum = randSeatNumHelper.QueryStudentSeatNum(examPlace, ExamDate, startTime, studentNo);
    
                string countAll = QueryAllSeatNum(examPlace);
                if (seatNum < Convert.ToInt32(countAll))
                {
                    //判断座位是否可以使用
                    while (!QuerySeatUseful(examPlace, seatNum) || !QuerySeatBeenTaken(examPlace, ExamDate, startTime, seatNum))
                    {
                        //不可使用
                        seatNum = seatNum + 1;
                    }
                    //当座位可以使用的时候
                    return seatNum;
                }
                else if (seatNum == Convert.ToInt32(countAll))
                {
                    //判断座位是否可以使用
                    if (QuerySeatUseful(examPlace, seatNum))
                    {
                        //座位可以使用，判断座位是否已经被占用
                        if (QuerySeatBeenTaken(examPlace, ExamDate, startTime, seatNum))
                        {
                            //座位没有被占用，可以使用
                            return seatNum;
                        }
                        return -1;
                    }
                    return -1;
                }
                else
                {
                    return -1;
                }
            }
            #endregion

按照班级抽取预座位：

#region 按照班级分配座位-王雷-2017年6月23日15:58:30
            /// <summary>
            /// 按照班级分配座位-王雷-2017年6月23日15:58:30
            /// </summary>
            /// <param name="examPlace">考试地点</param>
            /// <param name="ExamDate">考试日期</param>
            /// <param name="startTime">考试开始时间</param>
            /// <param name="studentNo">学生学号</param>
            /// <returns>int</returns>
            public int QueryStudentSeatNum(string examPlace, string ExamDate, string startTime, string studentNo)
            {
                SQLHelper sqlHelper = new SQLHelper("connStr");
                string strSql = " select * FROM (select top 100 percent row_number() over (order by StudentNo) as rowNum ,StudentNo FROM V_StudentExamInfo where ExamDate ='" + ExamDate + "' and StartTime ='" + startTime + "' AND ExamPlace like '" + examPlace + "%' ORDER BY StudentNo) as b where b.StudentNo ='" + studentNo + "'";
                DataTable dt = sqlHelper.ExecuteQuery(strSql, CommandType.Text);
                return Convert.ToInt32(dt.Rows[0]["rowNum"]);
            } 
            #endregion

判断座位是否可以使用：

#region 判断座位是否可以使用-王雷-2017年7月3日10:55:38
            /// <summary>
            /// 判断座位是否可以使用-王雷-2017年7月3日10:55:38
            /// </summary>
            /// <param name="examPlace">考场</param>
            /// <param name="seatNum">座位</param>
            /// <returns>bool</returns>
            public bool QuerySeatUseful(string examPlace, int seatNum)
            {
    
                string sql = "SELECT * FROM t_computer WHERE RoomNo = @examPlace and SeatNo=@seatNum and IsUse ='1'";
                MySqlParameter[] parameters = new MySqlParameter[]
                {
                    new MySqlParameter("@examPlace",examPlace),
                    new MySqlParameter("@seatNum",seatNum )
    
                };
    
                DataTable dt = new DataTable();
                try
                {
                    //调用sqlhelper的方法得到结果
                    dt = MySqlHelper.ExecuteDataTable(sql, parameters);
                    if (dt != null && dt.Rows.Count > 0)
                    {
                        //可以使用
                        return true;
                    }
                    else
                    {
                        //不可以使用
                        return false;
                    }
                }
                catch (Exception ex)
                {
                    //错误展出
                    WriteLog.WriteError(ex.ToString());
                    throw;
                }
            } 
            #endregion

查询座位是否已经被占用：

#region 查询座位是否已经被占用-王雷-2017年7月3日16:07:51
            /// <summary>
            /// 查询座位是否已经被占用-王雷-2017年7月3日16:07:51
            /// </summary>
            /// <param name="examPlace"></param>
            /// <param name="ExamDate"></param>
            /// <param name="startTime"></param>
            /// <param name="seatNo"></param>
            /// <returns></returns>
            public bool QuerySeatBeenTaken(string examPlace, string ExamDate, string startTime, int seatNo)
            {
                //判断座位是否已经被占用
                string sql = "select * from t_exambasicinfo where ExamPlace like @examPlace and Date=@ExamDate and StartTime=@startTime and SeatNo=@seatNo";
    
                MySqlParameter[] parameters = new MySqlParameter[]
                {
                    new MySqlParameter("@examPlace",examPlace+"%"),
                    new MySqlParameter("@ExamDate",ExamDate ),
                    new MySqlParameter("@startTime",startTime ),
                    new MySqlParameter("@seatNo",seatNo )
    
                };
    
                DataTable dt = new DataTable();
                try
                {
                    //调用sqlhelper的方法得到结果
                    dt = MySqlHelper.ExecuteDataTable(sql, parameters);
                    if (dt != null && dt.Rows.Count > 0)
                    {
                        //座位已经被占用，不能使用
                        return false;
                    }
                    else
                    {
                        //可以使用
                        return true;
                    }
                }
                catch (Exception ex)
                {
                    //错误展出
                    WriteLog.WriteError(ex.ToString());
                    throw;
                }
            } 
            #endregion

# 五、小结 #

这个是一个神奇的故事。

算法就是一个神奇的故事，当我们在学习，在想如何实现一个功能的时候，这个路子就是我们自己编辑的算法。算法也是在不断的摩擦中不断改进的。加油！

[SouthEast]: /images/20220613/d0efad4941fb4407be909fb537407b42.png
[SouthEast 1]: /images/20220613/1c8149513cc24b86af7b11bf3e6304e6.png