在一棵树中，从任意一个结点到达另一个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。若树中结点带有表示某种意义的权值，那么从根结点到达该节点的路径长度再乘以该结点权值被称为该结点的带权路径长度。树所有的叶子结点的带权路径长度和为该树的带权路径长度和。给定n个结点和它们的权值，以它们为叶子结点构造一棵带权路径和最小的二叉树，该二叉树即为哈夫曼树，同时也被称为最优树。给定结点的哈夫曼树可能不唯一，所以关于哈夫曼树的机试题往往需要求解的是其最小带权路径长度和。回顾一下我们所熟知的哈夫曼树求法（原理很容易理解，就是把小的往下放）。1.将所有结点放入集合K。2.若集合K中剩余结点大于2个，则取出其中权值最小的两个结点，构造他们同时为某个新节点的左右儿子，该新节点是他们共同的双亲结点，设定它的权值为其两个儿子结点的权值和。并将该父亲结点放入集合K。重复步骤2或3。3.若集合K中仅剩余一个结点，该结点即为构造出的哈夫曼树数的根结点，所有构造得到的中间结点(即哈夫曼树上非叶子结点)的权值和即为该哈夫曼树的带权路径和。为了方便快捷高效率的求得集合K中权值最小的两个元素，我们需要使用堆...

算法总结-深搜由于是深度优先，后进入的结点需要先读取，因此选取堆栈实现，在栈中保存从起始结点（状态）到当前结点的路径上的所有结点。一般用递归实现。非递归框架DFS(){初始化栈while(栈不为空&未找到目标结点){取栈顶元素扩展，扩展出的结点放回栈顶}......}递归框架在深度优先搜索中，状态空间的图结构并不一定需要显式地保存下来。typenode;voidDFS(intdepth){for(node的每一个可行变化){改变nodeDFS(depth+1)恢复node}}该做法需要一个全局数组array来存放每个走过的node，array[depth]就是进入DFS函数时需要扩展的结点。  ...

算法总结-广搜（BFS：breadth-firstsearch）广度优先搜索算法（用QUEUE）把初始节点S0放入Open表（待扩展表）中；如果Open表为空，则问题无解，失败退出；把Open表的第一个节点取出放入Closed表，并记该节点为n；考察节点n是否为目标节点。若是，则得到问题的解，成功退出；若节点n不可拓展，则转第2步；扩展节点n，将其不在Closed表和Open表的子节点（判重）放入Open表的尾部，并为每一个子节点设置指向父节点的指针（或记录节点的层次），然后转第2步；（详见刘家瑛课程PPT，结合CatchThatCow）广搜和深搜的比较广搜一般用于状态表示比较简单、求最优策略的问题。一层一层的搜，每一条路径的搜索进度都是一样的，因此需要用到队列的知识，不需要使用递归.优点：是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。缺点：盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大。深搜几乎可以用于任何问题，一条路搜到底，不能再往下了，就回溯一步...

算法总结-递归定义：所谓递归即函数直接或间接地调用函数本身，调用的方式按照问题的不同人为定义，这种调用方式被称为递归方式。同时，为了不使这样的递归无限的发生，我们必须设定递归的出口，即当函数达到某种条件时停止递归。问题的求解过程->划分成相同性质的子问题的求解->子问题的求解过程可以很容易地求出->这些子问题的解就构成原问题的解。递归和枚举的区别：枚举——把一个子问题划分成一组子问题，依次对这些子问题求解。子问题之间是横向的，同类的关系；递归——把一个问题逐级分解成子问题。子问题与原问题之间是纵向的，同类的关系。注意：使用递归函数务必注意递归的层数。一个程序可以使用的栈空间是有限的，当递归的过深或者每层递归所需的栈空间太大将会造成栈的溢出，使评判系统返回程序运行时异常终止的结果，一旦你的递归程序出现了这种错误，你就要考虑是否是由递归的太深而造成了爆栈。这是使用递归程序一个很重要的注意要点。具体可使用的栈大小，每个评判系统不同而有所差异，需要自行测试后确定。套路：待求解问题的解->输入变量x的函数f(x)通过寻找函数...

算法总结-枚举定义：依次尝试搜索空间中所有的解，测试其是否符合条件，若符合则输出答案，否则继续测试下一组解。注意：在使用枚举这种相对较为暴力的解法来进行解题时，我们对其时间复杂度要做特别的关注。枚举问题的时间复杂度往往与需要枚举的情况个数有关，因为我们必须不遗不漏地枚举每一种可能成为答案的情况。所以搜索空间越大，枚举的时间复杂度就越高。所以，我们在对某一问题进行枚举时，必须保证其时间复杂度在题目时限可以接受的范围内。在复杂度允许的范围内，直白的枚举思路简单，代码清晰，在一些看似无从下手的题目面前，我们可以换个角度，试着从更暴力的角度去思考。套路：给出解空间，建立简洁的数学模型：找出解对应的可能情况，使模型中的变量数尽可能少，它们之间相互独立减少搜索的空间：利用知识缩小模型中各变量的取值范围，避免不必要的计算。采用合适的搜索顺序：搜索空间的遍历顺序要与模型中条件表达式一致。例题：百鸡问题#include<iostream>usingnamespacestd;intmain(){intn;while(cin>>n){for(intx=0;x<=100;x++)...

动态规划-背包问题此博客分别讨论0-1背包，完全背包和多重背包，并给出相应的解题模板。0-1背包题目：有一个容量为V的背包，和一些物品。这些物品分别有两个属性，体积w和价值v，每种物品只有一个。要求用这个背包装下价值尽可能多的物品，求该最大价值，背包可以不被装满。 0-1背包问题：在最优解中，每个物品只有两种可能的情况，即在背包中或者不在背包中（背包中的该物品数为0或1），因此称为0-1背包问题。步骤1-找子问题：子问题必然是和物品有关的，对于每一个物品，有两种结果：能装下或者不能装下。第一，包的容量比物品体积小，装不下，这时的最大价值和前i-1个物品的最大价值是一样的。第二，还有足够的容量装下该物品，但是装了不一定大于当前相同体积的最优价值，所以要进行比较。由上述分析，子问题中物品数和背包容量都应当作为变量。因此子问题确定为背包容量为j时，求前i个物品所能达到最大价值。步骤2-确定状态：由上述分析，“状态”对应的“值”即为背包容量为j时，求前i个物品所能达到最大价值，设为dp[i][j]。初始时，dp[0][j](0<=...

动态规划（DP：DynamicProgramming）动态规划是求解包含重复子问题的最优化方法，把原问题分解为相对简单的子问题。动态规划只能应用于有最优子结构的问题（即局部最优解能决定全局最优解，或问题能分解成子问题来求解）。基本思想将原问题分解为相似的子问题，再合并子问题的解以得出原问题的解。动态规划在求解的过程中通过保存子问题的解求出原问题的解（而不是简单地分而治之），仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。动态规划=记忆化搜索分治与动态规划共同点：二者都要求原问题具有最优子结构性质,都是将原问题分而治之,分解成若干个规模较小(小到很容易解决的程序)的子问题.然后将子问题的解合并,形成原问题的解.不同点：分治法将分解后的子问题看成相互独立的，通过用递归来做。　　　　 动态规划将分解后的子问题理解为相互间有联系,有重叠部分，需要记忆，通常用迭代来做。问题特征最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优...

一，算法介绍在CS124课程的第一周提到求解两个字符串相似度的算法---MinimumEditDistance（最短编辑距离）算法。该算法在NLP（自然语言处理）中也会用到。如何定义相似度呢？任给两个字符串X和Y，使用以下三种操作将字符串X变到字符串Y ：①插入(Insert)操作；②删除操作（delete）；③替换操作(substitute)比如字符串X="intention"， 字符串Y="execution"。从字符串X转换成字符串Y如下图所示： 定义：插入操作的代价为1，删除操作的代价为1，替换操作的代价为2（称为：Levenshteindistance）。那么，"intention" 变成 "execution"执行了三次替换，一次删除，一次插入。因此，总代价为8而这个代价又称为编辑距离，用之来衡量两个字符串的相似程度。显然，若两个字符串越相似，则从一个字符串变到另一个字符串所需要的“操作”步骤就越少。 二，动态规则求解最短编辑距离为什么能用动态规划来求解呢？ⓐ该问题可以分解成若干个子问题；ⓑ...

 分类：js（4443）（0）零：数据准备，给定数组arr=[2,5,4,1,7,3,8,6,9,0];一：冒牌排序1思想：冒泡排序思想：每一次对比相邻两个数据的大小，小的排在前面，如果前面的数据比后面的大就交换这两个数的位置    要实现上述规则需要用到两层for循环，外层从第一个数到倒数第二个数，内层从外层的后面一个数到最后一个数2特点：排序算法的基础。简单实用易于理解，缺点是比较次数多，效率较低。3实现： [html]viewplaincopy var times=0;  var bubbleSort=function(arr){      for(var i=0;i<arr.length-1;i++){          for(var j=i+1;j<arr.length;j++...

计算1-100之间的所有奇数的和classProgram{staticvoidMain(string[]args){intsum=GetOdd(1,100);Console.WriteLine("1-100之间所有奇数整数和{0}",sum);Console.ReadKey();}///<summary>///奇数和///</summary>///<paramname="p1"></param>///<paramname="p2"></param>///<returns></returns>privatestaticintGetOdd(intp1,intp2){intsum=0;for(inti=p1;i<=p2;i++){if(i%2!=0){sum+=i;}}returnsum;}}  求1-100之间的所有质数（素数）的和：所以先必须知道什么是质数？一个数是不是素数  “素数”是指除了能被1和自身整除外，不能被任何其...

现在网上下载的软件大部分都需要注册后才能使用其全部的功能，也就是说当前大部分软件都是建立了注册机制的，对于一个刚进入软件行业的程序员来说一定非常想了解其中的注册机制是怎样实现的。其实用VC开发软件，是可以很方便地加入注册机制的。　　要实现软件注册功能，首先需要知道实现注册机制要涉及到的几个问题：1、如何加入注册检测，判断软件是否注册；2、如何生成注册码，如何保证一个用户名只生成与之唯一对应的注册码；3、在软件不注册情况下，如何限制软件功能的局限性；4、对已经负费使用用户而言，不应造成使用不便。　　首先，应该有一个生成注册码的算法，以下是我简单的一个生成15为注册码的算法：//该函数返回一个CSTRING类型的15位注册码，入口参数为用户名CStringGetRegPasswd(CString&DirName){//将用户名换算成15位注册码longNum1,Num2,Num3;charsn[16]={0};CStringp;inti,len;Num1=0;Num2=0;Num3=0;len=int(strlen(DirName));if(len!=0){for(i=1;i<...

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。重复以上过程，仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到最大数前的一对相邻数，将小数放前，大数放后，第二趟结束，在倒数第二个数中得到一个新的最大数。如此下去，直至最终完成排序。 由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。 用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i,j的值依次为1,2,...10-i。产生 在许多程序设计中，我们需要将一个数列进行排序，以方便统计，常见的排序方法有冒泡排序，二叉树排序，选择...

参考：https://blog.csdn.net/androidlushangderen/article/details/44889677倒排索引：一般的索引检索信息的方式。比如原始的数据源假设都是以文档的形式被分开，文档1拥有一段内容，文档2也富含一段内容，文档3同样如此。然后给定一个关键词，要搜索出与此关键词相关的文档，自然而然我们联想到的办法就是一个个文档的内容去比较，判断是否含有此关键词，如果含有则返回这个文档的索引地址，如果不是接着用后面的文档去比，这就有点类似于字符串的匹配类似。很显然，当数据量非常巨大的时候，这种方式并不适用。原来的这种方式可以理解为是索引-->关键词，而倒排索引的形式则是关键词--->索引位置，也就是说，给出一个关键词信息，我能立马根据倒排索引的信息得出他的位置BSBI：Blockedsort-basedindexing  https://nlp.stanford.edu/IR-book/html/htmledition/blocked-sort-based-indexing-1.html1、将文档中的词进行id的映射，这...

1.基础力导向算法1.1算法模型FR算法模型建立在粒子物理理论的基础上，将无向图的节点模拟成原子，通过模拟原子间的力场来计算节点间的相对位置。该模型假设任意两个节点间存在斥力，相互连接的两个节点间存在引力。通过模拟节点间的相互作用力，计算得到节点的速度和偏移量，经过不断的迭代计算，最终达到一种动态平衡的状态。1.2算法思路（1）计算任意两点间的相互斥力。（2）计算有边连接的节点间的相互引力。（3）根据节点所受的合力计算速度，将速度转化为节点位置偏移量，此时注意通过最大偏移量限制移动距离，防止偏移过大无法收敛。（4）根据偏移量计算每一个节点的位置。（5）经过多次迭代，最终达到动态平衡，节点位置近似不变。 1.3伪代码2.改进1:引入模拟退火算法优化结束条件2.1引入模拟退火算法的原因在基础力导向算法中，由于迭代次数是外部指定的参数。在不同拓扑结构的无向图而言，达到收敛的迭次次数不同。如果迭代次数过大，相应的计算耗时也会这增加，存在一些多余的迭代过程。如果迭代次数过小，此时算法还没有收敛，会导致节点分布不均衡，效果不理想。因此，需要引入一种机制来控制算法迭代终止的条件。 ...

Dijkstra算法是图论中经典的最短路径算法之一，主要用于解决单源最短路径问题。单源最短路径问题,即求某个源节点到其他各个节点的最短路径。Dijkstra算法采用了贪心算法的思想，如图求1号节点到其他各个节点最短路径。首先从1号节点出发，扩展已知的最短路径集合，每次优先“松弛”最近的节点所相连的边，直到所有扩展范围覆盖全部，所得即最优结果。由于负权值使得上一次最优结果积累失效，所以Dijkstra算法不能解决负权路问题。  ...