分治法 |
您所在的位置：网站首页 › ig比赛日程表 › 分治法 |
分治法
|
循环比赛日常安排表
题目描述提示
题目解题Code 递推Code 递归结语
题目描述
设有n个选手进行循环比赛，其中n = 2^m，要求每名选手要与其他n - 1名选手都赛一次，每名选手每天比赛一次，循环赛共进行n - 1天，要求每天没有选手轮空。 输入 一行，包含一个正整数m。 输出 表格形式的比赛安排表（n行n列），每个选手的编号占三个字符宽度，右对齐。 样例输入 Copy 3 样例输出 Copy 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 提示以表格的中心为拆分点，将表格分成A、B、C、D四个部分，就很容易看出有A=D，B=C，并且，这一规律同样适用于各个更小的部分。 题目链接 - 循环比赛日常安排表 题目解题每名选手要与 n - 1 名选手比赛，那就需要比 n - 1 天，每天比赛的人不一样，并且打印出每日选手比赛的安排表 同理： 2号选手 第1天和 1号选手比赛 4号选手 第3天和 1号选手比赛 8号选手 第7天和 1号选手比赛 题目最终目的是打印比赛日程表 我们发现了一个规律， 左上角和右下角 一模一样（红色表示） 右上角和左下角一模一样（蓝色表示） 我们再看左上角的红色和右上角的蓝色，发现规律没？ 右上角的数值等于左上角的数组 + 4 (而且位置编号相差4) 现在我们仅仅看左上角的红色，里面的两个绿色和黄色基本一摸一样 右上角的黄色数值等于左上角上的数值+ 2（而且位置编号相差 2） 可以发现右上角的数值等于左上角的值 加上 n（此时小方块的大小） 左上角的绿色部分里的深蓝和紫色也满足以上规律 可以发现一个二维平面可以变为同等类型的小规模问题 一个 8 * 8 可以变为一个 4 * 4 一个4* 4 可以变为 一个 2 * 2 一个2 * 2 可以变为 一个 1 * 1 这不就是分治思想嘛？哈哈哈，的确是的，大规模问题化为小规模问题 天下久和必分， 分久必和。 （说明： 分治是一种算法思想， 随之大部分会用递归来实现，因为递归刚好体现啦分治。但是递归仅仅只是编程的一种实现，我们还可以用递推， 迭代等等） 分治仅仅是一种思想而不是实现编程的手段！！！ Code 递推有了分治的思想，该题的递推很简单啦！从小到大 ，从1 往外推 #include int a[100][100]; void gen(int x, int y, int d) {//gen函数的作用是左上角的数值复制到右上角 int i, j; for (i = x; i //左上角复制到右下角， 右上角复制到左下角 int i, j; for (i = 0; i int i, j; for (i = 0; i int d = 1; a[0][0] = 1;//首先左上角为1 int m; scanf("%d", &m); for (int i = 1; i if (d == 0) return ;//递归结束边界 fun(d/2);//每次递归都 / 2 //下面代码部分基本不变 gen(0, 0, d/2); cpy(0, d/2, d/2, d/2, 0); cpy(0, 0, d/2, d/2, d/2); } void gen(int x, int y, int d) { int i, j; for (i = x; i int i, j; for (i = 0; i int i, j; for (i = 0; i int d = 1; a[0][0] = 1; int m; scanf("%d", &m); int k = pow(2, m); fun(k);//其实就是用一个fun函数来自我调用 print(k, k); return 0; } 结语当然新手上路，该题的分治策略讲解也许会有许多不足，多多谅解！ 此处附上循环比赛日常安排表的视频链接， 推荐看一看来加深分治思想的理解和巩固 https://www.bilibili.com/video/BV1rp4y1X7mb |
可以发现 1号选手 在 第1 天和2 号选手比赛，在 第3 天和4 号选手比赛 第7天(第n-1天) 和 6号选手比赛
【本文地址】
今日新闻 |
推荐新闻 |