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

《算法设计与分析》实 验 报 告（ 2 ） 学号 姓名：黄佳伟 班级： 计102 成绩： 实验名称：分治算法设计验证 实验地点：信息楼215 所使用的工具软件及环境：Microsoft Visual Studio 2010 实验要求： 项目一：循环赛日程表问题 1．了解程序的执行过程，正确分析算法时间复杂性； 2．完成代码编写，调试正确 3．对n=8，n=11进行测试。 项目二：棋盘覆盖问题求解 1．了解程序的执行过程，正确分析算法时间复杂性； 2．完成代码编写，输出棋盘覆盖矩阵； 3．对4×4，8×8棋盘进行测试。 二、实验内容： 项目一：循环赛日程表问题 重要的程序说明 设你班有n=2^k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次。 (2)每个选手一天只能参赛一次。 (3)循环赛在n-1天内结束 按此要求可将比赛日程表设计成有n行和n-1列的表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。按分治策略，可以将所有选手对分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下两个选手时，比赛日程表的制定就变得很简单，这时只要让这两个选手进行比赛就可以了。 #includeiostream using namespace std; const int SIZE = 50; int a[SIZE][SIZE]; 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输入运动员人数:; cin n; tournament(n); cout***********循环赛日程表***********endl; if(odd(n)) // n为奇数和偶数输出情况不同，要分别考虑 { for(i = 1; i=n; i++) { for(j = 1; j=n+1; j++) if(a[i][j] == n+1) cout 0 ; else cout a[i][j] ; cout endl; } } else { for(i = 1; i=n; i++) { for(j = 1; j=n; j++) cout a[i][j] ; cout endl; } } } void copy(int n) { int m = n/2; for(int i = 1; i=m; i++) for(int j = 1; j=m; j++) { a[i][j+m] = a[i][j] + m; a[i+m][j] = a[i][j+m]; a[i+m][j+m] = a[i][j]; } } void tournament(int n) { if(n == 1) { a[1][1] = 1; return; } if(odd(n)) { tournament(n+1); return; } tournament(n/2); makecopy(n); } int odd(int n) { if(n%2==1)