(四)递归
2019-07-27 本文已影响0人
guideEmotion
一 概念
递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
规则
- 执行一个方法时，就创建一个新的受保护的独立空间(
栈空间) - 方法的
局部变量是独立的，不会相互影响, 比如n变量 - 如果方法中使用的是
引用类型变量(比如数组)，就会共享该引用类型的数据. - 递归必须向
退出递归的条件逼近，否则就是无限递归,出现StackOverflowError - 当一个方法
执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。
二 迷宫问题
image.png
代码实现-找到路
package com.zyc.recursion;
/**
* @author zhuyc
* @create 2019-07-27 8:54
*/
public class MiGong {
public static void main(String[] args) {
// 先创建一个二维数组，模拟迷宫
// 地图
int[][] map = new int[8][7];
// 使用 1 表示墙
// 上下全部置为 1
for (int i = 0; i < 7; i++) {
map[0][i] = 1; map[7][i] = 1;
}
// 左右全部置为 1
for (int i = 0; i < 8; i++) {
map[i][0] = 1; map[i][6] = 1;
}
//设置挡板, 1 表示
map[3][1] = 1;
map[3][2] = 1;
// map[1][2] = 1;
// map[2][2] = 1;
// 输出地图
System.out.println("地图的情况");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++)
{
System.out.print(map[i][j] + " ");
}
System.out.println();
}
//使用递归回溯给小球找路
setWay(map, 1, 1);
//setWay2(map, 1, 1);
// 输出新的地图, 小球走过，并标识过的递归
System.out.println("小球走过，并标识过的 地图的情况");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
//使用递归回溯来给小球找路
// 说明
// 1. map 表示地图
// 2. i,j 表示从地图的哪个位置开始出发 (1,1)
// 3. 如果小球能到 map[6][5] 位置，则说明通路找到.
// 4. 约定： 当 map[i][j] 为 0 表示该点没有走过 当为 1 表示墙 ； 2 表示通路可以走 ； 3 表示该点已经 走过，但是走不通
//5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
/**
* @param map 表示地图
* @param i 从哪个位置开始找
* @param j * @return 如果找到通路，就返回 true, 否则返回 false
* */
public static boolean setWay(int[][] map, int i, int j) {
if (map[6][5] == 2) {
return true;//表示目的地已经到达
}else if(map[6][5] != 0){//1或3
return false;
}else{//表示还有机会
if(map[i][j] != 0){
/*
表示该点已经没必要走了
1：墙没必要走
2：已经走过了该点，再走该点没必要了。不能重复尝试，不然会死循环（关键：每次到一个点都会把所有的可能性都试一遍）
3：从该点出发，不管怎么样都找不到目的地。死路
*/
return false;
}else {
//继续尝试
//先假定该点可以走通
map[i][j] = 2;
//下面的策略可以自定义,默认上下左右
// if(setWay(map,i-1,j)){
// return true;
// }else if(setWay(map,i+1,j)){
// return true;
// }else if(setWay(map,i,j+1)){
// return true;
// }else if(setWay(map,i,j-1)){
// return true;
// }else{
// return false;
// }
//换个车略， 下 -左 -上 -右
if(setWay(map,i+1,j)){
return true;
}else if(setWay(map,i,j+1)){
return true;
}else if(setWay(map,i-1,j)){
return true;
}else if(setWay(map,i,j-1)){
return true;
}else{
return false;
}
}
}
}
}
总结
- 代码有点像
深度优先。找到一个点如果该点可以走，就继续按照策略来找到子节点来尝试。就是一条路走到黑.看能不能找到目的地。如果某条路是死路（走到头了），则返回上一个节点。按照策略找到另一个子节点来尝试。 - 为什么走过的节点不给
重复走？- 从逻辑上：如果你可以通过重复走过的节点找到出路，那就说明真正有效的路只是重复节点之后的路。前面的都是白走的。那为什么不直接找出有效路径呢？
- 从代码上： 如果走过的节点可以走，那就会出现可能性一直存在的问题，即
无限循环.想象一下，你再走迷宫是，发现自己不断的走曾经走过的地方，但你却认为这条路还是可能是对的。就一直走一直走
三 八皇后问题
image.png
思路分析
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否OK， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
- 继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
- 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到.
- 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤
说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列
为什么要一行一行放？
因为从结果上看，8个皇后不可能再一行上,也不可能再一列。必定每行每列都有，那么我们可以假设他是从第一行开始形成结果的
代码实现
package com.zyc.recursion;
/**
* @author zhuyc
* @create 2019-07-27 12:21
*/
public class queen8 {
//定义一个max表示共有多少个皇后
int max = 8;
//定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
int[] array = new int[max];
static int count = 0;
static int judgeCount = 0;
public static void main(String[] args) {
//测试一把 ， 8皇后是否正确
queen8 queue8 = new queen8();
queue8.check(0);
System.out.printf("一共有%d解法", count);
System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w
}
//编写一个方法，放置第n个皇后
//特别注意： check 是 每一次递归时，进入到check中都有 for(int i = 0; i < max; i++)，因此会有回溯
private void check(int n) {
if(n == max) { //n = 8 , 其实8个皇后就既然放好
print();
return;
}
//依次放入皇后，并判断是否冲突
for(int i = 0; i < max; i++) {
//先把当前这个皇后 n , 放到该行的第1列
array[n] = i;
//判断当放置第n个皇后到i列时，是否冲突
if(judge(n)) { // 不冲突
//接着放n+1个皇后,即开始递归
check(n+1); //
}
//可以发现无论上面是否成功，都会把每列都尝试一遍
}
}
//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
/**
*
* @param n 表示第n个皇后
* @return
*/
private boolean judge(int n) {
judgeCount++;
for(int i = 0; i < n; i++) {
// 说明
//1. array[i] == array[n] 表示判断 第n个皇后是否和前面的n-1个皇后在同一列
//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
// n = 1 放置第 2列 1 n = 1 array[1] = 1
// Math.abs(1-0) == 1 Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
//3. 判断是否在同一行, 没有必要，n 每次都在递增
if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
return false;
}
}
return true;
}
//写一个方法，可以将皇后摆放的位置输出
private void print() {
count++;
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
}
总结
- 一维数组便表示
行肯定不会冲突 - 算法目的是得到
所有的可能性。所以不管深度优先（就是找到一个方向一直往下找）是否成功发现了解，都会继续尝试将本行的皇后放其他列.我们要做 - 如何判断是否在
同一列，我们可以发现同一列的两个点的连线的斜率是1.表示两个点在x/y轴上的绝对值差距相等。 - check方法就是尝试把第n+1个皇后放在第n行
for(int i = 0; i < max; i++) {
//先把当前这个皇后 n , 放到该行的第1列
array[n] = i;
//判断当放置第n个皇后到i列时，是否冲突
if(judge(n)) { // 不冲突
//接着放n+1个皇后,即开始递归
check(n+1); //
}
//可以发现无论上面是否成功，都会把每列都尝试一遍
}
- for循环表示一列一列尝试
- 只有judage成功，才递归
check(n+1)。表示如果本行的该列放置皇后是错误的，那么没必要试：在当前场景下下一行皇后放哪 - 没有break表示，表示无论如何都要把所有列尝试一遍。不管是否找到了正解
四 汉诺塔问题
汉诺塔：汉诺塔(Tower of Hanoi)源于印度传说中，大梵天创造世界时造了三根金钢石柱子，其中一根柱子自底向上叠着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
问题抽象一下
就是有n层圆盘（），和3个柱子下a,b,c（如下图）。在a上有n层圆盘，需要将a全部移动到b。还有若干规则
image.png
解体思路
说实话这个算法对我感觉就是神奇，我脑子实在无法像计算机去模拟执行过程。在这个算法中，我们只要定义好运行规则，计算机就会输出运行结果。这也突出了抽象问题的魅力 ,只要我们搞懂了解体思路，定义了接替规则，枯燥和海量的计算就交给计算机好了。
- 首先如果有一个圆盘，那答案很简单，就是a-->b(表示将a柱子上的圆盘移动到b)即可
- 如果有两个盘子呢，答案也很简单,应该大家都能想到，需要借助
中转轴c。- 先将最小的移动到c
- 然后将最大移动到b
- 将c上的圆盘移动到b
- 如果是3个，4个呢？越来越麻烦了吧。
这时通过分析可得，我们可以将实现目的过程就是三步。
image.png
假设把上面这三步封装成一个方法 f(a,b,c,n);
a:源柱子
b:目标柱子
c:其他柱子n
n:移动多少层
那现在就有一个问题如何把a上面的除了最后一个盘移动到c呢？
我们可以调用上面刚封装的f方法：f(a,c,b,n-1)
那如何把c上的全移动到b呢
也是调用方法f(c,b,a,n-1)
临界条件
把某个柱子上的一层移动到目的柱子，这样就不需要三步了。直接一步（直接移动接口）。当然前提就是：
我们需要保证这样移动是不会违反题目的规定（即小盘不能放在大盘上面）
小结
我们总结出了过程的规律，但是我本人自己还是没能模拟出计算机执行的过程。因为这个规律在从结果往前推的，这个递归方法在前面的调用中都不会去移动盘子。直到临界点，然后后进先出式的执行
java实现就是
public static void main(String[] args) {
hannuota(3,"a","b","c");
}
/**
* 将n层塔，从x转移到y，z是中转轴
* @param n
* @param x
* @param y
* @param z
*/
public static void hannuota(int n,String x,String y,String z) {
if(n==1) {//如果只有一层 直接移动即可
System.out.println(x+"-->"+y);
}else {
/*
* 如果有多层有3步
* 1. 将n-1层从x移动到z
* 2. 将x的最后一层（有且只有一层）移动到y
* 3. 将z上的n-1层全部移动到y上面
*/
hannuota(n-1,x,z,y);
move(x,y);
hannuota(n-1,z,y,x);
}
}
public static void move(String x,String y) {
System.out.println(x+"-->"+y);
}
