一、递归和分制策略
汉诺塔递归实现：
Void hannoi(int n,char x,char y,char z)
{
if (n ==1)
move(x,1,z);//printf(“%i Move disk %i from %c to %c \n”,++c,n,x,z)
//将编号1从x移到z
else{
hanoi(n-1, x,z,y);//将x上编号1至n-1的移到y，z做辅助
move(x,n,z);// 将编号n从x移到z
hanoi(n-1, y,x,z);// 将y上编号1至n-1的移到z，x做辅助
}
}
递归小结
优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
解决方法：在递归算法中消除递归调用，使其转化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了
本来由编译器做的事情，优化效果不明显。
2.用递推来实现递归函数。
3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。
排序总结
直接插入排序：
void insertSort(listtp & r)
{ for(i=2; i<=n; i++)
{ r[0]=r[i]; /* 设置监视哨*/
j=i-1; k=r[i].key;
while(j>0&&r[j].key>k)/* 大值的记录后移*/ { r[j+1]=r[j]; j--; }
r[j+1]=r[0]; /*插入位置*/
}
} /* straisort */
希尔排序：将整个序列划分成若干子序列，分别进行直接插入排序。
void ShellSort(SeqList R,int dlta[],int t)
{
For(k=0;k ShellInsert(R，dlta[k])； //一趟增量为dlta[k]的Shell插入排序 } //ShellSort { for(i=dk+1; i<=n; i++) { r[0]=r[i]; /* 设置监视哨*/ j=i-dk; k=r[i].key; while( r[j].key>k)/* 大值的记录后移*/ { r[j+dk]=r[j]; j-=dk; } r[j+dk]=r[0]; /*插入位置*/ } } /* straisort */ 冒泡排序： void buble_sort(listtp r) { for (i=1; i<=n-1; i++) /* 共计n-1趟 */ for (j=1; j<=n-i ; j++) if (r[j].key>r[j+1].key) { x=r[j]; r[j]=r[j+1] r[j+1]=x;} } /* bubble_sort */ 快速排序：在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每 次移动的距离较大，因而总的比较和移动次数较少。private static void qSort(sqlist & L,int low, int high) { if (low int pivotloc=partition(L,low,high); //以a[pivotloc]为基准元素将a[low:high]划分成3段a[low: pivotloc -1],a[pivotloc]和a[pivotloc +1:high]，使得a[low: pivotloc-1]中任何元素小于等于a[pivotloc]，a[pivotloc +1:high]中任何元素大于等于a[pivotloc]。下标pivotloc在划分过程中确定。 qSort (L,low, pivotloc-1); //对左半段排序 qSort(L, pivotloc+1,high); //对右半段排序 } } Int Partition(sqlist &L,int low,int high) { L.r[0]=L.r[low];//用子表第一个元素作为轴 Pivotkey = L.r[low].key; While(low { While(low High--; If(L.r[high].key R[low]=r[high]; While(low Low++; If(L.r[low].key>privotkey) R[high]=r[low]; } L.r[low]=L.r[0]; Return low; } 归并排序： public static void mergeSort(Comparable a[], int left, int right) { int m = (left+right)/2; //取中点 if(left>=right) return; if(left+1==right) { if(a[left]>a[right]) std::swap(a[left], a[right]); return; } mergeSort(a, left, m); mergeSort(a, m+1, right); merge(a, left,m, right); //合并到数组a } } void Merge(A[], int l, int m, int h) { int i = l; int j = m+1; int k = 0; while(i<=m&&j<=h) { if(A[i] { B[k++] = A[i]; i++; } else { B[k++] = A[j]; j++; } } while(i<=m) B[k++] = A[i++]; while(j<=h) B[k++] = A[j++]; for(i=l; i<=h; i++) A[i] = B[i-l]; } 二分法： #include #define N 10 using namespace std; int main() { int a[N],front,end,mid,x,i; cout<<"请输入已排好序的a数组元素:"< for(i=0;i cin>>a[i]; cout<<"请输入待查找的数x:"< cin>>x; front=0; end=N-1; mid=(front+end)/2; while(front<=end&&a[mid]!=x) { if(a[mid] if(a[mid]>x)end=mid-1; mid=(front+end)/2; } if(a[mid]!=x) cout<<"没找到！"< else cout<<"找到了！在第"< return 0; } 二叉树递归、非递归遍历 package edu.cumt.jnotnull; import java.util.Stack; public class BinaryTree { protected Node root; public BinaryTree(Node root) { this.root = root; } public Node getRoot() { return root;
