#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
enum {
GAMENUMPLAYER = 6,
NUMPLAYER = 100,
ROUNDNUMPLAYER = NUMPLAYER - NUMPLAYER % GAMENUMPLAYER,
NUMROUND = 27
};
static int Schedule[NUMROUND][NUMPLAYER];
static int Numgame[NUMPLAYER][NUMPLAYER];
static int Numunplayed = (NUMPLAYER * (NUMPLAYER - 1)) / 2;
static void count(int r, int i, int delta) {
int start;
int stop;
int j;
if (i >= ROUNDNUMPLAYER) return;
start = i - i % GAMENUMPLAYER;
stop = start + GAMENUMPLAYER;
for (j = start; j < stop; j++) {
int p;
int q;
if (j == i) continue;
p = Schedule[r][i];
q = Schedule[r][j];
if (q < p) {
int t;
t = p;
p = q;
q = t;
}
if (Numgame[p][q] == 0) Numunplayed--;
Numgame[p][q] += delta;
if (Numgame[p][q] == 0) Numunplayed++;
}
}
static void swap(int r, int i, int j) {
int t;
count(r, i, -2);
count(r, j, -2);
t = Schedule[r][i];
Schedule[r][i] = Schedule[r][j];
Schedule[r][j] = t;
count(r, i, 2);
count(r, j, 2);
}
static void validate(void) {
int nu;
int q;
nu = 0;
for (q = 0; q < NUMPLAYER; q++) {
int p;
for (p = 0; p < q; p++) {
int ng;
int r;
ng = 0;
for (r = 0; r < NUMROUND; r++) {
int i;
for (i = 0; i < ROUNDNUMPLAYER; i++) {
int k;
if (Schedule[r][i] != p) continue;
for (k = 0; k < GAMENUMPLAYER; k++) {
if (Schedule[r][i - i % GAMENUMPLAYER + k] == q) ng++;
}
}
}
assert(ng * 2 == Numgame[p][q]);
assert(Numgame[p][q] >= 0);
if (Numgame[p][q] == 0) nu++;
}
}
assert(nu == Numunplayed);
}
int main(void) {
int r;
for (r = 0; r < NUMROUND; r++) {
int i;
for (i = 0; i < NUMPLAYER; i++) {
int j;
j = rand() % (i + 1);
Schedule[r][i] = Schedule[r][j];
Schedule[r][j] = i;
}
for (i = 0; i < NUMPLAYER; i++) count(r, i, 1);
}
while (Numunplayed > 0) {
int r;
int i;
int j;
int previous;
r = rand() % NUMROUND;
i = rand() % NUMPLAYER;
j = rand() % NUMPLAYER;
previous = Numunplayed;
swap(r, i, j);
if (Numunplayed < previous) {
fprintf(stderr, "%d\n", Numunplayed);
} else if (Numunplayed > previous) {
swap(r, i, j);
}
}
for (r = 0; r < NUMROUND; r++) {
int i;
for (i = 0; i < NUMPLAYER; i++) {
if (i > 0) putchar(i % GAMENUMPLAYER == 0 ? ';' : ',');
printf("%d", Schedule[r][i]);
}
putchar('\n');
}
return EXIT_SUCCESS;
}
1 回答
处理相关社交高尔夫球手问题的方法之一是本地搜索 . 一些提出的方法非常复杂 . 下面的C程序不是;它选择一个随机的初始时间表并进行随机交换,这不会增加不玩的玩家对的数量 . 100名玩家和6人组需要至少21轮(一些玩家坐在一轮,然后需要ceil((100 - 1)/(6 - 1))= 20轮来玩每个人),所以27不是虽然我确信使用更复杂的优化技术可以做得更好,但距离最佳值太远了 .