下载文档原格式
题目：某学校举行乒乓球比赛，在初赛时采用循环赛，设有n位选手参赛，初赛共进行n-1天，每位选手与其他每一位选手进行一场比赛，然后按照积分进行选拔进入决赛的选手。
根据学校作息时间，要求每位选手每天必须进行一场比赛，不能轮空。
按此要求为比赛安排具体日程，即决定每天各选手的对阵情况。
解题思路：可考虑使用分治思想来建华日程的安排，按照分治策略，可以将所有的参赛选手分为两半，则n个选手的比赛日程就可以通过n/2个选手的比赛日程表来决定。
继续用这种一分为二的方法对选手们进行划分，直到只剩下2位选手时情况就很简单了。
实验代码：#define MAXN 64int a[MAXN][MAXN]={0};void gamecal(int k,int n) //deal from k--k+n{int i,j;if(n==2){a[k][1]=k; //hosta[k][2]=k+1; //vipa[k+1][1]=k+1; //hosta[k+1][2]=k; //vip}else{gamecal(k,n/2);gamecal(k+n/2,n/2);for(i=k;i<k+n/2;i++){for(j=n/2+1;j<=n;j++)a[i][j]=a[i+n/2][j-n/2];}for(i=k+n/2;i<k+n;i++){for(j=n/2+1;j<=n;j++)a[i][j]=a[i-n/2][j-n/2];}}}int main(){int m,i,j;cout<<"please input the player number: ";cin>>m;j=2;for(i=2;i<8;i++){j=j*2;if(j==m)break;}if(i>=8){cout<<"the player number must be pow(2,n),and smaller than 65 !"<<endl;return 0;}gamecal(1,m);cout<<"Num: ";for(i=1;i<m;i++)cout<<i<<"d ";cout<<endl;for(i=1;i<=m;i++){cout<<" ";for(j=1;j<=m;j++)cout<<a[i][j]<<" ";cout<<endl;}return 0;}。
问题描述：设有n=2^k个运动员要进行网球循环赛。
现要设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能参赛一次；(3)循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。
在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。
其中1≤i≤n，1≤j≤n-1。
8个选手的比赛日程表如下图：算法思路：按分治策略，我们可以将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
如上图，所列出的正方形表是8个选手的比赛日程表。
其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。
据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。
依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。
算法步骤：(1)用一个for循环输出日程表的第一行for(int i=1;i<=N;i++) a[1][i] = i(2)然后定义一个m值，m初始化为1，m用来控制每一次填充表格时i（i表示行）和j（j表示列）的起始填充位置。
(3)用一个for循环将问题分成几部分，对于k=3，n=8，将问题分成3大部分，第一部分为，根据已经填充的第一行，填写第二行，第二部分为，根据已经填充好的第一部分，填写第三四行，第三部分为，根据已经填充好的前四行，填写最后四行。
for (ints=1;s<=k;s++) N/=2;(4)用一个for循环对③中提到的每一部分进行划分for(intt=1;t<=N;t++)对于第一部分，将其划分为四个小的单元，即对第二行进行如下划分同理，对第二部分（即三四行），划分为两部分，第三部分同理。
分治算法及其应用分治算法是一种常见的算法思想，它主要的思想是将一个问题分解为多个子问题，分别求解后再将其合并为原问题的解。
分治算法在计算机科学中有着广泛的应用，例如排序、搜索、图像处理等领域。
1.基本思想分治算法的基本思想是将一个大问题分解为若干个相似的子问题，并递归地求解这些子问题，最后将结果合并成原问题的解。
例如，在求解一个大数组的排序问题时，可以先将数组分成两个子数组，再对每个子数组进行排序，最后将两个子数组合并成一个有序的数组。
2.实现分治算法的实现通常采用递归的方法。
在递归过程中，每次将大问题分解为若干个子问题，然后将子问题递归地求解，直到子问题无法再分解，然后进行合并。
以归并排序为例，该算法分为分解、解决和合并三个过程。
首先将一个大数组分解为两个相等的子数组，然后递归地对子数组进行排序，最后将两个有序的子数组合并成一个有序的数组。
3.算法复杂度分治算法的复杂度主要取决于子问题规模和分解子问题的方式。
通常情况下，分治算法的时间复杂度可以表示为：T(n) = aT(n/b) + f(n)其中，a是每个递归过程的次数，b是子问题规模，f(n)是除了递归外的其他操作的复杂度。
根据主定理，当a>b^d时，算法复杂度为O(n^logb a)，否则算法复杂度为O(n^d)。
4.应用分治算法在计算机科学中有广泛应用，例如排序、搜索、图像处理等领域。
归并排序、快速排序、堆排序等都是基于分治算法实现的排序算法。
在搜索领域，二分查找算法就是一种基于分治思想的搜索算法。
在图像处理领域，分治算法可以用来实现图像的分割、匹配等操作。
例如，可以将一幅图像分解成若干个子图像，然后对每个子图像进行处理，最后将处理结果合并成原图像的结果。
总之，分治算法是一种非常重要的算法思想，它能够解决很多复杂的问题，并且在实际应用中取得了很好的效果。
分治法在安排循环赛中的应用
循环赛是一种现象，它可以给有限的参赛者之间带来最大值的完美竞争和有趣的观点，因此，如何有效地安排循环赛一直是比赛组织者所面临的重要问题。
分治法是求解循环赛安排问题的一种有效方法，它是一种很常见的算法以及实际的解决方法，可用来解决在比赛中如何有效地安排参赛者的许多技术问题。
分治法是一种典型的深度优先搜索（DFS）算法，它采用一种
按“分而治之”的思想来解决复杂问题。
它将比赛安排看作一个
由不同队伍组成的复杂性网络，可以将这个网络划分成多个小的网络，通过求解这些小网络来最大化循环赛的覆盖面，从而实现全局最优解。
除了分治法，另一种常用的安排循环赛的算法是“拉格朗日循
环比赛安排法”，它可以将循环赛看作一个多维的最优化问题，通过求解约束和不等式条件来找到全局最优解，从而使得参赛者能够更好地比较和评价，给比赛带来有效把握。
总之，分治法和拉格朗日循环安排法都是求解比赛安排问题的有效算法，它们既可以使得比赛具有最大的覆盖范围，又可以使比赛具有最佳的参赛者安排，有增加竞争性和趣味性，提高比赛的品质。
附件二【学生用】《算法分析与设计》综合训练实习报告题目：利用分治思想设计循环赛日程表学号姓名专业班级指导教师实践日期目录一、综合训练目的与要求 (1)二、综合训练任务描述 (1)三、算法设计 (1)四、详细设计及说明 (5)五、调试与测试 (5)六、实习日志 (8)七、实习总结 (8)八、附录：核心代码清单 (8)一、综合训练目的与要求本综合训练是软件工程专业重要的实践性环节之一，是在学生学习完《算法分析》课程后进行的综合练习。
本课综合训练的目的和任务：1. 巩固和加深学生对算法分析课程基本知识的理解和掌握；2. 培养利用算法知识解决实际问题的能力；3. 掌握利用程序设计语言进行算法程序的开发、调试、测试的能力；4. 掌握书写算法设计说明文档的能力；5. 提高综合运用算法、程序设计语言、数据结构知识的能力。
二、综合训练任务描述有n个运动员要进行网球循环赛，设计比赛日程表：（1）每个选手必须与其他n-1个选手赛一次；（2）每个选手一天只能赛一次；（3）当n是偶数时，循环赛进行n-1天；当n是奇数时，循环赛进行n天；（4）要求掌握分治法或者多边形方法；（5）设计一个界面，显示产生的日程表；（6）编程语言不限；三、算法设计(1) 文字描述按分治策略，可以将所有的选手对分为两组（如果n是偶数，则直接分为n/2每组，如果n是奇数，则取（n+1）/2每组），n个选手的比赛日程表就可以通过为（n/2或（n+1）/2）个选手设计的比赛日程表来决定。
递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。
这时只要让这两个选手进行比赛就可以了。
下图给出的是六个选手的比赛日程表，其中第一列表示1-6个选手，第二列到第六列表示各个选手在第一天到第五天的所遇到的选手。
(2)框图比赛人数nNNYNYNYYNYint i=1i<=Ni++a[1][i]=ii++m=1s=1s<=k?N=N/2int t=1t<=N?int i=m+1i<=2*mj=m+1j<=m+1a[i][j+(t-1)*m*2] = a[i-m][j+(t-1)*m*2-m] a[i][j+(t-1)*m*2-m] = a[i-m][j+(t-1)*m*2]j++i++t++s++ m=m*2k+=1伪代码public static 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];}}public static void tournament(int n) {if (n == 1) {a[1][1] = 1;return;}if (odd(n)) {tournament(n + 1);}tournament(n / 2);makecopy(n);}public static boolean odd(int n) {return (n & 1) != 0;}public static void makecopy(int n) // makecopy 与copy算法类似，但是要区分n/2为奇数或偶数的情形{if (n / 2 > 1 && odd(n / 2))copyodd(n);elsecopy(n);}public static void copyodd(int n) // 实现n/2为奇数时的复制{int b[] = new int[size];int m = n / 2;for (int i = 1; i <= m; i++) {b[i] = m + i;b[m + i] = b[i];}for (int i = 1; i <= m; i++) // 这个循环比较难看懂，试着在纸上走走n=6时的情形，就能明白为什么要这么写 { for (int j = 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 (int j = 2; j <= m; j++) { a [i][m + j] = b[i + j - 1]; a [b[i + j - 1]][m + j] = i; }}}}四、详细设计及说明1.输入数字n 判断n 的奇偶性，根据情况进行分治法，安排赛程。
分治算法在循环赛赛程分配中的应用循环赛赛程分配是指在一个参赛队伍数量为2的幂次方的情况下，如何设计赛程，使得每个队伍都能与其他队伍进行一次比赛。
分治算法是一种将问题划分为更小的子问题，然后递归地解决这些子问题，并将子问题的解合并为原始问题的解的方法。
在循环赛赛程分配中，我们可以使用分治算法来实现一个高效的赛程分配算法。
首先，考虑到参赛队伍数量是2的幂次方，我们可以将所有队伍分为两个组，并将每个组分别再次分成两个更小的子组。
这个过程可以持续进行直到每个组只有两个队伍。
然后，将每个组内的两个队伍进行比赛，得到胜者和败者。
胜者将进入下一轮的比赛，而败者则被淘汰。
这个过程可以一直进行，直到最后只剩下一个胜者。
为了更好地理解分治算法在循环赛赛程分配中的应用，下面我们可以考虑一个具体的例子。
假设有8个队伍，编号分别为A、B、C、D、E、F、G、H。
首先，我们先将它们分成两组，每组4个队伍。
第一轮比赛：组1：A、B、C、D组2：E、F、G、H然后，在每个组内进行比赛，得到胜者和败者。
第二轮比赛：组1：胜者A、胜者B、胜者C、胜者D组2：胜者E、胜者F、胜者G、胜者H同样地，在每个组内进行比赛。
第三轮比赛：组1：胜者A、胜者B组2：胜者C、胜者D组3：胜者E、胜者F组4：胜者G、胜者H再次进行比赛。
第四轮比赛：组1：胜者A组2：胜者B组3：胜者C组4：胜者D组5：胜者E组6：胜者F组7：胜者G组8：胜者H最后，胜者A将被认定为整个比赛的冠军。
通过上述例子，我们可以看到分治算法在循环赛赛程分配中的应用。
通过将问题不断地划分为更小的子问题，并通过递归地解决这些子问题，最后合并子问题的解，我们可以有效地设计出循环赛的赛程，使得每个队伍都能与其他队伍进行一次比赛。
总结来说，分治算法在循环赛赛程分配中的应用是通过将问题划分为更小的子问题，并通过递归地解决这些子问题，最终得到一个完整的赛程安排。
这种方法可以保证每个队伍都能与其他队伍进行一次比赛，并且通过使用递归和分治的思想，我们能够高效地解决问题。
循环赛程表#define MAXN 64#define MAX 32int a[MAX][MAX];void Copy(int tox, int toy, int fromx, int fromy, int n) { for (int i=0; i<n; i++)for (int j=0; j<n; j++)a[tox + i][toy + j] = a[fromx + i][fromy + j];}void Table(int k, int a[][MAX]){ int i, n = 1 << k;int r;for (i=0; i<n; i++)a[0][i] = i + 1;for (r=1; r<n; r<<=1){ for (i=0; i<n; i+=2*r){ Copy(r, i + r, 0, i, r);Copy(r, i, 0, i + r, r);}}//ENDFOR}void Out(int a[][MAX], int n){ for (int i=0; i<n; i++){ for (int j=0; j<n; j++) printf("%3d", a[i][j]);printf("\n");}printf("\n");getch();}void main(){ int i;for (i=0; i<5; i++){ int len = 1 << i;Table(i, a);Out(a, len);}}归并排序void merge(int data[], int p, int q, int r){ int n1 = q - p + 1;int n2 = r - q;int L[n1],R[n2];for(int i = 0, k = p; i < n1; i++, k++) L[i] = data[k];for(int i = 0, k = q + 1; i < n2; i++, k++) R[i] = data[k];for(int k = p, i = 0, j = 0; i < n1 && j < n2; k++){ if(L[i] > R[j]) { data[k] = L[i]; i++; }else { data[k] = R[j]; j++; }}if(i < n1) { for(j = i; j < n1; j++, k++) data[k] = L[j]; }if(j < n2) { for(i = j; i < n2; i++, k++) data[k] = R[i]; }}void merge_sort(int data[], int p, int r){ if(p < r){ int q = (p + r) / 2;merge_sort(data, p, q);merge_sort(data, q + 1, r);merge(data, p, q, r);}}快速排序int partition(int number[], int left, int right){ int s = number[right];int i = left - 1;for(int j = left; j < right; j++)if(number[j] <= s) { i++; SW AP(number[i], number[j]); } SW AP( number[i+1], number[right] );return i+1;}void quicksort(int number[], int left, int right){ int q;if(left < right){ q = partition(number, left, right);quicksort(number, left, q-1);quicksort(number, q+1, right);}}二分搜索（非递归）public static int binarySearch(int [] a, int x, int n){ // 在a[0] <= a[1] <= ... <= a[n-1] 中搜索x// 找到x时返回其在数组中的位置，否则返回-1int left = 0; int right = n - 1;while (left <= right){ int mid = (left + right)/2; // mid = low + ((high - low) / 2);if (x == a[mid]) return mid;if (x > a[mid]) left = mid + 1;else right = mid - 1;}return -1; // 未找到x}二分递归public static int binarySearch(int a[], int x, int left ,int right){ // 找到x时返回其在数组中的位置，否则返回-1if (left>right) return -1; // 未找到xelse{ int mid = (left + right)/2;if (x == a[mid]) return mid;if (x > a[mid]) return binarySearch(a, x, mid+1,right);else return binarySearch( a,x,left,mid);}}大数乘法int qiuweishu(long z){ int t=0;while(z>0){ z=z/10; t++; }return t;}main(){ long x,y,a,b,c,d;double z;printf("Please input the two number x and y:\n");scanf("%,%l",&x,&y);a=x/(long)pow10(qiuweishu(x)/2);b=x%(long)pow10(qiuweishu(x)/2);c=y/(long)pow10(qiuweishu(y)/2);d=y%(long)pow10(qiuweishu(y)/2);z=(double)(a*c*pow10(qiuweishu(x))+(a*d+b*c)*pow10(qiuweishu(x)/2)+b*d); /*z=(a*c*(long)pow10(qiuweishu(x))+((a-b)*(d-c)+a*c+b*d)*(long)pow10(qiuw eishu(x)/2)+b*d);*/printf("the result is %ld:",z);}棋盘覆盖#define BOARD_SIZE 4int board[BOARD_SIZE][BOARD_SIZE];// c1, r1: 棋盘左上角的行号和列号c2, r2: 特殊方格的行号和列号void chessboard(int r1, int c1, int r2, int c2, int size) // size = 2 ^ k{ if(1 == size) return;int half_size;static int domino_num = 1;int d = domino_num++;half_size = size / 2;if(r2 < r1 + half_size && c2 < c1 + half_size) //特殊方格在左上角子棋盘{ chessboard(r1, c1, r2, c2, half_size); }else // 不在此棋盘，将此棋盘右下角设为相应的骨牌号{ board[r1 + half_size - 1][c1 + half_size - 1] = d;chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size);}if(r2 < r1 + half_size && c2 >= c1 + half_size) //特殊方格在右上角子棋盘{chessboard(r1, c1 + half_size, r2, c2, half_size); }else // 不在此棋盘，将此棋盘左下角设为相应的骨牌号{ board[r1 + half_size - 1][c1 + half_size] = d;chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size);}if(r2 >= r1 + half_size && c2 < c1 + half_size) //特殊方格在左下角子棋盘{ chessboard(r1 + half_size, c1, r2, c2, half_size);}else // 不在此棋盘，将此棋盘右上角设为相应的骨牌号{ board[r1 + half_size][c1 + half_size - 1] = d;chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size - 1, half_size);}if(r2 >= r1 + half_size && c2 >= c1 + half_size) //特殊方格在左上角子棋盘{chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size); }else // 不在此棋盘，将此棋盘左上角设为相应的骨牌号{ board[r1 + half_size][c1 + half_size] = d;chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size);}}//ENDint main(){ board[2][2] = 0;chessboard(0, 0, 2, 2, BOARD_SIZE);for(i = 0; i < BOARD_SIZE; i++){for(j = 0; j < BOARD_SIZE; j++){printf("%-4d", board[i][j]);}printf("\n");}}。
