1.汉诺塔问题
汉诺塔问题的由来：一位法国数学家曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
程序员看来就是一个求总移动次数的问题（也可以顺便打印移动顺序），用递归/分治的思路就是f(n)=2*f(n-1)+1；下面给出打印移动顺序的代码：
#include <stdio.h>
void move(int,char,char,char);
int main()
{
printf("Please input the Tower of Hanoi's number:\n");
int m;
scanf("%d",&m);
move(m,'A','B','C');
}
/*
XYZ分别代表三根柱子
*/
void move(int m,char x,char y,char z)
{
if(m==1)
{
printf("%c->%c\n",x,z); //如果只有一个金片了，那么我们直接将其从X移至Z即可。
return;
}
move(m-1,x,z,y); //先将m-1个金片从X移至Y。此步骤即整体代换
printf("%c->%c\n",x,z);//每次递归时，我们总是将1号金片移至Z。
move(m-1,y,x,z); //再将整体代换的m-1个金片从Y移至Z
}
2.算法分析
分治法所能解决的问题一般具有以下几个特征：
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；
4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；
第二条特征是应用分治法的前提它也是大多数问题可以满足的，此特征反映了递归思想的应用；、
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
第四条特征涉及到分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
这个相较动归来说还比较简单，粘一些过来 实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。 1、一定是先找到最小问题规模时的求解方法 2、然后考虑随着问题规模增大时的求解方法 3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。