算法笔记2——摩尔投票法(Boyer–Moore majority vote algorithm)

1、简要概述

摩尔投票法(Boyer–Moore majority vote algorithm)出自论文，算法解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。常见的算法是扫描一遍选票，对每个候选人进行统计的选票进行统计。当候选人的数目固定时，这个常见算法的时间复杂度为：O(n)，当候选人的数目不定时，统计选票可能会执行较长时间，可能需运行O(n^2^)的时间。当选票有序时，可以很容易编出O(n)的程序，首先找到中位数，然后检查中位数的个数是否超过选票的一半。这篇论文针对无序且侯选人不定的情形，提出了摩尔投票算法。算法的比较次数最多是选票（记为n）的两倍，可以在O(n)时间内选出获票最多的，空间开销为O(1)

==摩尔投票法的一大应用就是求众数==。

算法笔记1——链式前向星+SPFA+Dijkstra

题目链接：[P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)]

1、题目描述（入门）

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

jQuery笔记

1、JQuery介绍

• JQuery是JavaScript和查询（Query），它就是辅助JS开发的类库
• 核心思想：写得少做的多，所以它解决了很多浏览器的兼容问题
• 流行程度：是目前最流行的JS库
• 优点：免费、开源，语法设计使开发更便捷，例如操作文档对象、选择DOM元素、制作动画效果、事件处理、使用Ajax以及其他功能

编译原理实验6——基于SLR(1)分析法的语法制导翻译及中间代码生成

1、语法制导翻译

​ 对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或规约时，语法分析程序除执行相应的语法分析动作之外，还要执行相应地语义动作或语义子程序。每个语义子程序都指明了相应产生式中各个符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义动作。

2、实验内容

基于SLR(1)文法，完成以下描述赋值语句语法制导生成中间代码三地址码的过程。

• G[E]：
  S→V=E

  E →E+T∣E-T∣T

  T→T*F∣T/F∣F

  F→(E)∣i

  V→i

编译原理实验5——SLR(1)文法分析器实现

1、代码功能：

（1）计算非终结符的FIRST和FOLLOW集

（2）构造SLR分析表

（3）判断该文法是否为SLR文法

（4）输入字符串，按照SLR分析法判断该字符串的语法是否正确，并给出判断过程