循环赛日程表棋盘覆盖问题

《循环赛日程表棋盘覆盖问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验报告（2）学号：10101444姓名：黄佳伟班级：计102成绩：实验名称：分治算法设计验证实验地点：信息楼215所使用的工具软件及环境：MicrosoftVisualStudio2010一、实验要求：项目一：循环赛日程表问题1．了解程序的执行过程，正确分析算法时间复杂性；2．完成代码编写，调试正确3．对n=8，n=11进行测试。项目二：棋盘覆盖问题求解1．了解程序的执行过程，正确分析算法时间复杂性；2．完成代码编写，输出棋盘覆盖矩阵；3．对4×4，8×8棋盘进行测试。二、实验内容：项目一：循环赛日程表问题1．重要

2、的程序说明设你班有n=2^k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次。(2)每个选手一天只能参赛一次。(3)循环赛在n-1天内结束按此要求可将比赛日程表设计成有n行和n-1列的表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下两个选手时，比赛日程表的制定就变得很简单，这时只要让这两个选手进行比赛就可以

3、了。#includeusingnamespacestd;constintSIZE=50;inta[SIZE][SIZE];voidcopy(intn);voidtournament(intn);intodd(intn);voidmakecopy(intn);voidcopyodd(intn);voidmain()—6—{intn;inti,j;cout<<"输入运动员人数:";cin>>n;tournament(n);cout<<"***********循环赛日程表***********"<

4、(n))//n为奇数和偶数输出情况不同，要分别考虑{for(i=1;i<=n;i++){for(j=1;j<=n+1;j++)if(a[i][j]==n+1)cout<<"0";elsecout<

5、=a[i][j]+m;a[i+m][j]=a[i][j+m];a[i+m][j+m]=a[i][j];}}voidtournament(intn){if(n==1){a[1][1]=1;—6—return;}if(odd(n)){tournament(n+1);return;}tournament(n/2);makecopy(n);}intodd(intn){if(n%2==1)return1;elsereturn0;}voidmakecopy(intn){if(n/2>1&&odd(n/2))copyodd(n);elsecopy(

6、n);}voidcopyodd(intn){intb[SIZE];intm=n/2;for(inti=1;i<=m;i++){b[i]=m+i;b[m+i]=b[i];}for(inti=1;i<=m;i++){for(intj=1;j<=m+1;j++){if(a[i][j]>m){a[i][j]=b[i];a[m+i][j]=(b[i]+m)%n;}elsea[m+i][j]=a[i][j]+m;}for(intj=2;j<=m;j++){a[i][m+j]=b[i+j-1];—6—a[b[i+j-1]][m+j]=i;}}}1．

7、算法复杂性分析与计算时间复杂度：O(4k)2．程序运行测试结果列举项目二：棋盘覆盖问题求解1．重要的程序说明棋盘覆盖问题:在一个2^k×2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。—6—分析：当k>0时，将2k×2k的棋盘分成4个2k-1×2k-1的子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为

8、特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小棋盘的汇合处，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，知道棋盘转化为1×1的棋盘。#inc