羽毛球循环赛日程表.cpp

问题描述： 设有 个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表： （1） 每个选手必须与其他n-1个选手各赛一次； （2） 每个选手一天只能赛一次； （3） 循环赛一共进行n

// 这是使用应用程序向导生成的 VC++ 
// 应用程序项目的主项目文件。

#include "stdafx.h"
#include <wjz_execute.h>

#using <mscorlib.dll>

using namespace std;
static int circleCount=0;
int size;

void ArrangeCalendar(int team[],int** &calen,int num)
{
	if(num<=1)
	{
		cout<<"队员数目太少，无法安排！"<<endl;
		return;
	}
	int *forward_half=new int[num/2],*backward_half=new int[num/2];
	for(int i=0;i<num/2;i++)
	{
		forward_half[i]=team[i];
		backward_half[i]=team[num/2+i];
	}
	int j;

	for(i=0;i<num/2;i++)
	{
		for(j=0;j<num/2;j++)
		{
			calen[backward_half[j]-1][forward_half[i]-1]=circleCount;
			calen[forward_half[i]-1][backward_half[j]-1]=circleCount;
			circleCount++;
		}
	}
	if(num==2) return;
	ArrangeCalendar(forward_half,calen,num/2);
	ArrangeCalendar(backward_half,calen,num/2);
	delete[] backward_half;
	delete[] forward_half;
}


void ShowArrangementOf(int** &calen,int num)
{
	int **table;
	table=new int*[num];
	for(int i=0;i<num;i++)
	{
		table[i]=new int[num-1];
	}
	
	//初始化table
	int j;
	for(i=0;i<num;i++)
	{
		for(j=0;j<num-1;j++)
		{
			table[i][j]=0;
		}
	}

	multimap<int,int> pair;
	for(i=0;i<num;i++)
	{
		for(j=i+1;j<num;j++)
		{
			pair.insert (multimap<int,int>::value_type (i+1,j+1));
		}
	}


	//安排日程
	int low=0,day=0;
	multimap<int,int>::iterator pos,deleted_pos;
	int deleted=0;

	for(day=0;day<num-1 && !pair.empty();day++)
	{
		pos=pair.begin();
		if(low>=num/2) low=0;
		while(low<num/2)
		{
			if((table[pos->first-1][day]==0) && (table[pos->second-1][day]==0))
			{
				table[pos->first-1][day]=pos->second ;
				table[pos->second-1][day]=pos->first ;
				low++;
				deleted_pos=pos;
				deleted=1;
				pos++;
				pair.erase (deleted_pos);

			}
			if(!deleted) pos++;
			else
			{
				deleted=0;
			}
			if(pos==pair.end ()) pos=pair.begin ();
			
		}
	}

	//显示日程
	cout<<endl;
	for(i=0;i<num;i++)
	{
		for(j=0;j<num-1;j++)
			cout<<setw(3)<<table[i][j]<<" ";
		cout<<endl;
	}


	//销毁分配的内存
	for(i=num;i>0;)
		delete[] table[--i];
	delete[] table;
}


void StartProc(void)
{
	cout<<"\n请输入K的值：";
	char exp[10];
	cin>>exp;
	if(atoi(exp)<0) 
	{
		cout<<"输入数据不合法!"<<endl;
		return;
	}
	if(atoi(exp)>9)
	{
		cout<<"数据太大，系统气绝服务!"<<endl;
		return;
	}
	int number;
	number=(int)ldexp(1.0,atoi(exp));
	size=number;
	int **calendar;
	calendar=new int*[number];
	for(int i=0;i<number;i++)
	{
		calendar[i]=new int[number];
	}
	int j;	
	
	//初始化calendar数组
	for(i=0;i<number;i++)
	{
		for(j=0;j<number;j++)
			calendar[i][j]=0;
	}
	
	int *team=new int[number];
	for(i=0;i<number;i++)
		team[i]=i+1;

	circleCount=1;
	ArrangeCalendar(team,calendar,number);
	
	cout<<"场次\n"<<endl;
	for(i=0;i<number;i++)
	{
		for(j=0;j<number;j++)
			cout<<setw(3)<<calendar[i][j]<<" ";
		cout<<endl;
	}


	cout<<"\n日程表：\n";
	ShowArrangementOf(calendar,number);


	//销毁已分配的内存
	delete []team;
	for(int i=number;i>0;)
		delete[] calendar[--i];
	delete[] calendar;

}

int _tmain()
{
    // TODO: 请用您自己的代码替换下面的示例代码。
	cout<<"提示：此算法仅对队员数为(2＾k)的比赛有效！"<<endl;
	execute(StartProc);
	return 0;
}