本帖最后由 轻舟过 于 2012-5-1 16:10 编辑
不太清楚是不是适合发到这个版
其实相比与编程语言来说，算法是更像魔法一般的存在。
简介
维基百科上对“算法”的定义是“指完成一个任务所需要的具体步骤和方法"。也就是给定一定的输入，能够得到所要求的输出的方法。
虽然现在算法时常和计算机一同被提到，实际上算法在计算机产生的很久以前就已经产生了，它在古代被称为“术”，最早出现在《周髀算经》、《九章算术》，尤其是特别是《九章算术》，给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法，线性方程组求解的算法。三国代的刘徽给出求圆周率的算法：刘徽割圆术。
在计算机技术迅速发展的今天，我们更是在有意无意之间接触到各种算法。比如在使用word的时候，查找替换就是使用了字符串匹配的算法，word会帮你纠错也是因为实现了相应的纠错算法。社交网络中的好友推荐、matlab中数值计算、google检索网页都用到了特殊的算法。一般编程语言自带的库中也实现了各种常用的数据结构和算法，像C++中的STL就实现了链表、平衡查找树、优先队列等数据结构。在平时写程序之前使用算法分析的方法，估算下自己的方法能不能在较短时间内出解以及是否能得到正确的解，就能避免为不好的方法编码而浪费时间。
可以说，算法不管是在计算机的各个领域中，还是在现代技术的革新中都承担了重要的角色。个人感觉算法有很多有趣的地方，不过也有非常考验思维的地方。
最大公约数算法
举个最简单求最大公约数的算法来说明，这里输入是两个数a,b，输出是a和b的最大公约数。
算法1
很直观的方法是从min(a, b)开始枚举，直到遇到能同时整除两个数的数为止，代码如下：
[mw_shl_code=cpp,true]int gcd(int a, int b) {
for(int i = min(a, b); i > 0; --i) {
if(a % i == 0 && b % i == 0)
return i;
}
return -1;
}[/mw_shl_code]
上面的方法需要测试的数是min(a, b)个，需要做2*min(a,b)次求余操作
算法2
其实我们初中就学过的一个求最大公约数的算法叫做辗转相除法，就是每次将大的数对小的数取余，用得到的余数替换掉大的数，一直这么做下去，直到某次整除了那个数就是要求的最大公约数。实现的代码如下，我个人非常喜欢这个代码实现：
[mw_shl_code=cpp,true]int gcd(int a, int b) {
return (a == 0 ? b : gcd(b % a, a));
}[/mw_shl_code]
这个算法中求余等操作的次数比较难以计算，直观地来讲，算法1在a、b大于1e8的时候就比较慢了，而算法2在引入大数运算之后甚至可以用于a、b等于1e100，1e1000数量级的运算。
可以看到，不同的算法在运行效率上有质的差别，一般算法分析上会用时间复杂度和空间复杂度来衡量一个算法的好坏，关于这两者，下次再说吧。
最后有个问题大家可以思考讨论下：
Fibonacci数开始两项为1，后面每一项为前面两项之和，即f(1)=1, f(2)=1； f(n) = f(n - 1) + f(n-2) n >= 3
规模不断扩大的几个问题
1. 求第15个Fibonacci数
2. 求第1007个Fibonacci数除以1e9+7的余数（这里求余数是为了避免大数运算）
3. 求第1e9+3个Fibonacci数除以1e9+7的余数