循环赛问题,急用,100分,绝对信誉!!!
有n个队伍(1-n),参加比赛,比赛时间不能超过n天,每支队伍每天只能参加一次比赛.每两支队伍之间仅比一次,请设计一个赛程表!
比如和世界杯32强出线以后.............
问题点数：100、回复次数：2Top
1 楼smalltalk（老徐）回复于 2003-11-02 13:54:57 得分 100
循环赛问题,通过函数arrangeMatches()解决，已经验证！程序如下：
#include <string>
#include <vector>
using namespace std;
typedef unsigned int T_TEAMNUM;
struct T_MATCH
{
T_TEAMNUM a;
T_TEAMNUM b;
};
struct DAYMATCHES
{
vector<T_MATCH> matches;
};
/* if no conflict, return 0, otherwise return other */
int testCondition(T_MATCH match, DAYMATCHES & daymathes)
{
vector<T_MATCH>::iterator it;
for (it = daymathes.matches.begin(); it != daymathes.matches.end(); it++)
{
if ( (it->a == match.a) || (it->a == match.b) || (it->b == match.a) || (it->b == match.b) )
return -1;
}
return 0;
}
/* return value, o mean OK, other mean Can't arrange */
int arrangeMatches(unsigned int totalteams, unsigned int limitdays, vector<DAYMATCHES>& result)
{
vector<T_MATCH> leftmatches;
T_MATCH one;
//1.generate all matches to be arranged
for (T_TEAMNUM i = 1; i <= totalteams; i++)
{
for (T_TEAMNUM j = i + 1; j <= totalteams; j++)
{
one.a = i;
one.b = j;
leftmatches.push_back(one);
}
}
//2.arrange the matches for each day with conditions
DAYMATCHES dms;
vector<T_MATCH> lefttemp;
for (unsigned int day = 1; day <= limitdays; day++)
{
if (0 == leftmatches.size())
break;
lefttemp.clear();
dms.matches.clear();
for (unsigned int pos = 0; pos < leftmatches.size(); pos++)
{
one = leftmatches[pos];
if ( testCondition(one, dms) == 0 )
dms.matches.push_back(one);
else
lefttemp.push_back(one);
}
result.push_back(dms);
leftmatches = lefttemp;
}
if (leftmatches.size() > 0)
return -1;//can't arrange it.
else
return 0;//arrange OK.
}
#define TOTAL_TEAMS 32
#define LIMIT_DAYS 32
int main()
{
vector<DAYMATCHES> arrange;
unsigned int tt = TOTAL_TEAMS;
unsigned int ld = LIMIT_DAYS;
arrange.clear();
int ret;
ret = arrangeMatches(tt, ld, arrange);
if (ret == 0)
{
printf("List of arrangement matches between %d teams in %d days:\n", tt, ld);
DAYMATCHES dms;
vector<T_MATCH>::iterator it;
for (unsigned int day = 0; day < arrange.size(); day++)
{
printf("Matches in %d day\n", day+1);
printf("------------------------\n");
dms = arrange[day];
for (it = dms.matches.begin(); it != dms.matches.end(); it++)
printf("Team %d vs Team %d\n", it->a, it->b);
}
}
else
printf("Can't arrange matches between %d teams in %d days!\n", tt, ld);
return ret;
}
Top
2 楼flyinger（风往北吹）回复于 2003-11-02 14:22:23 得分 0
这好象就是8皇后问题！
1 2 3 4 5 6 7 8（对）
2
3
4
5
6
7
8
往里边填7个数，保证不重复，每一行没有没有重复的数！带回朔功能！Top
相关问题
关键词
得分解答快速导航
相关链接
广告也精彩
反馈
