循环赛日程表问答研究.doc

学年论文题目循环赛日程表问题研究学生指导教师年级级专业软件工程系别软件工程学院计算机科学与信息工程学院哈尔滨师范大学年月论文提要本文采用分治算法来解决循环赛日程表的安排问题。通过对问题的详细分析,列出到个选手的比赛日程表,找出两条规则,作为算法实现的依据,而后采用c语言实现算法,通过测试分析,程序运行结果正确,运行效率较高。同时也介绍了循环赛日程表问题的另一种解法多边形解法,这种方法另辟蹊径,巧妙地解决了循环赛日程表问题,运行效率较高。循环赛日程表问题研究摘要:本文采用分治算法来解决循环赛日程表的安排问题。根据算法的设计结果,采用c语言实现算法,通过测试分析,程序运行结果正确,运行效率较高。同时也介绍了循环赛日程表问题的另一种解法,这种方法另辟蹊径,想法独特,运行效率较高。关键词:循环赛日程表问题;分治法题目描述设有n个运动员要进行网球循环赛。设计一个满足以下要求的比赛日程表:()每个选手必须与其他n-个选手各赛一次;()每个选手一天只能赛一次;()当n是偶数时,循环赛进行n-天。当n是奇数时,循环赛进行n天。问题分析循环赛日程表可以采用分治法实现,把一个表格分成个小表格来处理,每个小表格都是一样的处理方法,只是参数不同。分析过程具体如下:、n=(表-).、n=(表-)、n=()添加一个虚拟选手#,构成n+=()/=,分两组,每组各自安排(),()每组跟另一组分别比赛(拷贝)这是四个人比赛的(表-)人赛程 ()把虚选手置为(表-)人赛程 这是三个人比赛的安排、n=,见表-、n=()加一个虚选手,n+=。安排好个人的比赛后,把第个人用表示即得人的。()分成两组()(),各名选手 ()依照表-,安排第组;按表-安排第组(除元素外,都加)(表-) ()把表-排于表-下方(表-) ()把同一天都有空的两组安排在一起比赛(按这种安排,肯定每天只有一对空组)。(表-)()第一组的()和第组的()分别比赛。但是由于(,),(,),()已经比赛过了,所以在后面的安排中不能再安排他们比赛。 首先,#只能和#或#比赛。(a)若#-#,由于#和#已经比赛过,所以只能安排:#-#,#-#(b)若#-#,由于#和#已经比赛过,只能安排:#-#,#-#这样安排后前三行的后两列,后三行的后两列由上面的三行来定:(表-)人赛程表-就是名选手的比赛日程安排。将其中的号作为虚拟选手,把换成,即得名选手的赛程安排表:(表-)人赛程、n=,见表-。、n=,添加,n+=。名选手的安排,由名选手(表-)构成 (表-)人赛程将其中的改成,即得名选手的赛程安排。(表-)人赛程、n=,见表-。、n=,由n+=人,将虚选手号置为来得到。、n=。人的比赛,分两组()和()各人。前人比赛的安排如表-(表-)第组的人比赛就是将前人比赛选手(非)号对应加(表-)然后两组合并,得到表-(表-)找两组中同一天中没有安排比赛的,安排他们比赛:(表-)由于两组中:按列对应的已经比赛过一次:-,-,-,-,-。后面再安排两组选手分别比赛的时候