日程安排表【】问题解数据结构算法精选考研习题￥62.1

时间：2022-05-21 19:04:19 来源：网络整理

一、算法思路

1、想法

分治算法的思路是：对于一个大小为N的问题，如果这个问题很容易解决（比如规模N小），那么直接解决，否则就分解了分成M个小规模的子问题，这些子问题相互独立且形式与原问题相同，递归求解这些子问题，然后将每个子问题划分为子问题的解为合并得到原问题的解

数据结构和算法选考题

￥62.1

购买

2、分治法的适用范围

一般来说，具有以下特点的问题可以通过分治算法来解决：

(1）问题可以通过分解成几个更小规模的相同问题来解决

(2）解决问题的规模分解到一定程度，很容易解决

(3）@ >结合子问题的解可以得到问题的解

(4）求解问题分解的子问题相互独立

3、分治法步骤

(1）分解：将要解决的问题分解成更小的同质问题

(2）解：当子问题的划分足够小时，用比较简单的方法求解子问题，得到子问题的解

(3）@>合并：根据求解问题的要求，逐层合并子问题的解，即可以构成最终解

二、分治法示例：比赛日程安排

1、问题描述

在一所学校举行乒乓球比赛在预赛阶段设置为循环赛。有n名选手参加了预赛。预赛为期n-1天。 .根据学校的作息时间，要求每位参赛者每天必须比赛一次，不能轮空。根据这一要求，为比赛安排了具体的赛程，即确定每位选手每天要面对的对手

2、分析

n=2^k 选手参加循环赛，需要设计满足以下要求的比赛日程：

1）每位选手必须与其他选手比赛n-每位选手只能玩一次；

2）每位参赛者一天只能玩一次

3、插图

(1）2人的情况

如果只有两个玩家，那么第 0 列被视为玩家编号（我们从 0 开始对列进行编号，我们的第 0 列可以看作是每个玩家在第 0 天与自己对战），并且第一列是每个玩家第一天想玩的玩家编号

( 2）如果玩家人数为2^2=4，那么赛程如下

如果有4人日程安排表，设计4/2=2人的赛程，前一天1-2人的赛程显示在上表左上角深蓝色子表部分，前一天3-4名选手的比赛日程见上表左下角的子表。床单。相应地日程安排表，对于接下来两天的日程，可以将左上角的子表按照其对应的位置复制到右下角的子表中，左下角的子表可以根据对应的位置将corner复制到右上角的子表中。（同时，我们注意到这是一个行列是参赛人数2^2 = 4的表。当使用分治法找到行列是（2 ^2）/2) ，首先确定左上角的子表，左下角的子表可以通过左上角的子表相加得到（2^< @2）/2)

(3）@>如果玩家的人数是2^3=8，那么赛程如下：

当玩家人数为8时，左上角的子表是玩家1到玩家4前三天的比赛日程，左下角是前三天的比赛日程5号选手到8号选手。根据接下来四天的比赛赛程，将左上角的子表按照对应的位置复制到右下角，复制到左下角。 , 的子表根据其对应位置复制到右上角。至此，比赛日程的安排就完成了。

这个解法是将求解2^k个选手的比赛日程的问题分成2^1、2^2、……、2^k个选手的赛程。也就是说，如果需要2^k个玩家的赛程，必须分成两部分，然后将2^(k-1)个玩家的赛程合并。当然，这个方案可以只找到玩家人数是 2 次方的情况

在求解每次迭代的过程中，可以看到Do 4部分：

1）找到左上角的分表：左上角的分表是前2名的比赛上半场赛程表^(k-1)@ > 玩家。

2）找到左下角的分表：左下角的分表是剩余2^(k-1) @>玩家，这个子表和左上角子表的对应关系是，对应元素等于左上子表对应元素加上2^(k-1) .

3）@>找到右上子表：等于左下子表的对应元素

4）寻找右下角的子表：等于左上角子表的对应元素

代码实现如下：

#包括

int main(void)

{