论坛 › 【编程】编程圣殿 › 长期困惑的算法问题

苏格拉底柏拉图 发表于 2008-4-12 16:57

长期困惑的算法问题

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

皇家救星 发表于 2008-4-12 17:54

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

iptton 发表于 2008-4-12 18:02

LZ是来考我们的？

星期日 发表于 2008-4-12 18:54

:call: 压根就不会！

苏格拉底柏拉图 发表于 2008-4-12 19:55

原帖由 iptton 于 2008-4-12 18:02 发表 https://www.gdutbbs.com/images/common/back.gif
LZ是来考我们的？
是我学了三年的计算机都不懂写这样的程序，所以来问大家。

cdy20 发表于 2008-4-13 08:58

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

无聊的路过

苏格拉底柏拉图 发表于 2008-4-14 14:09

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

kids 发表于 2008-4-15 08:22

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

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

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

kids 发表于 2008-4-15 08:29

晕死，大老。你看书拉

zaijzhgh 发表于 2008-4-15 15:43

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

hjack 发表于 2008-4-15 18:15

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

Welcome to here.

cdy20 发表于 2008-4-15 19:56

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

cdy20 发表于 2008-4-15 19:56

Orz   kids            。

kids 发表于 2008-4-15 20:07

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

cdy   一边去

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

onttpi 发表于 2008-4-15 20:23

LS两位公开TQ呀。。

kids 发表于 2008-4-15 20:24

同个ip的话

onttpi 发表于 2008-4-15 21:29

LS系谁。。。

zaijzhgh 发表于 2008-4-15 22:32

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

using namespace std;
void Round_play(int number, int (&cal));
int main(int argv, char **argc)
{
      int number;
      int i, j;
      int cal = {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<<"   ";
                        if(j%(length-1) == 0)
                              cout<<ENDL;
               }
      }
      system("pause")      ;
      return 0;
}
void Round_play(int number, int(&cal))
{

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

zaijzhgh 发表于 2008-4-15 22:33

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

onttpi 发表于 2008-4-15 22:58

well..

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

查看完整版本: 长期困惑的算法问题