文章 44
浏览 11238
编译原理笔记(4)

编译原理笔记(4)

编译原理第四章笔记

谱聚类再次整理

谱聚类再次整理

常读常新啊,又更新一次,理解又加深一次!

编译原理笔记(3)

编译原理笔记(3)

编译原理第三章笔记

最小生成树算法

最小生成树算法

引入问题 首先来看这样一个问题 现有村落间道路的统计数据表中,列出了有可能建设成标准公路的若干条道路的成本,求使每个村落都有公路连通所需要的最低成本。 输入格式: 输入数据包括城镇数目正整数 N(≤1000)和候选道路数目 M(≤3N);随后的 M 行对应 M 条道路,每行给出 3 个正整数,分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见,城镇从 1 到 N 编号。 输出格式: 输出村村通需要的最低成本。如果输入数据不足以保证畅通,则输出 −1,表示需要建设更多公路。 根据题目的描述,我们可以得知这是一道图论的题目,图为带权无向图,边上的权值即为题中描述的道路修建成本。 现在需要我们根据已有的图,求该图的最小(权值和最小)生成树。 这时候就需要引入解决问题的最小生成树算法了。 Prim 算法思路 首先读入所有的边,边的数据结构是一个结构体,主要包括:起点、终点、权值。 读入边之后按照边的权值由小到大排序。初始化一个数组记录边加入生成树的状态,初始时全部边为未加入。再初始化一个数组记录结点加入生成树的情况。 将某一个结点加入生成树(改变状态标志),因为所....

编译原理笔记(2)

编译原理笔记(2)

编译原理第二章笔记

整型数二进制1的个数

整型数二进制1的个数

这是由BBfat推荐给我的一道经典面试题

编译原理笔记(1)

编译原理笔记(1)

编译原理第一章的笔记

模板题——连续子序列和的最大值

模板题——连续子序列和的最大值

题目: 给定一个长度为 n 的整形数组 nums,求从数组索引 l 至 索引 r 的整数序列中,连续序列和的最大值为多少。 思路: 本题的主要思路,可分为两种 使用遍历的思想,遍历出序列的每种情况,逐一求和,计算最大值 但这种思路及其耗费时间,不可取。 使用动态规划的思想,使用一个数组 dp 记录,从索引 l 起包含位置 k 连续序列和的最大值 (l<=k<=r),最大值可由下面的公式推导。 dp[k] = max{ num[k] , num[k] + dp[k-1] } 公式解释: 这个公式的意思很明了,即某个位置之前的序列和若为正,那么包含之前的序列,肯定会使包含当前位置的序列和增大。 这个公式不好理解之处在于,若一个位置的值为负还要包括他吗?举个例子来说明: 若位置 i 处值为负,之前序列和为正,那么虽然包括了他使到这个位置为止的序列和减小,但是起到了连接 i+1 位置的作用,若 i+1 位置的值很大,那么包含 i 位置使序列和减小的损失就可以忽略了,因为到 i+1 处的序列和是增大的了。 若之前序列和为负,那么包含之前序列就没有任何意义,到 i ....