一、实战演练——欧洲冠军杯比赛日程安排“问题”。
问题描述：
一年一度的欧洲冠军杯马上就要打响了，在初赛阶段采用循环制，设共有n队参加，初赛共进行n-1天，每队要和其他各队都进行一场比赛，然后按照最后积分选拔进入决赛的球队。
要求每队只能进行一场比赛，并且不能轮空。
请按照上述需求安排比赛日程，决定每天各队的对手。
算法要求：
根据分治算法的思路，将所有参赛队伍分为两组，则n队的比赛日程表可以通过n/2个队的比赛日程来决定。
然后继续按照一分为二的方法对参赛队进行划分，直到只剩余最后两队时为止。
假设n队的编号为1，2，3，……，n，比赛日程表为一个二维表格。
每行表示每队所对阵队的编号，8支球队7天比赛的日程表如下：
编号第1天第2天第3天第4天第5天第6天第7天（这怎么这么像数独？）
根据对表的分析，可以将复杂的问题分治而解，即分解为多个简单的问题。
例如有4队的比赛日程表：
编号第1天第2天第3天代码实现：
#includestdio.h#defineMAXN64inta[MAXN+1][MAXN+1]={0};voidg(intk,intn){//处理从编号k开始的n个球队的比赛日程inti,j;if(n==2){a[k][1]=k;//参赛球队编号a[k][2]=k+1;//对阵球队编号a[k+1][1]=k+1;//参赛球队编号a[k+1][2]=k;//对阵球队编号}else{g(k,n/2);g(k+n/2,n/2);for(i=k;ik+n;i++){//填充右上角for(j=n/2+1;j=n;j++){a[i][j]=a[i+n/2][j-n/2];}}for(i=k+n/2;ik+n;i++){//填充左上角for(j=n/2+1;j=n;j++){a[i][j]=a[i-n/2][j-n/2];}}}}intmain(){intm,i,j;printf("参赛球队数：");scanf_s("%d",m);j=2;for(i=2;i8;i++){j=j*2;if(j==m){break;}}if(i=8){printf("参赛球队数必须为2的整数次幂，并且不超过64！\n");getch();return0;}g(1,m);printf("\n球队编号：");for(i=2;i=m;i++){printf("%2d天",i-1);}printf("\n");for(i=1;i=m;i++){for(j=1;j=m;j++){printf("%5d",a[i][j]);}printf("\n");}getchar();}
首先出现了一个尴尬的问题，迈克菲杀毒软件居然将其识别成了病毒！
而我通过删除部分代码排查，发现问题出现在了voidgamecal(intk,intn)函数上。因而我将其函数改成了voidg(intk,intn)。
分析：
首先是定义一个常量64，用于数组a的定义长度，之所以+1，是为了把数组的0元素除外。因为8*8=64个组合。
然后定义一个递归函数g，表示从编号k开始的n个球队的比赛日程。
例如从编号1开始的4个球队。
定义两个变量i，j，用于循环和数组的第一维和第二维的识别.
然后判断，如果球队只有2个的话：
就执行当前编号的第2个队伍，即：
如果是从编号5开始的2个球队，就是如下的情况：
否则，当队伍大于2时，就执行自我调用，也就是递归。
将队伍减半，再判断，直到剩下2个队伍后，就输出。
例如，从编号5开始的3个队伍？好吧！不支持奇数的队伍。
因为在main()函数中，通过36~41行；如果是奇数，让j变得很大，以至于i=8。再判断i是否大于等于8，从而进行输出提示并结束程序。
如果是偶数，也就会因为j等于队伍数而结束循环，从而i也就是队伍数。（感觉这部分好像可以改善？）
然后就是第二次的自我调用，并且这时将标号追加到上一个编号+队伍的一半，其实也就是往下迁移上一个结构，并且再让队伍数减半。
例如，原本是从编号1开始的两个队伍，不过由于n=2时，不执行这一步，又因为队伍数不能是奇数，所以至少也得是从编号1开始的4个队伍。
然后进行递归函数后，就是从编号1的两个队伍；
然后再执行新的递归函数，就是从编号（1+4/2）的（4/2）的队伍，也就是从编号3的2支队伍，也就是a[3][1]=3，a[3][2]=4，a[4][1]=4，a[4][2]=3。
即：
可以肯定，这只是第1天的量。
然后再通过for循环的i，k嵌套，将其进行输出。
例如：从编号1的4个球队；
i=1;i1+4/2;i++;也就是i等于1，小于3，i++，所以会输出两行；而j=4/2+1；j=4;j++;也就是j等于3，小于等于4，j++，所以会输出两个列。也就构成左上角了。
然后再通过a[i][j]=a[i+n/2][j-n/2];公式，将第3行第4行的第1列和第2列的值，平移到第1行第2行的第3列和第4列中。
即：
然后又是一个for循环i，j嵌套输出。
例如：同样从编号1的4个球队；
i=1+4/2；i1+4；i++；也就是i等于3，小于5，i++，也是个2*2矩阵。
j=4/2+1;j=4;j++;也就是j等于3，小于等于4，j++，同样也是个2*2矩阵。
并且通过a[i][j]=a[i-n/2][j-n/2];进行平移。
即：
（由此可以看出，能看到其规律性是大事啊！）
最后就是在主函数中的使用了。
首先是定义三个变量，m为手动输入的队伍数。i和j虽然用于循环，同样的也用于判断队伍数是否为奇数，如果第一个for(i=2;i8;i++)循环和if(i=8)。
然后调用从编号1开始的m个队伍。
在经过递归自我调用后，就自然的生成了一个m*m的表格。
然后也就只要注意遍历出来就行了。
不过这里要注意的是，这个for(i=2;i=m;i++)语句是用来打印天数的，而最后的for(i=1;i=m;i++){for(j=1;j=m;j++)……才是矩阵的打印。
运行结果：
当然，因为程序本身在编辑时，最大的队数就是8，所以超过8就会提示：
8*8=64！
PS：
这里由于给出了k和n是“处理从编号k开始的n个球队”，所以让我有了头绪。同时想必也是因为参数少，又碰巧看出了规律，以及一点点的捋顺出来的结果吧！
虽然通过这次，让我感觉对上一个也有了些感悟。不过还是……以后再说吧！
预览时标签不可点收录于话题#个上一篇下一篇转载请注明：http://www.0431gb208.com/sjslczl/291.html
