动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
Read the rest of this entry »

多阶段决策过程最优化问题

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。

每个阶段中，都求出本阶段的各个初始状态到过程终点的最短路径和最短距离，当逆序倒推到过程起点时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果。
Read the rest of this entry »

Dijkstra’s algorithm use Fibonacci heap to implement
董明峰 2005/10/25
讨论内容：
(1)Dijkstra’s algorithm是解决single source shortest path问题的一种算法。single source shortest path是探讨从一个起始点s到其它每个端点v的最短路径。假设p[v]是用来存放从s到每个点v的最短距离，例如p[s]=0，代表从s到s的最短距离是0；假设总共有n个点，m个边(点到点的距离)所以必须要跑 n次，才可以算完每个点；而每次的计算包含两部分，一部分是求目前距离s最近的点(该点的p[v]值还不是最短距离的值)，另一部分是修改p[v]的值；举个例子：假设n = 4，求v1到其它每个点的最短距离，一开始初始化p[v1]=0，p[v2]=2，p[v3]=4，p[v4]=∞(如果一开始v1无法直接到达该点，必须透过其它点才可到达，p[v]值就给∞)；接着开始去跑n次循环，每次循环包含两部分：

Read the rest of this entry »

假定你有一点算法数据结构知识
如果没有的话,所有提到的内容请自行查找,
不推荐提问.

最后偶会说说为什么写这些东西,
为什么选择这些而没有选择另一些.

1 链表找环(探测环形链表) O(n)
A 拓扑排序,删0入度点
B DFS(经过一个点就标记,标记2次的即可判定为环)

2 半素数
(只要一个数能被分解成两个素数，那么这个数就是半素数)
注意时间空间的平衡.
输入N (2<=N<=1000000),输出Y或者N,每行一个,遇0结束

这里只讨论探查找第一个质因数的问题.
A 从 2 到 ceil(sqrt(N)) 取余数探查
B 筛质数,2-1000中的质数进行筛选 (因为对最大的N,ceil(sqrt(N))=1000)
C 小素数筛选,大素数使用 Miller-Rabin 测试

3 LCA(最近公共祖先,Least Common Ancestors) 和 RMQ(Range Minimum/Maximum Query)
Read the rest of this entry »

许多人(尤其指phpers)连基础的算法都不会.
更有许多人只会算法不会coding.

这方面让高中生给所有人做榜样.

陈启峰发现了一种BST(Binary Search Tree)的新实现方式,
命名为Size Balanced Tree(SBT).
(显然这是不容易的,学业压力中能够得到这样的成果)

SBT和其它BST一样,基本都支持以下操作.
insert,delete,find,rank,select,pred,succ

SBT最值得称道的就是它均摊O(1)的maintain操作.
正因为这样的维护操作,使它有着超过AVL的速度
(注:仅限于题目的测试,其它种类的BST没有经过严格的测试)
Read the rest of this entry »

堆结构是一种隐式数据结构（implicit data structure），用完全二叉树表示的堆在数
组中是隐式存贮的（即没有明确的指针或其他数据能够重构这种结构）。由于没有存贮结构信
息，这种描述方法空间利用率很高，事实上没有空间浪费。尽管堆结构的时间和空间效率都
很高，但它不适合于所有优先队列的应用，尤其是当需要合并两个优先队列或多个长度不同
的队列时。因此需要借助于其他数据结构来实现这类应用，左偏树（ leftist tree）就能满足这
种要求。

左倾树是一种二叉树，它的节点除了和二叉树的节点一样具有左右子树指针（left、right）外，还有两个属性：键值和距离（dist）。键值上面已经说过，是用于比较节点的大小。距离则是如下定义的：

一个具有空左子树或空右子树的节点称为外节点；一个节点的距离是这个节点到最近的外节点所经过的边的数目（最近的意思是边的数目最小），特别的，如果一个节点本身是外节点，则它的距离为0；而空节点的距离规定为-1（后面将会看到这样规定的理由）。在本文中，有时也提到一棵树的距离，这是指该树根节点的距离。
Read the rest of this entry »

一．摘要
本文将给出一个简单但非常有效率的多模式匹配算法，这个算法基于压
缩编码的思想。该算法在自左向右扫描文本的过程中，根据出现在输入模式
中的字符将文本中的字符进行编码。这个简单的扫描算法展示了同时处理大
量的输入模式的能力。我们的实验表明，在大多数情况下，我们的算法比当
前的多模式匹配算法(比如agrep, grep）有更快的执行速度。
Read the rest of this entry »

德国数学家Moritz Stern和法国钟表匠Achille Brocot提出了构造不可约分数集的方法，也就是Stern-Brocot tree.

A special type of binary tree obtained by starting with the fractions 0/1
and 1/0 and iteratively inserting (m+m’)/(n+n’) between each two adjacent
fractions m/n and m’/n’. The result can be arranged in tree form

构造这种树的主要思想就是从两个分数0/1和1/0开始，重复进行以下操作：
Insert (m+m’)/(n+n’) between two adjacent fractions m/n and m’/n’.

考虑这样一个问题：给定一个不可约分数m/n, 如何在这棵树上找到对应节点？
可以使用类似Binary search的方法，从树的根1/1开始，
如果m/n小于当前节点的数，那么就递归地遍历到左子树，记为L.否则R.
这样寻找后，我们就得到了一个类似LRLRLLRL…的串

题目: USACO Ordered Fractions
Read the rest of this entry »

费马小定理: 假如a是一个整数，p是一个质数，且a、p互素(a,p)=1, 则a^p≡1(mod p)

费马小定理只是个必要条件,符合费马小定理而非素数的数叫做Carmichael.
前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。
在1~100000000范围内的整数中，只有255个Carmichael数。

为此又有二次探测定理
二次探测定理 如果p是一个素数，0

Miller-Rabin算法的一般步骤:
Read the rest of this entry »

8.5最小生成树
最小生成村树有很多种解决方案，可以分为几类：
1.创建并扩展一些树，使它们合并成更大的树(Boruvka)
2.创建一个树的集构成一棵生成树(Kruskal)
3.创建并扩展一棵树，为它添加新的树枝(Prim)
4.创建并扩展一棵树，为它添加新的树枝，也可能从中删除一些树枝(Dijkstra)
Read the rest of this entry »