- 理解递归的概念
- 掌握设计有效算法的分治策略
- 学习分治策略的设计技巧
文章目录
- 二、递归与分治策略
- 2.1 递归的概念
- 2.2 分治法的基本思想
- 2.3 二分搜索技术
- 2.4 大整数的乘法
- 2.5 Strassen矩阵乘法
- 2.6 棋盘覆盖
- 2.7 合并排序
- 2.8 快速排序
2.1 递归的概念
直接或者间接调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
示例：
int factorial(int n){
if(n == 0) return 1;
else return n*factorial(n-1);
}
说明：
边界条件与递归方程是递归函数的两个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
递归算法的优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性。
递归算法的缺点：递归算法的运行效率较低。
2.2 分治法的基本思想
概念：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归地解子问题，然后将各子问题的解合并得到原问题的解。
示例：
divide-and-conquer(P){
if(|P| <= n0)
adhoc(P);
divide P into smaller subinstances P1,P2,...,Pk;
for(i = 1; i<=k; i++)
yi = divide-and-conquer(Pi);
return merge(y1,y2,...,yk);
}
2.3 二分搜索技术
例：给定已按照升序排好序的n个元素a[0:n-1]，现在要在这n个元素中找出一特定元素x。
template2.4 大整数的乘法 2.5 Strassen矩阵乘法 2.6 棋盘覆盖int BinarySearch(Type a[], const Type& x,int n){ int left = 0; int right = n-1; while(left <= right){ int middle = (left + right) / 2; if(x == a[middle]) return middle; if(x > a[middle]) left = middle + 1; else right = middle - 1; } return -1; }
算法思路：
void chessBoard(int tr, int tc, int dr, int dc, int size){
if (size==1)
return;
int s = size/2; //分割棋盘
int t = ++num; //L型骨牌号,全局变量
if (dr < tr + s && dc < tc +s){ //覆盖左上角子棋盘
chessBoard(tr,tc,dr,dc,s); //特殊方格在此棋盘中
}
else{ //此棋盘中无特殊方格
Matrix[tr+s-1][tc+s-1] = t; //用t号L型骨牌覆盖右下角
chessBoard(tr,tc,tr+s-1,tc+s-1,s); //覆盖其余方格
}
if (dr < tr + s && dc >= tc + s ){ //覆盖右上角子棋盘
chessBoard(tr,tc+s,dr,dc,s); //特殊方格在此棋盘中
}
else{ //此棋盘中无特殊方格
Matrix[tr+s-1][tc+s] = t; //用t号L型骨牌覆盖左下角
chessBoard(tr,tc+s,tr+s-1,tc+s,s); //覆盖其余方格
}
if (dr >= tr + s && dc < tc + s){ //覆盖左下角子棋盘
chessBoard(tr+s,tc,dr,dc,s); //特殊方格在此棋盘中
}
else{
Matrix[tr+s][tc+s-1] = t; //用t号L型骨牌覆盖右上角
chessBoard(tr+s,tc,tr+s,tc+s-1,s); //覆盖其余方格
}
if (dr >= tr + s && dc >= tc + s){ //覆盖右下角子棋盘
chessBoard(tr+s,tc+s,dr,dc,s); //特殊方格在此棋盘中
}
else{
Matrix[tr+s][tc+s] = t; //用t号L型骨牌覆盖左上角
chessBoard(tr+s,tc+s,tr+s,tc+s,s); //覆盖其余方格
}
}
2.7 合并排序
基本思想：将n个元素分成2个大小相同的子集合，分别对子集合进行排序，最终将排好序的子集合合并为有序集合。n=1时中止。
MergerSort()函数用于将数组分成两个大小相同的子集合。
void MergeSort(int arr[],int left,int right){
int middle = 0; //定义中间值
if(left
middle = (left+right)/2; //取左右值的中间值
MergeSort(arr,left,middle); //递归调用
MergeSort(arr,middle+1,right); //递归调用
Merge(arr,left,middle,right); //合并排序
}
Merge()函数用于合并排好序的两个子集合。
void merge(int arr[],int left,int middle,int right){
int k;
int left_min = left;
int left_max = middle;
int right_min = middle+1;
int right_max = right;
int *b = (int *)malloc((right-left+1)*sizeof(int)); //定义临时数组，并申请内存空间
for(k=0;left_min<=left_max&&right_min<=right_max;k++){
if(arr[left_min] //如果数组左边的值比右边的小，就把值添加到b中，反之添加右边的值
b[k] = arr[left_min++];
}else{
b[k] = arr[right_min++];
}
}
if(left_min<=left_max){ //如果比较完，左边还有剩余，就把剩余的值复制到数组后边
for(int i=left_min;i<=left_max;i++){
b[k] = arr[i];
k++;
}
}
if(right_min<=right_max){ //如果比较完，右边还有剩余，就把剩余的值复制到数组后边
for(int i=right_min;i<=right_max;i++){
b[k] = arr[i];
k++;
}
}
for(int i=0;i
arr[left+i] = b[i];
}
free(b);
}
2.8 快速排序
基于分治策略的排序
在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大（小）的记录一次就能交换到后（前）面单元，总的比较和移动次数较少。
QuickSort()函数用于将数组分解成三部分，分别为左半段、右半段和本身元素。
templatevoid QuickSort(Type a[], int p, int r){ if(p < r){ int q; q = Partition(a, p, r); QuickSort(a, p, q-1); QuickSort(a, q+1, r); } }
Partition()函数用于将本体元素放到正确的位置，并返回位置下标。并且将左边大于本体元素的元素与右边小于本体元素的元素交换位置。
templateint Partition(Type a[], int p, int r){ int i =p, j = r+1; Type x = a[p]; // 将小于x的元素交换到左边区域，将大于x的元素交换到右边区域。 while(true){ while(a[++i] < x && i < r); while(a[--j] > x); if(i >= j) break; Swap(a[i], a[j]); } a[p] = a[j]; a[j] = x; return j; }
