分治算法-球队问题

《分治算法-球队问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验一：分治与递归【实验目的】应用分治与递归的算法求循环赛问题。【实验性质】验证性实验。【实验内容与要求】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：⑴每个选手必须与其他n-1个选手各赛一次；⑵每个选手一天只能赛一次；⑶循环赛一共进行n-1天。按此要求可将比赛日程表设计－成有n行和n-l列的一个表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。用分治法编写为该循环赛设计一张比赛日程表的算法并运行实现、对复杂度进行分析。算法思想：按分治策略，我们可以将所有选手对分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比

2、赛日程表来决定。递归地用这种一分为二的策略对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。下图所列出的正方形表是4个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手2和选手3至选手4第1天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，将左下角小块中的所有数字按其相对位置抄到右上角，这样我们就分别安排好了选手1至选手2和选手3至选手4在后2天的比赛日程。这种安排是符合要求的。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。下表是8个选手的日程安排表。#include

3、#include#include#includeintdata[32][32];voidtable(intk,intn){inti,j;if(n==2){data[k-1][0]=k;data[k][0]=k+1;}else{table(k,n/2);table(k+n/2,n/2);}for(i=k-1;i

4、){for(j=n/2;j>n;if((n&(n-1))!=0)//在二进制数中，若2的k次方等于n，则n只有最高位为1，其他位为0，故（n-1）的最高位为0(相对于n来说)，其他位为1，{cout<<"输入有误，请重新输入！"<

5、>>n;cout<<"输入有误，请重新输入！"<