plussai
- 浏览: 88409 次
- 性别:
- 来自: 杭州
-
最新评论
-
zhyawshhz：
顶上！我就是算缺少代码能力型的 ！
百度面试归~~我还是太年轻了。。。。 -
lanjf635241：
...
递归组合算法
文章列表
斐波那契散列法其实是一种特殊的乘法散列，先来看乘法散列.根据算法导论第2版中的定义，构造乘法散列函数包含两个步骤。第一步，用关键字k乘上常数A（0<A<1），并抽取出kA的小数部分。然后，用m乘以这个值，再结果的低。总之，散列函数为h(k)=[m(kA mod 1)]
一般来说，m取值为2^p，而A的取值为形如s/2^w的分数(w为计算机的字长,int32,long long 64)，那么简化之后h(k)=s*k的低w位中的高p位。
为了得到更好的随即性， knuth认为A去黄金分割数是一个比较理想的值，因此A=0.6180339887.... ...
本文大量参考：http://www.nocow.cn/index.php/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F
感谢：byvoid
首先，强连通分支是定义在一个有向图G上的。一个有向图的强连通分支就是一个最大的顶点集合， ...
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。
在zoj_2832中，map主要用来建立文件名（即字符串）和一个整数的关联，其中字符串为key,整数为value.
值得注意的一点是，代码34行注释中使用的map插入方法，出现BUG。当使用p[s]时，如果p中存在关键字为s的数据，返回对应的value,如果不存在p会自动建立一个关键字为s,value为0的数据。
zoj_2832
在zoj_3023中，无耻的利用了map内 ...
问题1：输入为一行字符串被中间被一些空格隔开，要求提取这些被空格隔开的字符串.
方法：直接使用cin，因为cin遇到空格附，换行附，\0，EOF等会停止输入
string s;
while(cin>>s)
{
cout<<s<<endl;
}
问题2：输入为一行字符串被中间被一些空格隔开，要求提取整行字符到一个字符数组中
方法：使用cin.get(char* p,int pcount)或者cin.getline(char*p int ...
针对Bellman-Ford算法效率比较低的问题，SPFA是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，有办法证明对于通常的情况，k在2左右。
值得注意的一点是，如果某个点进入队列的次数超过V次则图中存在负环（SPFA无法处理带负环的图）。
#include<iostream>
#include<vector>
#include<queue&g ...
Bellman-Ford算法的特点是能够解决带负权值的最短路径问题，并且实现起来比较简单。整个循环体循环V-1次，每次循环遍历图中的每一条边(u,v)，并对点V做松弛操作。可以证明，通过V*E次的操作，最后得到的dist[i]值就是从原点到点i的最短路径。具体的Bellman-Ford的正确性证明见《算法导论》
但是，Bellman-Ford算法有一种情况不能处理，即图中存在从源可达的负权回路。如果出现这种情况，我们可以绕这这个环无限次，得到的最短路径即为负无穷。所以，这种情况下的最短路径问题是没有意义的。在Bellman-Ford算法中，还有一个对每条边的 ...
今天细读了算法导论的21章不相交集合，也就是传说中的并查集，有点小收获。原来网上搜的并查集只介绍了路径压缩，今天第一次听说还有按秩合并这回事儿。算法导论上说，同时利用按秩合并和路径压缩技术处理，并查集的操作速度可以大大提升。设有一连串的make-set,find-set,union操作共m个，其中make-set有n个，在渐进意义上，这一连串的操作的时间复杂度为O(m*a(n))，a(n)是一个增长很慢的函数。具体证明不太懂，以后有时间再看。这里值得注意的一点就是union操作包含2个find-set操作和1个link操作。
再用并查集来分析一下kruskal算 ...
安全边：
在无向图G=(V,E)中，A是图G的某棵最小生成树T的子集，当把图G中的某条（u, v）边加入到A中后，如果AU(u, v)仍然是某棵最小生成树T’的的子集，边(u, v)被成为A的一条安全边
割：
在无向图G=(V,E)中，割（S, V-S
推论1：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,n) | b。 推论2：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a,n)，或者无解。 定理1：设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b，则方程ax=b(modn)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod(n/d)，最大整数解x2=x1+(d-1)*(n/d)。 定理2：假设方程ax=b(mod n)有解，且x0 ...
筛法打素数表是一种高效的打表方法，体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。c这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。需要注意的是，选取质数的时候，循环只需到sqrt(n)就可以。
与之前的简单打表相比，来分析一个两种方法的效率。
先看一下简单方法，对于每个需要 ...
循环从2开始，到sqrt(a)，每次判断a是否能被i整除，如果可以，则将i存如vector中，a/=i,然后--i，目的是继续判断i，因为a可能可以被i整除多次.到循环结束的时候，再将a存入vector中。
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int getSum(int a)
{
int res=0;
int q=a;
while(q!=0)
{
res+=q%10;
q/=10;
}
...
在一个具有几个顶点的连通图G中，如果存在子图G'包含G中所有顶点和一部分边，且不形成回路，则称G'为图G的生成树，代价最小生成树则称为最小生成树。
许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
算法为贪心思想，每次将距离最近的一个顶点入MST中，然后对剩余的顶点做松弛操作。MST算法可以使用有限队列来实现，使用二叉堆O(VlogV+ElogV),使用F ...
使用二叉堆来实现优先队列，可以应用与图的最短路径，最小生成树等算法。优先队列包含一下功能，buildHeap_MIN,效率为O(N), extract_MIN,效率为O(logN), decrease_key,效率为O(logN)等。
#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;
class node
{
public:
int key,value;
node()
{
key=-1;
value=-1 ...
分治思想求解，超时了分析了一下T(n)=O(n)+O(logn)*k(k可能渐进为n)
#include<iostream>
#include<stdio.h>
using namespace std;
int cases,total,sum;
const int maxm=100000;
int array[maxm];
int enumFind(int*array,int start,int end)
{
int mid=(start+end)/2;
for(int i=mid;i>=start;i--)
{
for(int j ...
huffman编码是一种优化的编码方法，于ASCII等固定长度的编码方法相比较，他可以使编码的长度缩短。其主要的思路是，让出现频率高的字符拥有较短的编码，让出现频率较低的字符，拥有较长的编码。但是，这样的编码方式就要求任意一个字符的编码不能是其他字符编码的前缀，通常这种编码方式叫前缀编码。 huffman编码通过构造huffmanTree来实现，贪心思想。取权值（频率）最低的2个节点为新节点的左右子节点，新节点的权值为子节点权值之和。处理之后，子节点标记为已经处理过，新节点标记为未处理。循环处理该过程。如果huffmanTree中有m个叶节点，那么huffmanTree中肯定有 ...