B_M

算法课

Codeforces(5) java课(7) 分治(1) 动态规划(1) 图论(1) 数学(11) 数据结构(2)

/ 注册

全部文章 / 算法课（共13篇）

算法课-圆排列问题

问题给出一个若干个圆，将他们放到矩形框中，与矩形框的下底面相切，圆与圆之间不可以相交，求一个圆的排列方式使得所有圆中最左侧的点到最右侧的点距离水平距离最小解析计算两圆左右两侧距离如图所示，对于现切的两个圆，他们两个圆心之间的距离可以通过勾股定理计算，设距离为则，而对于如图所示的两圆最远端...

2020-06-10

0 1540

算法课-图染色问题

问题给出一个个点的连通图,用至多种颜色对图上每个点进行染色，要求任意两个有边直接相连的点不可以同色，染色方案数有多少种，输出方案数，若不存在这样的染色方案输出解析本题可以使用分支限界的方法来计算，尝试对每个点进行染***r>剪枝的情况： 1.如果当前尝试染色的点已经有颜色，则不需要继续...

2020-06-09

0 919

算法课-哈夫曼编码

问题给出一些字符和这些字符的出现频率，对这些字符用二进制进行编码，使得任意一个编码不是另一个编码的前缀，且编码的加权长度和最小。解析显然对于出现频率高的字符用更短的二进制进行编码，对出现频率低的字符用更长的二进制进行编码会得到编码加权长度和最小的结果。这个问题可以用哈夫曼编码树来解决。哈夫曼编...

2020-05-18

0 733

算法课-相容问题

问题给出若干个节目在同一个舞台演出，每个节目需要占用一段时间的舞台，用起始时间和结束时间表示。不同的节目占用舞台的时间不可以有重叠，如何安排可以被安排上的节目数量最多。解析对所有节目按照结束时间升序排列，按顺序排列不冲突的节目，最终得到的就是不冲突节目数量最多的安排证明：定理1：设时间区间...

2020-05-04

0 585

算法课-LCS最长公共子序列

问题给出两个序列,求出一个序列使得同时是和的子序列，且的长度最大解析给出一个动态规划的做法令表示序列的前项和序列的前项的最长公共子序列那么就有最优子问题证明已知是序列的前项和序列的前项的最长公共子序列当时，假设存在,则即存在与已知不符，假设不成立当时，假设存在,则与已知不符，假设不成...

2020-04-27

0 563

算法课-矩阵链乘法

问题给出一个长度为的序列表示个矩阵其中分别表示第个矩阵的行和列将个矩阵按顺序相乘，最少需要做多少次乘法解析对于行列分别为和的两个矩阵相乘，共需要次乘法同时对于矩阵乘法，满足结合律但不满***换律，即例如：对于序列表示矩阵按照原顺序，总运算次数为先对后两项做乘法，总运算次数为显然不同的...

2020-04-20

0 579

算法课-动态规划

问题给出个投资项目，每个项目有种投资方式第个项目第种投资方式需要花的钱，最后会得到的钱现在你有共有总量为的钱，合理分配，最终最多能赚多少钱解析令表示前个项目共花费元能够得到的最大价值则选择第个第种投资方式能得到的最大价值应该是证明:的任意一个确定状态的子决策都是此状态下的最优决策已知是前个...

2020-04-13

0 1922

算法课-第k小分治算法

问题给出序列求出其中第小的元素解析这里给出分治算法的做法按个一组对整个序列分组排序，选出每组中的中间项对所有的中项进行排序，选出中位数用中位数进行划分所有比中位数小的放到中位数前面，比中位数大的放到中位数后面若前面的数少于个，则在后半部分寻找第个，其中表示前半部分的元素个若前面的...

2020-04-05

0 582

算法课-平面最近点对

问题给出平面上一系列点，求任意两点之间欧几里得距离的最小值解析记作两点之间的欧几里得距离暴力做法很容易想到对这个问题暴力求解的方法，对于每一个点,计算它与其余所有点之间的距离，取最小值即可时间复杂度为分治策略首先按照分治策略的基本套路，一般都是将问题分解为若干个子问题，然后将子问题的...

2020-03-28

0 2887

算法课-归并排序

问题二分归并排序：对个不同的数构成的数组进行排序，其中解析归并将任意的两个升序序列和合并为一个升序序列主要步骤比较序列中的首元素和序列中的首元素若则将加到序列末尾，否则将加到序列末尾重复以上操作直到序列或序列为空将非空序列直接加到序列末尾正确性证明对于升序序列和，将两个序列的首元素分别记为和...

2020-03-22

0 495