您现在访问的是

算法驿站 powered by 编程爱好者网站

这个小站是我修读《信息与计算科学》本科时就自己所学到的所感受的东西留于笔下，开始不叫这名字，后来才慢慢感觉到‘算法’的威力，而‘驿站’是指作者我也是在学习，大家一起学习的这个过程。

有这样一种说法，先不说它的正确与准确性，至少还是有些道理的，就是，程序=数据结构+算法，程序就是一段指令，看看现在的计算机技术，从硬件的描述语言，汇编，高级语言，脚本，其实可以都认为是‘程序’，及程序就是计算机的全部，就算你是做硬件的人，你用CAD吧，你会从逻辑门开始设计吗？可编程逻辑器件，什么Intel8253之类，你做单片机，你会从汇编开始吧，或者是C语言，你不会去做那个片（我国国内好像还不能做'片'），拿到一堆APIs就开始干活，无非是2个8位拼成16位，还不就是做程序，好，你做程序员，就算你做系统程序员，你写个OS之类的，下面也是用别人做好的指令，你不会去设计微指令吧，流水线也不用管，cache也透明，剩下的东西，还不就是编程，做应用程序员，站在XP上干活，站在linux上干活，到你去做的事情，还是编程。我想说的是，‘程序’可以代替一个词‘逻辑’，而逻辑就是计算机的全部，至少当前的冯计算机，不同的只是大家所处的层次不同（越低级的人越少，但是我不同意越赚钱）。

而程序是=数据结构+算法，数据结构是精心地准备好数据，将那些信息以一定的形式一定的逻辑组织在一起，以使算法的效用达到最大，算法是所有程序的核心，可以看成程序本身，也可以这样比，算法是无形的，而程序是有形的，不管你如何实现，算法是发挥最大作用的东西，而程序是算法的某个实例。

做IT这行，只要是做技术的，只要把算法学好，动手能力强，不管做哪一行（计算机行也分很多）都会很吃香，剩下的只是工具的问题，实现的具体环境，熟能生巧嘛，越是高级的工具其实越容易上手，少数可能门槛比较高，但也都没有算法本身重要。

好了不多说了，本文是想把小站的内容做个链接，做个目录，以下是目录。

目录

1 基础算法

排序由浅入深（一）::选择排序
排序由浅入深（二）::交换排序
排序是算法的切入点，这两篇可能也没什么深度，现在看，那些个经典的排序算法，要时刻牢记于心，那会是一种算法设计泛型，比如快排，归并，基数排序，桶排等。

穷举搜索::回溯与深搜
分酒问题-搜索解法
就是一个DFS，图的深度搜索，基础。后面是一个好玩的例子。

贪心算法::启发式搜索
马踏棋盘的贪心算法
当时有些不太清楚，其实贪心和启发式还是有区别的，贪心是一种分阶段决策，和DP很是相同，但是更简单，往往只要从一个有序元组中依次选择决策，或从堆中动态选择，常见的最小支撑树啊，最短路径Dijkstra，都算是贪心，贪心算法现在还没有充要条件可以判别，就是在何时可以贪心。启发式，实际上就是做局部最优选择，可以是在搜索过程中，比如那个马遍历,但他不同于多阶段决策。

分治的实现::递归程序设计
想表述一下‘递归’的思想，分治的思想是整个算法设计的精髓，最简单的二分，二进制，有很多优秀的或者说伟大的算法里都有这些思想的影子，比如FFT，快排等。

最短带权路径问题的解法::Dijkstra & Floyd
两个确定的基本的最短路径算法。

公历历法::星期算法
当时研究出来比较兴奋，也没学初等数论的基础，中国人应该了解一下同余理论，扫扫盲吧。这个算是很简单的，比起证明费马小定理是不是容易很多。

满足任意精度的概率事件发生器
产生任意范围内的等概率随机数
满足任意概率密度函数分布的随机变量生成算法
这三篇的水平只能算是中学对概率理解的水平，当时还没学《概率论》，对随机数的发生，其实现在还不完全了解，应该是用相关度描述的，至于很好的随机数发生器，要到了专门学密码学的时候才会了解到，不知道有没缘了。第三个，其实早有了蒙特卡罗方法，只要有了U[0，1]的随机数，再知道了概率函数的反函数，就可以简单模拟了，但实际中有很多概率函数是积分形式，反函数没有简单形式，就只好单独对待了，比如高斯分布，有一个函数变换的方法和一个蒙特卡罗方法，有时间写一篇吧。

树的计数公式推导
这个叫catalan数，写的时候还不知道这东西，和离散卷积有关系。

CRC循环冗余校验码
好像是计算机网络时学的，后来又学信息论认识到了，一种线性分组码。

模式匹配的KMP算法详解
带通配符*,?的模式匹配
模式匹配基础东西。如果是模式识别，以我现在的数学水平还不够研究。后一篇有BUG，感谢那位网友指出来。

最长递增子序列问题的求解（LIS）
我转来的一篇，重复的东西也不用写了，写得很好。

Euclid算法与RSA
主要是讲如何求解同余方程xa=1(mod b)的Euclid算法。有一位网上朋友联系过我，说用我的代码不能过OJ，他也没发现问题在哪，如果你发现了，请告诉我。

基础算法还缺一些内容，比如非常重要的程序设计泛型DP。

2 中级算法

和基础算法不同，有些算法比较偏，更像是某种数学或某个方面的专门算法。

最小二乘法线性回归
最小二乘算得上一种数学方法吧，用处非常广泛，又何止只能线性回归呢？我们泛涵考试的最后一题就是求L2[0,1]上exp(x)的最佳三次多项式，由于是2范线性空间，恰好就是最小二乘。

幂极数在近似计算上的应用
数学分析2考完时写的，算是我对数值分析的启蒙认识吧，用我们数分老师的话说，那门课就是‘泰勒级数打天下’，连续的东西化成离散的，其实都是相通的，理论数学慢慢向实用靠近了。

博弈与人工智能
最小最大原理与搜索方法
估值函数与优化搜索
置换表与迭代加深
一个暑假突然迷上了人机博弈，写得比较空洞，文章中没有具体代码。当时做了一个黑白棋，后来觉得估值估得好还真不容易，不过至少对一个没学过黑白棋的人是可以轻易下赢的，我让我大堂哥和她走，他的结论是很需要脑筋，经常被我的程序翻盘。听他评价我的程序，真是开心。PS，人机的对弈本质上还是搜索，对弈树的搜索。

了解遗传算法
就是简单的表达了一下，遗传算法是怎么样的，收敛性，收敛速度都没任何表述，还没到那水平。

关于人工神经网络
也是对神经网络非常朴实的认识。下学期有选这门专业课。在我看到的一篇论文里他和遗传算法、模拟退火算法、模糊数学一同被称为先进算法。可能是因为他们都是非常成功的算法，但都有一些理论上遗留的未解决的问题吧。

[转]模拟退火算法求解TSP问题
转载的，写得很通俗易懂，SAA用于组合优化的有效方法。

A*高效搜索算法
搜索方法小结
两篇讲搜索的。A*是一种带启发式高效搜索算法，它的启发式带有某种预见性，因此可看成是智能搜索算法。

牛顿插值算法与实现
多项式插值，牛插是很容易计算机实现的一种算法。

香农编码
照香农老大的说法，编码的平均最优码长是以它的信息熵为下界的，通常情况下，哈夫曼编码也不是最优编码，只能是近似最优，因为编码必须是整数个符号，而哈夫曼编码的缺点是编码长短不一，香农编码是另一种编码，还有扩展码等。

Romberg算法求数值积分的原理与实现
我已经在不止一次课程设计里使用过这个算法了。有着变步长，可控制精度，收敛速度快诸多优点。

Fibonacci数列的计算
比较了几种算法实现的优劣，主要是介绍一种矩阵算法。

Priority Queue - Binary Heap
FibonacciHeap的C++模板实现
优先队列，我最喜欢的数据结构之一。

单纯形法性规划问题求解器
LP问题的有效求解方法，虽然最差情况下是NP的，但LP问题不是NP的，相反有人提出的in P的算法在实际中还不如单纯形法有效。

简单方法算pi和e，计算到小数点后面一万位
FFT乘法和高精运算库(1)
FFT乘法和高精运算库(2)
高精度的算法。

解线性方程组的一些方法
直接消元的，迭代的，和一些解特殊方程的方法。

其它的还有一些OJ上的题解，但是我做得不多，没什么影响力，还有一些就是学工具的，比如VC啊之类，原谅我把这些也滥竽充数放在这里吧。

最后希望这个小站能够带您在算法的广阔空间里自由飞翔！再引一位网友的签名结尾吧：算法如此多娇,引无数天才竞折腰。

评论