递归是一种使用相同的方法，通过解决问题的子集以达到解决整个问题的方法，是一种使用有限代码解决“无限”计算的方法。在C/C++语言中递归表现在函数对自身的直接/间接的调用上，在实现上，递归依赖于语言的运行时调用堆栈，使用堆栈来保存每一次递归调用返回时所需要的条件。递归通常具有简洁的编码和清晰的思路，但这种简洁是有代价的。一方面，是函数调用的负担；另一方面，是堆栈占用的负担（堆栈的大小是有限的）。
避免这种负担的方法就是将递归转化为迭代。迭代的思想主要在于，在同一栈帧中不断使用现有数据计算出新的数据，然后使用新的数据来替换原有数据。递归于迭代可以相互转化。将递归转化为迭代需要做两方面的工作：显式地维护一个堆栈，在递归算法中堆栈的维护由编译器隐式地完成；使用迭代控制结构，完成出栈、入栈和相关的计算。
Archive for ‘之算法神奇’ Category
April 29, 2011
October 18, 2010
简单实现了常见的几种内部排序算法，包括冒泡（Bubble），插入（Insert），快速排序（Quick Sort），堆排序（Heap Sort），归并（Merge），希尔排序（Shell Sort），并对这些算法的耗时在伪随机数上进行了简单的测试。
说明：
- 没有实现计数、基数排序等线性复杂度的算法；
- 各算法只是对算法思想的一次简单模拟，没有过多的优化；
- 各排序主程序接口参数均为整型数组及元素个数；
- 程序计时使用了glibc的gettimeofday()，因此。。。；
- 归并排序中，每次调用都申请和释放堆空间，因此比较耗时。可以采用原地归并、使用全局/静态的方法加以优化；
- 快速排序中，对待排子序列的长度进行的了判断，对短序列进行优先排序可以减小函数的递归深度（而不是次数）；
- 希尔排序中，为了简洁，步长因子统一取做2.2（11/5）。
May 6, 2010
Bellman-Ford算法简述
Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。这时候，就需要使用其他的算法来求解最短路径，Bellman-Ford算法就是其中最常用的一个。该算法由美国数学家理查德•贝尔曼（Richard Bellman, 动态规划的提出者）和小莱斯特•福特（Lester Ford）发明。Bellman-Ford算法的流程如下：
给定图G(V, E)（其中V、E分别为图G的顶点集与边集），源点s，
- 数组Distant[i]记录从源点s到顶点i的路径长度，初始化数组Distant[n]为
, Distant[s]为0； - 以下操作循环执行至多n-1次，n为顶点数：
- 对于每一条边e(u, v)，如果Distant[u] + w(u, v) < Distant[v]，则另Distant[v] = Distant[u]+w(u, v)。w(u, v)为边e(u,v)的权值；
- 若上述操作没有对Distant进行更新，说明最短路径已经查找完毕，或者部分点不可达，跳出循环。否则执行下次循环；
- 为了检测图中是否存在负环路，即权值之和小于0的环路。对于每一条边e(u, v)，如果存在Distant[u] + w(u, v) < Distant[v]的边，则图中存在负环路，即是说改图无法求出单源最短路径。否则数组Distant[n]中记录的就是源点s到各顶点的最短路径长度。
可知，Bellman-Ford算法寻找单源最短路径的时间复杂度为O(V*E).
May 4, 2010
有码有真相，各位看官您上眼：
1 2 3 4 5 6 | int main() { bar(++foo(372)); //~ 此行报错 bar(++foo(wrap_int(372))); //~ 无错 return 0; } |
第一个bar调用中foo返回int型临时对象，想要把这个int临时对象++后传给bar，未遂。第二个bar调用中，foo返回一个包装过的int, 即wrap_int，对这个临时对象进行++(重载)，得逞。结论：C++中，基本类型（内置类型）的临时对象不可以作为左值（l-value），即不可以修改；用户自定义类型的临时对象可以作为左值。
April 30, 2010
现有一个数列
，另有一个栈Stack和一个队列Queue，Stack与Queue初始为空。现对S中元素依次进行如下操作：
- 若Stack为空，则从S中取出一个元素入栈；
- 若Stack非空，则有两种选择：将栈顶元素弹出并入队，或者从S中取出一个元素入栈；
- 若S元素已经取完则操作结束，否则执行操作1或2。
问最终队列Queue有多少种排列情况？聪明且见识广博的你或许一下子就可以说出答案：
现在对这个结果进行证明。
设1表示入栈操作，0表示出栈操作。那么上面对n个元素的入栈和出栈操作就构成了长度为2n的由0和1组成的序列，其中1和0的个数均为n个，在没有任何限制的情况下，一共有
个这样的序列。但是，这里的01序列是建立在一些列的入栈出栈操作的基础上的，因此就会受到入栈、出栈操作的限制。这里，唯一的限制就是栈为空时，无法进行出栈操作。反映到这个01序列中就是，任意位置之前，0的个数都能比1的个数多。因为有了01序列的总数，所以为了找出满足条件的序列的个数，只需要找出不符合条件的序列的个数。
April 20, 2010
Dijkstra算法简述
Dijkstra算法是图论中的一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：集合T包含所有当前已经找到最短路径的点，初始情况下T中只有源点U = V – T，其中V为图G的点集。从源点开始，每次新扩展一个属于U、距离T中点最短的点，用该点更新U中的与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。若要处理含有负权值边的情况，就需要使用Bellman-Ford算法了。
Dijkstra算法流程
在以下说明中，start为源，Adj[u,v]为点u和v之间的边的长度，结果保存在Closest[]
- 初始化：源的距离Closest[start]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。
- 以下过程循环n-1次：
在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。
对于每个与u相邻的点v，如果Closest[u]+Adj[u,v] < Closest[v]，那么把Closest[v]更新成更短的距离Closest[u]+Adj[u,v]。此时到点v的最短路径上，前一个节点即为u。 - 结束。此时对于任意的u，Closest[u]就是start到u的距离。
April 19, 2010
一个无向、加权、连通图的生成树是指这样一棵树，它包含该图所有的n个顶点，和该图边集E中的n-1个边。最小生成树就是该图所有生成树中各边权值之和（构造代价）最小的生成树。求指定图的最小生成树有多种算法，除了这里要介绍的Kruskal算法，还有Prim算法、Sollin算法等。
Kruskal算法描述
用Kruskal算法为无向加权连通图G构造最小生成树T的步骤如下：首先初始化T为一个包含所有n个顶点、0个边的森林，E为G的边集。每次从E中取出一条具有最小权值的边（并从E中删除该边），如果该边不与T中其他边构成回路，则将该边加入T，否则舍弃该边。重复上述操作至T中含有n-1条边，此时T即Kruskal算法构造出的最小生成树。
Kruskal算法证明
易证，对于一个无向加权连通图，总是存在一棵或以上的有限课生成树，而这些生成树中肯定存在至少一棵最小生成树。下面证明Kruskal算法构造的生成树是这些最小生成树中的一棵。
设T为Kruskal算法构造出的生成树，U是G的最小生成树。如果T==U那么证明结束。如果T != U，我们就需要证明T和U的构造代价相同。由于T != U，所以一定存在k > 0条边存在于T中，却不在U中。接下来，我们做k次变换，每次从T中取出一条不在U中的边放入U，然后删除U一条不在T中的边，最后使T和U的边集相同。每次变换中，把T中的一条边e加入U，同时删除U中的一条边f。e、f按如下规则选取：a). e是在T中却不在U中的边中最小的一条边；b). e加入U后，肯定构成唯一的一个环路，令f是这个环路中的一条边，但不在T中。f一定存在，因为T中没有环路。
April 14, 2010
设”此物”为x，则x满足同余方程组：
若存在x满足上述方程组，则
也满足该方程其中k任意整数，方程的最小正整数解满足
，即对3,5,7的最小公倍数求余。
在介绍求x的具体方法之前，先介绍两个简单的定理(证明从略)：
- 被除数增加(或减少)除数的倍数，除数不变，则余数电不变；
- 被除数扩大(或缩小)指定的倍数，除数不变，则余数扩大(或缩小)同样的倍数(余数总小于除数)。
April 10, 2010
首先，你知道下面的语句的语义是什么吗？
int (a); |
或许写成这样你会更明白一点：
int (a) = 0; |
它等同于
int a = 0; |
November 17, 2009
对最简单的SDBMHash(char*)做了一个简单的测试。随机生成200个长度为31的字符串，利用SDBM得到一个Hash值，然后用直接取余法插入长度为113的HashSet，为简单起见，只是将HashSet对应的位置进行加一。
1 2 3 4 5 6 7 8 9 10 11 | // SDBM Hash Function unsigned int SDBMHash (char *str) { unsigned int hash = 0; while (*str) { hash = (*str++) + (hash << 6) + (hash << 16) - hash; } return (hash & 0x7FFFFFFF); } |