算法洗脑系列(8篇)——第五篇 分治思想
一: 思想
有时候我们处理一个复杂的问题,可能此问题求解步骤非常杂,也可能是数据非常多,导致我们当时很难求出或者无法求出,古语有云:
步步为营,各个击破,这个思想在算法中称为分治思想,就是我们可以将该问题分解成若干个子问题,然后我们逐一解决子问题,最后将子问题
的答案组合成整个问题的答案。
二: 条件
当然各个思想都有它的使用领域,所以玩这场分治游戏就要遵守它的游戏规则。
① 求解问题确实能够分解成若干个规模较小的子问题,并且这些子问题最后能够实现接近或者是O(1)时间求解。
② 各个子问题之间不能有依赖关系,并且这些子问题确实能够通过组合得到整个问题的解。
三:步骤
通过上面对分治的说明,可以看到分治分三步走:
① 分解: 将问题分解成若干了小问题。
② 求解: O(1)的时间解决该子问题。
③ 合并: 子问题逐一合并构成整个问题的解。
四:举例
有n位选手参加羽毛球赛,比赛要进行n-1天,每位选手都要与其他每一个选手比赛一场并且每位选手每天都要比赛一场,请根据比赛要求
排出选手的比赛日程表。
思路:首先我们拿到问题要给自己打气,哈哈,因为日常的基本问题都跑不出我们所知道算法思想的范畴,此问题也包括在内。
当n是8,16,32时,面对这么一个庞大的问题我们可能就崩溃了,因为我们实在无法求出来,此时我们就要想想是否可以分治一下。
① 就拿16个选手的比赛安排来说,需要比赛15天。
② 分成2个8位选手7天的比赛安排。
③ 分为4个4位选手3天的比赛安排。
④ 分为8个2位选手1天的比赛安排。
相信2位选手1天的比赛安排大家都会吧,如图:
然后退化到第三步即4位选手3天的比赛安排,如图:
在图中可以看出:
第一天:将1,2位和3,4位选手的日程合并。
第二天,第三天:这两天的比赛安排其实可以发现规律的,整个表格可以划分四格,对角赋值。
程序代码如下:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Fenzhi public class Program //这里 static int[,] GameList = new int[8, 8]; static void Main(string[] args) Console.Write("请输入参赛选手的人数:\t"); int person = Convert.ToInt32(Console.ReadLine()); //参数检查合法性 if (person % 2 != 0) Console.WriteLine("输入的人数必须是2的倍数!"); return; //因为我定了只能容纳8位选手的日程的比赛安排,多的话就会爆掉 if (person 8) Console.WriteLine("对不起,最多8位选手"); return; //调用分值计算函数 GameCal(1, person); Console.Write("\n编号\t"); //最后就是将数组表头 for (int i = 1; i person; i++) Console.Write("第{0}天\t", i); //换行 Console.WriteLine(); //输出数组内容 for (int i = 0; i person; i++) for (int j = 0; j person; j++) Console.Write("{0}\t", GameList[i, j]); Console.WriteLine(); Console.ReadLine(); /// summary /// 分治计算 /// /summary /// param name="index" 起始选手编号 /param /// param name="num" 选手的人数(因为是分治,所以每次砍半) /param static void GameCal(int index, int num) //如果人数为2,则说明已经分治到了最简问题 if (num == 2) //参赛选手编号 GameList[index - 1, 0] = index; //对阵选手编号 GameList[index - 1, 1] = index + 1; //参赛选手编号 GameList[index, 0] = index + 1; //对阵选手编号 GameList[index, 1] = index; else //折半递归 GameCal(index, num / 2); //折半递归 GameCal(index + num / 2, num / 2); /* 子问题都结束后就要想办法合并,根据发现的规律进行合并 */ //用于将“左下角”填充到“右上角” //控制横坐标 for (int i = index; i index + num / 2; i++) //控制“纵坐标” for (int j = num / 2; j num; j++) //对角赋值 GameList[i - 1, j] = GameList[(i - 1) + num / 2, j - num / 2]; //用于将“左上角”填充到“右下角” //控制横坐标 for (int i = index + num / 2; i index + num; i++) //控制纵坐标 for (int j = num / 2; j num; j++) //对角赋值 GameList[i - 1, j] = GameList[(i - 1) - num / 2, j - num / 2]; }
课外闲谈9.谈一谈分治法和在线处理等常见方法 将整个问题分解成若干个小问题后再分而治之。如果觉得得到的子问题的规模还是太大,那就继续分解,直到得到的子问题规模达到要求。必要时逐步合并这些子问题的解,从而得到问题的解。
相关文章
- 算法洗脑系列(8篇)——第七篇 动态规划
- 算法系列15天速成——第八天 线性表【下】
- 算法系列15天速成——第一天 七大经典排序【上】
- Java实现 蓝桥杯VIP 算法提高 欧拉函数
- Java实现 蓝桥杯VIP 算法训练 和为T
- JAVA-蓝桥杯-算法训练-字符串变换
- POS DES MAC 算法
- 一步步教你轻松学决策树算法
- 【程序员眼中的统计学(6.1)】原创实现几何分布算法以及应用
- (算法)扔棋子
- matlab 等间距抽稀算法
- [YOLOv7/YOLOv5系列算法改进NO.16]主干网络C3替换为轻量化网络PP-LCNet
- [YOLOv7/YOLOv5系列算法改进NO.15]网络轻量化方法深度可分离卷积
- [YOLOv8/YOLOv7/YOLOv5系列算法改进NO.5]改进特征融合网络PANET为BIFPN(更新添加小目标检测层yaml)
- YOLO系列(YOLOv5/YOLOv7/YOLOv8)算法训练数据集保姆级教程
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.62】结合NeurIPS 2022年GhostnetV2网络模块
- 【YOLOv8/YOLOv7/YOLOv5/YOLOv4/Faster-rcnn系列算法改进NO.58】引入DRconv动态区域感知卷积
- 【YOLOv7/v5系列算法改进NO.46】融合DLinkNet模型中协同双注意力机制CDAM2
- Atitit 前端算法技术体系总结 目录 1. 3. Ui方面的算法 32 3.1. 软键盘算法 计算软键盘上下左右按键位置 32 3.2. Sprire生成随机位置算法 随机数算法 3
- Py之scikit-learn:机器学习sklearn库的简介、六大基本功能介绍(数据预处理/数据降维/模型选择/分类/回归/聚类)、安装、使用方法(实际问题中如何选择最合适的机器学习算法)之详细攻略
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-选择排序
- 【数据结构与算法Python实践系列】5分钟学会经典排序算法-快速排序
- 【数据结构与算法】用 golang 实现 LSM Tree 代码
- openssl之EVP系列之1---算法封装
- 白话经典算法系列之七 堆与堆排序
- 算法培训