长期困惑的算法问题

苏格拉底柏拉图

英格兰超级联赛实行20支球队双循环制，共38轮。这里我只考虑半个赛程，即只考虑一次循环。
       在一次循环里，每支球队均要与另外19支队交战一次，共19轮完成。每一轮20支球队同时开战（那么同一轮里没支球队也只能同时进行一场比赛），已对战过的球队在后面轮次里不再相碰。
       现在就想编个程序，把19轮的对阵全安排出来。请问，该程序该怎么写？

皇家救星

经典的算法问题　忘了名字了　好像叫动态规划

iptton

LZ是来考我们的？

星期日

:call: 压根就不会！

苏格拉底柏拉图

原帖由 iptton 于 2008-4-12 18:02 发表
LZ是来考我们的？

是我学了三年的计算机都不懂写这样的程序，所以来问大家。

cdy20

n阶竞赛图，
可以用分治法
也可以用dp
分治法可以优化
也可以打表

无聊的路过

苏格拉底柏拉图

我也想过分治法，但如何“分治”呢？再次，平分之后如果每边都是奇数呢？

kids

楼上你的话很奇怪，可能你用最原始的做法吧
也可以用多边形方法
选手（设为n）位偶数个的话：顶点为选手，n-1个顶点和一个中心点（画个图好过附件里面）
红线不要动，外部转一下就出一组数据

奇数可以转化为偶数的情况
慢慢玩啊

[ 本帖最后由 kids 于 2008-4-15 08:28 编辑 ]

kids

晕死，大老。你看书拉

zaijzhgh

刚写了一个类似的，不过只是对2^n支球队进行安排，使用分治法。奇数支球队肯定不行的。偶数支嘛……我只是用手排了六支球队的。对于十支及其它2*n(除了2^n)的没有验证。

hjack

zaijzhgh, Could you please share your idea with more detail? thanks.:victory: :victory:

Welcome to here.

cdy20

－－！还没解决
当n为奇数时候的时候，增设一个虚拟对手n＋1，将问题转换为n的偶数的情形
当选手与虚拟选手比赛时，轮空。
这样就转化为偶数的情况

cdy20

Orz   kids            。

kids

我得那个
(n^2)/8次
o（n^2）

cdy     一边去

[ 本帖最后由 kids 于 2008-4-16 13:20 编辑 ]

onttpi

LS两位公开TQ呀。。

kids

同个ip的话

onttpi

LS系谁。。。

zaijzhgh

code:
#include
#include
#include
#define MAXN 256

using namespace std;
void Round_play(int number, int (&cal)[MAXN+1][MAXN]);
int main(int argv, char **argc)
{
        int number;
        int i, j;
        int cal[MAXN+1][MAXN] = {0};
        cout<<"Input the number of player(2^n):";
        cin>>number;
        Round_play(number, cal);
        int length = (int)pow(2, number);
        cout<<"                 ";
        for(int k = 1; k <= length; k++ )
        {
                cout<<K<<"天";
         }
        cout<<ENDL;
         for( i = 1; i <= length; i++)
        {
                cout<<"第"<<I<<"个选手的对手：";
                 for (j = 1; j < length; j++)
                {
                        cout<<CAL[j]<<"   ";
                        if(j%(length-1) == 0)
                                cout<<ENDL;
                 }
        }
        system("pause")        ;
        return 0;
}
void Round_play(int number, int(&cal)[MAXN+1][MAXN])
{

        int col, row, m, playernumber, tag1, tag2;
        playernumber = number;
        cal[1][1] = 2;
        cal[2][1] = 1;//预先置第1和第2位选手比赛
        m = 1;
        tag1 = 1;
        for (; m < playernumber; )
        {
                m++;
                tag1 += tag1;
                tag2 = 2*tag1;        //安排2^m位选手比赛
                //首先填充日程表的左下方
                for (col = tag1 + 1; col <= tag2; col++)
                {
                        for (row = 1; row <= tag1 - 1; row++)
                        {
                                cal[col][row] = cal[col - tag1][row] + tag1;//左下方的内容等于左上方的内容对应项tag1        
                        }
                        
                }
                //然后填充日程表的右上方
                //先填日程表的右上方的第1列
                cal[1][tag1] = tag1 + 1;
                for(col = 2; col <= tag1; col++)
                        cal[col][tag1] = cal[col-1][tag1] + 1;
                //填充日程表的右上方的其他列，填法参照前一列填充当前列，也就是采用循环轮转法
                for (row = tag1 + 1; row < tag2; row++)        
                {
                        for (col = 1; col < tag1; col++)
                        {
                                cal[col][row] = cal[col+1][row-1];
                        }
                        cal[tag1][row] = cal[1][row-1];
                }
                //填充日程表的右下方
                for (row = tag1; row < tag2; row++)
                {
                        for (col = 1; col <= tag1; col++)
                        {
                                cal[cal[col][row]][row] = col;//这里是查找对应已经填好的项，根据填好的项来填没有填的项
                        }
                }
        }
}
PS:col代表行，row代表列，由于写程序的时候搞错了它们的E文意思，so……呵呵，E文不过关呀！之前写好了文档的，可是一不小心把它给删了，后悔呀。

zaijzhgh

晕死，怎么贴上去头文件就不见了？？奇怪，再贴头文件。
#include <iostream>
#include <stdlib.h>
#include <math.h>

onttpi

well..

正在上算法课。。。这学期也要慢慢细究算法了。。