天天看点

循环赛问题(分治)

设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:⑴每个选手必须与其他n-1个选手各赛一次;⑵每个选手一天只能赛一次;⑶循环赛一共进行n-1天。按此要求可将比赛日程表设计-成有n行和n-l列的一个表。在表中第i行和第j列处填入第i个选手在第j天所遇到的选手。

分析:

分治策略, 递归地用一分为二的策略对选手进行分割,知道只剩2个选手。

1.初始化第一位选手

2.递归分割选手直到剩2人,通过返回更新的比赛表,右下角复制左上角,左下角复制右上角

继续阅读