文档介绍：算法总结

穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的是穷举法，即将密码
11=3
while (nv=10)
!
f[n]=f[n-1 ]+f(n-2]
n=n+l
I
write(f[10])
递归法
在问题求解思想上，递推是从已知条件出发，一步步递推出未知项，直到问题的解。递归也是递推的一种，只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题，然后再一步步返回，从而得到原问题的解。
【斐波那契数列算法2］利用递归思想写出求斐波那契数列的递归算法。
分析：在问题求解中，求解同一个问题的方法通常不止一个。根据递归法的思想，由斐波那契数列递推公式可以很容易地写出递归算法，伪代码描述如下。
求斐波那契数列递归算法：
〃函数fib返回第n(n>=l)个斐波那契数列的值
int fib(int n)
(
if(n=l)
retum(l)
else
if(n ==2)
retum(2)
else return (fib(n-1 )+fib(n-2))
图33 3阶Haoojigi^归迥程示育图
分析：可以把问题用初始状态和目标状态来表达，问题求解就是要找出搬移的次序和所有的中间状态。
Hanoi塔问题递归算法:
〃n为盘子数目
〃三根柱子from、to和temp分别表示起始柱子、目标柱子和临时柱子
void hanoitower(n,from,to,temp)
if(n>0)
〃把from柱子上的n-1个盘子搬移到temp柱子上，用to柱做临时柱子 hanoitower(n-1,from,temp,to);
movedisk(from,to);
〃把temp柱子上的n-1个盘子搬移到to柱子上，用from柱做临时柱子 hanoitower(n-1,temp,to,from);
}
回溯法
试探-失败返回-再试探的问题求解方法称为回溯法，回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解(并不一定是完整的，事实上这也就是构造约束函数的意义所在)与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。
【八皇后问题】八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8 的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。
分析：显然，每一行可以而且必须放一个皇后，所以
n皇后问题的解可以用一个n元向量X= (xi,X2,.....xn) 表示，其中，l<=i<=n且l<=xi<=n,即第n个皇后放在第i行第Xi列上。
由于两个皇后不能放在同一列上，所以，解向量 X必须满足的约束条件为:制若两个皇后的摆放位置分别是(i,Xi)和(j,Xj),在棋盘上斜率为-1的斜线上，满足条件i-j=Xi-X」；在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj；
综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足的约束条件为：
li-" Ij-Xil
八皇后问题求解的回溯算法：
〃试探第i个皇后，即第i行要放置的皇后位置
void queen(int i)
fbr(j=O;jv8;j++)
〃从第0列开始从左到右依次试探可能的位置
if(a|j]=O&&c[i+j]==i0 〃如果无冲突
〃(i,j)放皇后，即第i行的皇后放在第j列
a[j]=l; 〃在j列标记
b[i-j+7]=l; 〃(i,j)所在的主对角线做标记
c[i+j]=l；〃(i,j)所在的从对角线做标记
if(i<7)queen(i+l); //如果行还没有遍历完，进入下一行
else输出当前的摆放方案，即q数组；
〃当前列摆放了皇后，要继续试探当前行下一个可能的位置，此时需要
〃将当前列恢复为没有摆皇后的状态，尝试下一个可能的摆放方案
q[i,j]='*'；
a[j]=O;
b[i-j+7]=0;
c[i+j]=O;