B_M

分类

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

/ 注册

全部文章（共41篇）

算法课-圆排列问题

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

2020-06-10

0 1540

算法课-图染色问题

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

2020-06-09

0 919

算法课-哈夫曼编码

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

2020-05-18

0 733

算法课-相容问题

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

2020-05-04

0 585

数学-卡特兰数

卡特兰数卡特兰数的基本公式通项公式变形公式递推公式基本形式给出个元素，其中个元素，个元素，要求对于由两种元素按顺序排列组成的序列中，任意一个前缀的数量不少于,有多少种组合方式个节点的二叉树共有多少个可以将一棵二叉树分为根，左子树，右子树三部分，枚举左子树节点个数，则共有种不同的二叉树

2020-04-28

0 518

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

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

2020-04-27

0 563

数学-miller_rabin测试

miller_rabin素性测试给出一个非常大的数，判断它是不是素数对于较小的数，可以枚举内每一个数试除，若能整除则非素数，这么做的复杂度为对于较大的整数，如级别的数，不够用了所以去学了一下miller_rabin测试法miller_rabin测试法是一个随机算法，虽然不能保证完全正确，但是判断6...

2020-04-21

0 598

算法课-矩阵链乘法

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

2020-04-20

0 579

算法课-动态规划

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

2020-04-13

0 1922

算法课-第k小分治算法

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

2020-04-05

0 582