《循环赛日程表棋盘覆盖问题.doc》由会员分享，可在线阅读，更多相关《循环赛日程表棋盘覆盖问题.doc（9页珍藏版）》请在三一文库上搜索。
1、算法设计与分析实 验报告(2 )学号：10101444姓名：黄佳伟班级： 计102成绩:实验名称：分治算法设计验证实验地点：信息楼215所使用的工具软件及环境：Microsoft Visual Studio 2010一、实验要求：项目一：循环赛日程表问题1了解程序的执行过程，正确分析算法时间复杂性;2 完成代码编写，调试正确3 .对n=8, n=11进行测试。项目二：棋盘覆盖问题求解1.了解程序的执行过程，正确分析算法时间复杂性;2 .完成代码编写，输出棋盘覆盖矩阵；3 .对4X 4, 8X 8棋盘进行测试。二、实验内容：项目一：循环赛日程表问题1 .重要的程序说明设你班有n=2Ak个运动员要
2、进行网球循环赛。现要设计一个满足以下要求的比赛日程表：(1) 每个选手必须与其他n-1个选手各赛一次。(2) 每个选手一天只能参赛一次。(3) 循环赛在n-1天内结束按此要求可将比赛日程表设计成有n行和n-1列的表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分 害V,直到只剩下两个选手时，比赛日程表的制定就变得很简单，这时只要让这两个选手进 行比赛就可以了。#in cludeusing n amespace std;const int S
3、IZE = 50;int aSIZESIZE;void copy(i nt n);void tour name nt(i nt n);int odd(i nt n);void makecopy(i nt n);void copyodd(i nt n);void mai n() int n;int i,j;cout n;tourn ame nt(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 ;elsecout ai
4、j ”;cout en dl;elsefor(i = 1; i=n; i+)for(j = 1; j=n; j+)cout aij ”;cout en dl;void copy(i nt n)int m = n/2;for(i nt i = 1; i=m; i+)for(i nt j = 1; j 1 & odd(n/2)copyodd( n);elsecopy( n);void copyodd(i nt n) int bSIZE;int m = n/2;for(i nt i = 1; i=m; i+)bi = m+i;bm+i = bi;for(i nt i = 1; i=m; i+)for
5、(i nt j=1; j m)aij = bi;am+ij = (bi + m)% n;elseam+ij = aij + m;for(i nt j = 2; j0时，将2kx 2k的棋盘分成4个2k-1 x 2k-1的子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，我们可以用一个L型骨牌覆盖这3个较小棋盘的汇合处，这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，知道棋盘转化为1 x 1的棋盘。#in elude #i nclude using n a
6、mespace std;int board100100;存放棋盘L型的标号数组；int tile=0; / L 型骨牌号int mai n()void chessBoard(i nt tr, i nt tc, int dr, i nt dc, int size); / 棋盘的覆盖方法；void display(i nt *board,i nt size);/ 棋盘覆盖图；int size,dr,dc;coutttt棋盘覆盖问题n;cout size;cout分别输入特殊块的行列下标dr,dc(0-(size-1) drdc;boarddrdc=-1;cout棋盘覆盖图示：n; chessBoa
7、rd(0, 0, dr, dc, size);int i,j;for( i=0;isize;i+)for( j=O;jsize;j+) coutsetw(6)boardij;coute ndl a; return 0;void chessBoard(i nt tr, i nt tc, int dr, i nt dc, int size)if (size=1)return;int t = tile+;/ L 型骨牌号int s = size/2; / 分割棋盘II覆盖左上角子棋盘if (drtr+s&dctc+s)II特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);
8、elseII此棋盘中无特殊方格boardtr+s-1tc+s-1=t; II 用t号L型骨牌覆盖右下角 chessBoard(tr,tc,tr+s-1, tc+s-1, s);II 覆盖其余方格II覆盖右上角子棋盘if (dr = tc + s)II特殊方格在此棋盘中chessBoard(tr, tc+s, dr, dc, s);elseII此棋盘中无特殊方格boardtr + s - 1tc + s = t;II用t号 L型骨牌覆盖左下角chessBoard(tr, tc+s, tr+s-1, tc+s, s);II 覆盖其余方格II覆盖左下角子棋盘if (dr = tr + s & dc
9、= tr + s & dc = tc + s) II特殊方格在此棋盘中chessBoard(tr+s, tc+s, dr, dc, s);elseboardtr + stc + s = t;用t号L型骨牌覆盖左上角chessBoard(tr+s, tc+s, tr+s, tc+s, s); II 覆盖其余方格2 算法复杂性分析与计算设T(k)是算法ChessBoard覆盖一个2Ak x 2Ak棋盘所需的时间，则从算法的分治策略可知，T(k)满足如下递归方程： k=0,T(k)=O(1) k0,T(k)=4T(k-1)+O(1)解此递归方程可得：T(k)=O(4Ak)程序运行测试结果列举: IH
10、DOTS systesc棋盘覆盖问题As1ec：2 1 牍盘曙盖图示21CA-14C:TlND0TSs7St e*32cBd.exe棋盘覆盖问题Asize(size=2,4,8,16,32,64Ji 8疔刘輸入特操坝的行列T标壮,dc：7盖图示,223377S82113766841S599&1044500910101212131301718181211111317171&ia1411151519161620141415-11?1?20203三、实验结果、收获与体会：做第一个循环赛日程表时，开始就按书上的算法做，后来才发现实验报告上要计算运动员为奇数 时的日程表，再重新想，费了好大一番周折才完成。看来以后写程序要仔细读题，认真分析，考虑 到各个方面的小问题，才能做出好的，完美的程序。第二个程序感觉比较难理解，读了好久的题目 与书上的分析才理解，以后遇到题目也要仔细看，好好分析，不能图快，要好好理解算法的目的。11