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

算法设计与分析实 验 报 告（ 2 ）学号：10101444 姓名：黄佳伟 班级： 计102 成绩：实验名称：分治算法设计验证实验地点：信息楼215所使用的工具软件及环境：Microsoft Visual Studio 2010一、 实验要求：项目一：循环赛日程表问题1了解程序的执行过程，正确分析算法时间复杂性；2完成代码编写，调试正确3对n=8，n=11进行测试。项目二：棋盘覆盖问题求解1了解程序的执行过程，正确分析算法时间复杂性；2完成代码编写，输出棋盘覆盖矩阵；3对44，88棋盘进行测试。二、实验内容： 项目一：循环赛日程表问题1 重要的程序说明设你班有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次。 (2)每个选手一天只能参赛一次。 (3)循环赛在n-1天内结束按此要求可将比赛日程表设计成有n行和n-1列的表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下两个选手时，比赛日程表的制定就变得很简单，这时只要让这两个选手进行比赛就可以了。#include using namespace std; const int SIZE = 50; int aSIZESIZE; void copy(int n); void tournament(int n); int odd(int n); void makecopy(int n); void copyodd(int n); void main() int n; int i,j; cout n; tournament(n); cout*循环赛日程表*endl; if(odd(n) / n为奇数和偶数输出情况不同，要分别考虑 for(i = 1; i=n; i+) for(j = 1; j=n+1; j+) if(aij = n+1) cout 0 ; else cout aij ; cout endl; else for(i = 1; i=n; i+) for(j = 1; j=n; j+) cout aij ; cout endl; void copy(int n) int m = n/2; for(int i = 1; i=m; i+) for(int j = 1; j 1 & odd(n/2) copyodd(n); else copy(n); void copyodd(int n) int bSIZE; int m = n/2; for(int i = 1; i=m; i+) bi = m+i; bm+i = bi; for(int i = 1; i=m; i+) for(int j=1; j m) aij = bi; am+ij = (bi + m)%n; else am+ij = aij + m; for(int j = 2; j0时，将2k2k的棋盘分成4个2k-12k-1的子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小棋盘的汇合处，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，知道棋盘转化为11的棋盘。#include #include using namespace std;int board100100; /存放棋盘L型的标号数组；int tile=0; / L型骨牌号int main()void chessBoard(int tr, int tc, int dr, int dc, int size); /棋盘的覆盖方法；void display(int *board,int size); /棋盘覆盖图；int size,dr,dc;coutttt棋盘覆盖问题n;coutsize;cout分别输入特殊块的行列下标dr,dc(0-(size-1)drdc;boarddrdc=-1;cout棋盘覆盖图示：n;chessBoard(0, 0, dr, dc, size);int i,j;for( i=0;isize;i+)for( j=0;jsize;j+)coutsetw(6)boardij;coutendla;return 0;void chessBoard(int tr, int tc, int dr, int dc, int size) if (size=1) return; int t = tile+; / L型骨牌号 int s = size/2; / 分割棋盘 /覆盖左上角子棋盘 if (drtr+s&dctc+s) / 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else / 此棋盘中无特殊方格 boardtr+s-1tc+s-1=t; / 用 t 号L型骨牌覆盖右下角 chessBoard(tr,tc,tr+s-1, tc+s-1, s);/ 覆盖其余方格 /覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 boardtr + s - 1tc + s = t; /用t号L型骨牌覆盖左下角 chessBoard(tr, tc+s, tr+s-1, tc+s, s);/ 覆盖其余方格 /覆盖左下角子棋盘 if (dr = tr + s & dc = tr + s & dc = tc + s) / 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else boardtr + stc + s = t; / 用 t 号L型骨牌覆盖左上角 chessBoard(tr+s, tc+s, tr+s, tc+s, s); / 覆盖其余方格 2算法复杂性分析与计算设T(k)是算法ChessBoard覆盖一个2k2k棋盘所需的时间，则从算法的分治策略可知，T(k)满足如下递归方程：k=0,T(k)=O(1)k0,T(k)=4T(k-1)+O(1)解此递归方程可得：T(k)=O(4k)3程序运行测试结果列举三、实验结果、收获与体会：做第一个循环赛日程表时，开始就按书上的算法做，后来才发现实验报告