什么是算法

算法就是用来解决问题的，它有五大特性：

输入
输出
有穷性：有限个步骤和有限的时间内完成
确定性：
可行性

欧几里得算法：

#include<iostream.h>
int CommonFactor(int m, int n)
{
	int r = m % n ;
	while ( r != 0 )
	{
		m = n;
		n = r;
		r = m % n ;
	}
	return n;

}
void main( )
{
cout<<CommonFactor(63,54)<<endl;
}

概述

算法是一种方法论，它有一般的方法步骤，也有一定的前提条件，如果要解决的问题能够很好的满足这个前提条件那么这个算法对解决这个问题来说，它的效率是很高的（中医管这个叫“对症下药”）。

几种算法：

基本的（如何求出最优解，怎么求的算法？）：蛮力法、分治法、减治法、动态规划法和贪心法
搜索的（最优解已经有了，如何找到最优解，怎么找的算法）：回溯法和分支限界法

重要的问题类型

查找问题
排序问题
图问题
组合问题
几何问题

算法是用来解决问题，不能将算法和问题混淆。

每一种算法都可以解决问题，不过就是效率和优化的问题。

分述

能否一个算法不能很好地解决这个问题，然后用多种算法联合起来解决这个问题？所以重要的不是汉诺塔，而是汉诺塔背后的算法思想

蛮力法

简单而又直接，暴力求解问题，也可以说是穷举

分治法

分治法的精髓：

分–将问题分解为规模更小的相同的子问题；

治–将这些规模更小的子问题逐个击破；

合–将已解决的子问题合并，最终得出“母”问题的解；

个人感觉分治法和递归有点相像。

分治法所能解决的问题一般具有以下几个特征：

\1) 该问题的规模缩小到一定的程度就可以容易地解决

\2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

\3) 利用该问题分解出的子问题的解可以合并为该问题的解；

\4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；

第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；

第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。

第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

减治法

减治法是分治法的一种。

分治法是把一个大问题划分为若干个子问题，分别求解各个子问题，然后再把子问题的解进行合并得到原问题的解。

减治法同样是把一个大问题划分为若干个子问题，但是这些子问题不需要分别求解，只需求解其中的一个子问题，因而也无需对子问题的解进行合并。

所以，严格的说，减治法应该是一种退化了的分治法，时间复杂性一般是O(log2 n)。——程序员麻辣烫

动态规划法

什么是动态规划1？

什么是动态规划2？

动态规划算法最核心的思想是：递归？

当你企图使用计算机解决一个问题时，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！ ——摘自知乎王勐的回答

动态规划感觉有点一根筋啊，能不能两头堵啊？哈哈哈

动态规划虽然和分治法类似，都是将一个问题分为多个子问题，对子问题求解，然后从这些子问题中找到原问题的解，但是不同之处在于动态规划的子问题往往不是相互独立的，这就要记录并保存多个子问题的答案，如何记录保存呢？那就是建个表然后存入，既然要建表所以该算法的空间复杂度要比一般算法大得多，所以它本质是一种以时间换空间的算法。

适用动态规划的问题必须满足最优化原理(最优子结构性质)和无后效性。

最优化原理：最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质

无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性

整几个经典问题练练手：