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

编译原理笔记(1)

编译原理第一章的笔记

故障树分析(FTA)

故障树分析(FTA)

故障树分析,就是选择某一故障作为顶层事件,逐步拆解事件为中间事件,直到事件无法拆解变为底层事件。拆解事件的过程可以画成一棵树,这棵树也就称为故障树,利用故障树分析底层事件对故障发生影响的重要程度称为故障树分析。 建树符号 事件符号 逻辑符号 结构函数 底事件状态 顶事件状态 可用与底事件有关的函数表示 计算 或门 $ \phi( T ) = \sum _ { i = 1 } ^ { n } { x _ i } $ 与门 $ \phi( T ) = \prod_{i = 1 }^{ n }{ x_i } $ 化简 $ T = x_1 ( x_1 + x_4 ) x_3 = x_1 x_3 + x_1 x_4 x_3 = x_1 x_3 $ 最小割集 最小割集是指,是指让顶层事件发生的最少数量的底层事件集合 例: 顶层事件 T 可以表示为 化简为 根据表达式为或运算,则可知有 4 个最小割集,为: 路集:是割集的对偶集合,也即不触发发生顶层事件的底层事件集合 顶层事件概率的计算 将顶层事件表示为,最小割集的形式 $ ....

关于动态规划的一点小想法

关于动态规划的一点小想法

最近一直在做动态规划的题,也算有了一些自己的小感悟,暂时总结一下 首先看一道例题 题目链接 描述 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角,出口在右下角。 小明被带到地宫的入口,国王要求他只能向右或向下行走。 走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。 当小明走到出口时,如果他手中的宝贝恰好是 k 件,则这些宝贝就可以送给小明。 请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k 件宝贝。 输入 输入一行 3 个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12) 接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 输出 要求输出一个整数,表示正好取 k 个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。 输入样例1 2 2 2 1 2 2 1 输出样例1 2 输入样例2 2 3....

编译原理笔记(6)

编译原理笔记(6)

编译原理笔记——语义分析

编译原理笔记(5)

编译原理笔记(5)

编译原理第五章笔记

最短路径

最短路径

计算图的最短路径有几种经典的算法: 弗洛伊德(Floyd)算法 迪杰斯特拉(Dijkstra)算法 贝尔曼福德(Bellman-Ford)算法 SPFA 算法 弗洛伊德算法 弗罗伊德算法的思想来自于动态规划。 基本思路为: 我们知道若给定任意结点 A、B,若想使两点之间的距离减小只有引入第三个点。 首先引入 结点 1 ,是否能使任意两个结点之间距离缩短呢?若能则更新距离。接着引入 结点 2 ,是否能在结点 1 的基础上继续缩短距离呢?这样一直到 结点 N。 因为每次引入 结点 i+1 都是在 结点 i 的基础上,所以最终的结果就是任意两点间的最短距离。 算法模板: cin>>n>>m; //n为节点数,m为路径数 for(i=0;i<m;i++){ cin>>begin>>end>>len; route[begin][end]=len; //读入路径 } for(int k=1;k<=n;++k){ for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j){ if....

分页寻址

分页寻址

文章借鉴 内存寻址之分页机制 与 内存分页、寻址方式那些事 写在前面 分页与分段机制 分段机制是Intel CPU一直保持的机制,而分页机制在80x86的计算机中是一种可选的机制,但只有在保护模式下才存在这种机制,也就是说保护模式下才存在分页寻址的机制,但保护模式不一定开启分页寻址机制. 内存碎片化问题: 进程A进来,向os申请了200的内存空间,于是os把0~199分配给A 进程B进来,向os申请了5的内存空间,os把200~204分配给它 进程C进来,向os申请了100的内存空间,os把205~304分配给它 这个时候进程B运行完了,把200-204还给os但是很长时间以后,只要系统中的出现的进程的大小>5的话,200-204这段空间都不会被分配出去(只要A和C不退出)。过了一段更长的时间,内存中就会出现许许多多200-204这样不能被利用的碎片 分页的原因 解决内存碎片化问题,分页机制将虚拟内存空间和物理内存空间划分为同样大小的单位-页面,并以页面作为最小分配单位,然后将内存按照页为单位进行内存分配,这样一段内存空间就可以属于很多进程.内存在虚拟中为连续的,物理中离散....

最小生成树算法

最小生成树算法

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

整型数二进制1的个数

整型数二进制1的个数

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

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

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

题目: 给定一个长度为 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 ....