算法与数据结构(3)---分治与递归
递归算法:直接或者间接不断反复调用自身来达到解决问题的方法。要求原始问题可以分解为相同问题的子问题。
递归两个要素
1.递归边界
2.递归的逻辑——递归"公式"
列举一些例子
1 阶乘函数
n!=n(n-1)!
public static int factorial(int n){
if(n==0) return 1;
return n*factorial(n-1);
}
斐波那契数列
斐波那契数列的递推公式:Fib(n)=Fib(n-1)+Fib(n-2),指的是如下所示的数列:
1、1、2、3、5、8、13、21.....
按照其递推公式写出的递归函数如下:
1
2
3
4
5
6
7
8
|
public static int fib( int n) throws Exception {
if (n < 0 )
throw new Exception( "参数不能为负!" );
else if (n == 0 || n == 1 )
return n;
else return fib(n - 1 ) + fib(n - 2 );
} |
递归调用的过程像树一样,通过观察会发现有很多重复的调用。
讲完了递归 我们就可以讨论分治了。
分治
分治法有三个解题步骤,无论是简单的分治还是复杂的,都逃不开这个标准步骤。它们是:
- 拆解子任务
- 解决子任务
- 合并子任务的解
分治算法应用在方方面面,一般来说,解决子任务这一步骤相对容易,因为当子任务拆到规模一定小的情况下,解就会显得非常简单。分治算法的应用难点一般都会出现在拆解子任务与合并解的步骤上。
我们也是举几个例子来说明一些分治
例子1 二分搜索技术
1.二分查找又称折半查找,它是一种效率较高的查找方法。
2.二分查找要求:(1)必须采用顺序存储结构 (2).必须按关键字大小有序排列
3.原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后;将要查找的值和数组的中值进行比较,若小于中值则在中值前 面找,若大于中值则在中值后面找,等于中值时直接返回。然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分。
4.实现:二分查找的实现用递归和循环两种方式
例子2 棋盘覆盖 棋盘覆盖也是一个经典的分治
棋盘覆盖问题要求在2^k * 2^k 个方格组成的棋盘中,你给定任意一个特殊点,用一种方案实现对除该特殊点的棋盘实现全覆盖。
建立模型如图:
解决方案就是利用分治法,将方形棋盘分成4部分,如果该特殊点在某一部分,我们就去递归他,如果不在某一部分,我们假设一个点为特殊点,同样递归下去,知道全覆盖。
左上角的子棋盘(若不存在特殊方格):则将该子棋盘右下角的那个方格假设为特殊方格;
右上角的子棋盘(若不存在特殊方格):则将该子棋盘左下角的那个方格假设为特殊方格;
左下角的子棋盘(若不存在特殊方格):则将该子棋盘右上角的那个方格假设为特殊方格;
右下角的子棋盘(若不存在特殊方格):则将该子棋盘左上角的那个方格假设为特殊方格;
ps: 代码不写了。
例子3 合并排序
- //将有二个有序数列a[first...mid]和a[mid...last]合并。
- void mergearray(int a[], int first, int mid, int last, int temp[])
- {
- int i = first, j = mid + 1;
- int m = mid, n = last;
- int k = 0;
- while (i <= m && j <= n)
- {
- if (a[i] <= a[j])
- temp[k++] = a[i++];
- else
- temp[k++] = a[j++];
- }
- while (i <= m)
- temp[k++] = a[i++];
- while (j <= n)
- temp[k++] = a[j++];
- for (i = 0; i < k; i++)
- a[first + i] = temp[i];
- }
- void mergesort(int a[], int first, int last, int temp[])
- {
- if (first < last)
- {
- int mid = (first + last) / 2;
- mergesort(a, first, mid, temp); //左边有序
- mergesort(a, mid + 1, last, temp); //右边有序
- mergearray(a, first, mid, last, temp); //再将二个有序数列合并
- }
- }
- bool MergeSort(int a[], int n)
- {
- int *p = new int[n];
- if (p == NULL)
- return false;
- mergesort(a, 0, n - 1, p);
- delete[] p;
- return true;
- }
分治与递归就总结到这里吧。虽然简单,但是感觉还要自动多做练习,多写代码才能掌握。