梦开始的地方开始了^_^
递归：直接或间接地调用自己的算法
最典型的就是汉诺塔问题：

汉诺塔

设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则:
规则1∶每次只能移动1个圆盘;
规则2:任何时刻都不允许将较大的圆盘压在较小的圆盘之上;
规则3:在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上

void hanoi(int n, int a, int b, int c){
if (n > 0){
hanoi(n-1, a, c, b); //把最上面n-1个盘子从a移到c,借助b
move(a,b); //把a最底下那个大盘子移到b去
hanoi(n-1,c, b, a); //把c上的全部n-1个盘子移到b，通过a
}
}

分治法

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

• 该问题的规模缩小到一定的程度就可以容易地解决;
• 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
• 利用该问题分解出的子问题的解可以合并为该问题的解;
• 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

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

二分查找技术

给定已按升序排好序的n个元素a[0:n-1],现在这n个元素中找出一个特定的元素x
int BinaerSearch(Type a[],const Type& x,int l,int r){
while(r>=){
int m=(l+r)/2;
if(x==a[m]) return m;
if(xelse l=m+1;
}
return -1; //没找到
}
总共查找logN次

合并排序

用分治策略实现对n个元素进行排序的算法，将待排序的元素分成大小大致相同的两个子集，分别对两个子集进行排序，最后将排序好的子集合并成要求的排好序的集合。
void MergeSort（Type a[],int left,int right）{
if(leftint i=(left+right)/2;
MergeSort(a,left,i);
MergeSort(a,i+1,right);
Merge(a,b,left,i,right); //合并到数组b
Copy(a,b,left,right); //复制回数组a
}
}

快速排序

对于输入的子数组a[p:r],按以下三个步骤进行排序：

1. 分解：以a[p]为基准元素，将a[p:r]分为三段，a[p:q-1],a[q],a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于a[q]。下标q在划分过程中确定。
2. 递归求解：通过递归调用快速排序算法，分别对a[p:q-1]和a[q+1:r]进行排序
3. 合并：合并a[p:q-1]和a[q+1:r]，不需要执行任何计算，因为两个数组已经排序好了

void QuickSort(Type a[],int p,int r){
if(pint q=Partition(a,p,r);
QuickSort(a,p,q-1); //对左边进行排序
QuickSort(a,q+1,r); //对右边进行排序
}
}
Partition函数用于产生下标q.