【Java数据结构和算法】010-递归：迷宫问题、八皇后问题(回溯算法)

柔情只为你懂 2023-10-05 13:43 71阅读 0赞

目录

0、警醒自己

一、递归应用场景和调用机制

1、简介

2、两个案例

打印问题：

打印结果：

执行分析图：

阶乘问题：

运行结果：

阶乘逻辑解析：

二、递归能解决的问题和规则

1、额递能解决什么问题

2、递归调用规则

三、迷宫问题

1、问题描述

2、代码实现

3、运行结果

4、问题回顾

5、代码实现

6、运行结果

7、思考：最短路径问题

四、八皇后问题

1、问题描述

2、思路分析

说明：

3、代码实现

4、运行结果

0、警醒自己

1、学习不用心，骗人又骗己；

2、学习不刻苦，纸上画老虎；

3、学习不惜时，终得人耻笑；

4、学习不复习，不如不学习；

5、学习不休息，毁眼伤身体；

7、狗才等着别人喂，狼都是自己寻找食物；

一、递归应用场景和调用机制

1、简介

简单的说：递归就是方法自己调用自己，每次调用时传入不同的变量。递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

2、两个案例

打印问题：

  1. package com.zb.ds;
  3. //递归
  4. public class Recursion {
  5.     public static void main(String[] args) {
  6.         test(4);
  7.     }
  8.     public static void test(int n) {
  9.         if (n > 2) {
  10.             test(n - 1);
  11.         }
  12.         System.out.println("n=" + n);
  13.     }
  15. }

打印结果：

  1. n=2
  2. n=3
  3. n=4

执行分析图：

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70

阶乘问题：

  1. package com.zb.ds;
  3. //递归
  4. public class Recursion {
  5.     public static void main(String[] args) {
  6.         test(4);
  8.         System.out.println(test1(5));
  9.     }
  10.     //打印问题
  11.     public static void test(int n) {
  12.         if (n > 2) {
  13.             test(n - 1);
  14.         }
  15.         System.out.println("n=" + n);
  16.     }
  17.     //阶乘问题
  18.     public static int test1(int n){
  19.         if(n==1){
  20.             return 1;
  21.         }else {
  22.             return test1(n-1) * n;
  23.         }
  24.     }
  25. }

运行结果：

  1. n=2
  2. n=3
  3. n=4
  4. 120

阶乘逻辑解析：

test1(4)*5 —— test1(3)*4*5 —— test1(2)*3*4*5 —— test1(1)*2*3*4*5 —— 1*2*3*4*5

二、递归能解决的问题和规则

1、额递能解决什么问题

各种数学问题如：8皇后问题、汉诺塔、阶乘问题、迷宫问题、球和篮子的问题(google编程大赛)；

各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等；

将用栈解决的问题—>递归代码比较简洁；

2、递归调用规则

①当程序执行到一个方法时，就会开辟一个独立的空间（栈）；

②每个空间的数据（局部变量）是相互独立的；

③如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据；

④递归必须向退出递归的条件逼近，否则就是无限递归,出现StackOverflowError，死龟了。。。

⑤当一个方法执行完毕，或者遇到return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕；

三、迷宫问题

1、问题描述

①小球得到的路径，和程序员设置的找路策略有关即：找路的上下左右的顺序相关；

②再得到小球路径时，可以先使用(下右上左)，再改成(上右下左)，看看路径是不是有变化；

③测试回溯现象；

④思考: 如何求出最短路径?

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1

2、代码实现

  1. package com.zb.ds;
  3. //递归：迷宫问题
  4. public class MiGong {
  5.     public static void main(String[] args) {
  6.         //创建一个二维数组，模拟迷宫
  7.         //地图
  8.         int[][] map = new int[8][7];
  9.         //使用1表示墙
  10.         //上下全部置为1
  11.         for (int i = 0; i < 7; i++) {
  12.             map[0][i] = 1;
  13.             map[7][i] = 1;
  14.         }
  15.         //左右全部置为1
  16.         for (int i = 0; i < 8; i++) {
  17.             map[i][0] = 1;
  18.             map[i][6] = 1;
  19.         }
  20.         //挡板
  21.         map[3][1] = 1;
  22.         map[3][2] = 1;
  23.         //输出地图
  24.         for (int i = 0; i < 8; i++) {
  25.             for (int j = 0; j < 7; j++) {
  26.                 System.out.print(map[i][j] +" ");
  27.             }
  28.             System.out.println();
  29.         }
  30.         //找路
  31.         if(findWay(map, 1, 1)){
  32.             System.out.println("找到路了！");
  33.         }else {
  34.             System.out.println("没找到路！");
  35.         }
  36.         //输出地图
  37.         for (int i = 0; i < 8; i++) {
  38.             for (int j = 0; j < 7; j++) {
  39.                 System.out.print(map[i][j] +" ");
  40.             }
  41.             System.out.println();
  42.         }
  43.     }
  44.     /**
  45.      * 使用递归回溯，给小球找路
  46.      * 说明：
  47.      * 1、map是地图；
  48.      * 2、i、j表示从哪个位置出发(1,1)
  49.      * 3、如果小球能到map的(6,5)，说明找到路
  50.      * 4、约定：当地图map[i][j]为0时，表示未测试过（未走过），当为1时为墙，2为通路，3表示该位置已经走过但无法走通；
  51.      * 5、确定一个走迷宫探路的策略：先走下边、下边走不通走右边，以此类推顺序为“下——右——上——左”，如果走不通再回溯
  52.      * @param map 地图
  53.      * @param i 从哪个位置开始找
  54.      * @param j 从哪个位置开始找
  55.      * @return  找到路返回true，否则返回false
  56.      */
  57.     public static boolean findWay(int[][] map,int i,int j){
  58.         if(map[6][5]==2){
  59.             return true;
  60.         }else {
  61.             if(map[i][j]==0){
  62.                 //没走过，按策略走：下——右——上——左
  63.                 map[i][j] = 2;//假定此点可以走通
  64.                 if(findWay(map,i+1,j)){
  65.                     //向下走
  66.                     return true;
  67.                 }else if(findWay(map,i,j+1)){
  68.                     //向右走
  69.                     return true;
  70.                 }else if(findWay(map,i-1,j)){
  71.                     //向上走
  72.                     return true;
  73.                 }else if(findWay(map,i,j-1)){
  74.                     //向左走
  75.                     return true;
  76.                 }else {
  77.                     map[i][j] = 3;
  78.                     return false;
  79.                 }
  80.             }else{//如果map[i][j]!=0，可能是1，2，3
  81.                 return false;
  82.             }
  83.         }
  84.     }
  85. }

3、运行结果

（找到路了，2是路线，这个算法真是太强大了）

  1. 1 1 1 1 1 1 1 
  2. 1 0 0 0 0 0 1 
  3. 1 0 0 0 0 0 1 
  4. 1 1 1 0 0 0 1 
  5. 1 0 0 0 0 0 1 
  6. 1 0 0 0 0 0 1 
  7. 1 0 0 0 0 0 1 
  8. 1 1 1 1 1 1 1 
  9. 找到路了！
  10. 1 1 1 1 1 1 1 
  11. 1 2 0 0 0 0 1 
  12. 1 2 2 2 0 0 1 
  13. 1 1 1 2 0 0 1 
  14. 1 0 0 2 0 0 1 
  15. 1 0 0 2 0 0 1 
  16. 1 0 0 2 2 2 1 
  17. 1 1 1 1 1 1 1

4、问题回顾

我们可以知道，小球得到的路径和程序员设置的找路策略有很大关系，我们来讲原来的(下右上左)改成(上右下左)，进行测试，看结果如何；

5、代码实现

（说明：只需要将i的+1和-1呼唤即可）

  1. package com.zb.ds;
  3. //递归：迷宫问题
  4. public class MiGong {
  5.     public static void main(String[] args) {
  6.         //创建一个二维数组，模拟迷宫
  7.         //地图
  8.         int[][] map = new int[8][7];
  9.         //使用1表示墙
  10.         //上下全部置为1
  11.         for (int i = 0; i < 7; i++) {
  12.             map[0][i] = 1;
  13.             map[7][i] = 1;
  14.         }
  15.         //左右全部置为1
  16.         for (int i = 0; i < 8; i++) {
  17.             map[i][0] = 1;
  18.             map[i][6] = 1;
  19.         }
  20.         //挡板
  21.         map[3][1] = 1;
  22.         map[3][2] = 1;
  23.         //输出地图
  24.         for (int i = 0; i < 8; i++) {
  25.             for (int j = 0; j < 7; j++) {
  26.                 System.out.print(map[i][j] +" ");
  27.             }
  28.             System.out.println();
  29.         }
  30.         //找路
  31.         if(findWay(map, 1, 1)){
  32.             System.out.println("找到路了！");
  33.         }else {
  34.             System.out.println("没找到路！");
  35.         }
  36.         //输出地图
  37.         for (int i = 0; i < 8; i++) {
  38.             for (int j = 0; j < 7; j++) {
  39.                 System.out.print(map[i][j] +" ");
  40.             }
  41.             System.out.println();
  42.         }
  43.     }
  44.     /**
  45.      * 使用递归回溯，给小球找路
  46.      * 说明：
  47.      * 1、map是地图；
  48.      * 2、i、j表示从哪个位置出发(1,1)
  49.      * 3、如果小球能到map的(6,5)，说明找到路
  50.      * 4、约定：当地图map[i][j]为0时，表示未测试过（未走过），当为1时为墙，2为通路，3表示该位置已经走过但无法走通；
  51.      * 5、确定一个走迷宫探路的策略：先走下边、下边走不通走右边，以此类推顺序为“下——右——上——左”，如果走不通再回溯
  52.      * @param map 地图
  53.      * @param i 从哪个位置开始找
  54.      * @param j 从哪个位置开始找
  55.      * @return  找到路返回true，否则返回false
  56.      */
  57.     public static boolean findWay(int[][] map,int i,int j){
  58.         if(map[6][5]==2){
  59.             return true;
  60.         }else {
  61.             if(map[i][j]==0){
  62.                 //没走过，按策略走：下——右——上——左
  63.                 //更改策略为：上——右——下——左
  64.                 //说明：只需要将+1和-1呼唤即可
  65.                 map[i][j] = 2;//假定此点可以走通
  66.                 if(findWay(map,i-1,j)){
  67.                     //向下走
  68.                     return true;
  69.                 }else if(findWay(map,i,j+1)){
  70.                     //向右走
  71.                     return true;
  72.                 }else if(findWay(map,i+1,j)){
  73.                     //向上走
  74.                     return true;
  75.                 }else if(findWay(map,i,j-1)){
  76.                     //向左走
  77.                     return true;
  78.                 }else {
  79.                     map[i][j] = 3;
  80.                     return false;
  81.                 }
  82.             }else{//如果map[i][j]!=0，可能是1，2，3
  83.                 return false;
  84.             }
  85.         }
  86.     }
  87. }

6、运行结果

  1. 1 1 1 1 1 1 1 
  2. 1 0 0 0 0 0 1 
  3. 1 0 0 0 0 0 1 
  4. 1 1 1 0 0 0 1 
  5. 1 0 0 0 0 0 1 
  6. 1 0 0 0 0 0 1 
  7. 1 0 0 0 0 0 1 
  8. 1 1 1 1 1 1 1 
  9. 找到路了！
  10. 1 1 1 1 1 1 1 
  11. 1 2 2 2 2 2 1 
  12. 1 0 0 0 0 2 1 
  13. 1 1 1 0 0 2 1 
  14. 1 0 0 0 0 2 1 
  15. 1 0 0 0 0 2 1 
  16. 1 0 0 0 0 2 1 
  17. 1 1 1 1 1 1 1

7、思考：最短路径问题

（搁置，我自己的想法还不够成熟，暂时不做实现！）

四、八皇后问题

1、问题描述

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？【92种】

20201120090548586.png

2、思路分析

①第一个皇后先放第一行第一列；

②第二个皇后放在第二行第一列、然后判断是否OK（是否冲突）， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适；

③继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解；

④当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到；

⑤然后回头继续第一个皇后放第二列，后面继续循环执行①②③④的步骤；

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2

说明：

理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1个皇后，放在第i+1行的第val+1列；

3、代码实现

  1. package com.zb.ds;
  3. //递归：八皇后问题（回溯算法）
  4. public class EightQueen {
  5.     //定义一个max表示有多少个皇后
  6.     int max = 8;
  7.     int count = 0;
  8.     //定义一个数组array，保存皇后放置位置的结果，比如：arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3}
  9.     int[] array = new int[max];
  10.     public static void main(String[] args) {
  11.         //测试八皇后
  12.         new EightQueen().check(0);
  13.     }
  15.     //编写一个方法，放置第n个皇后
  16.     //每一次递归都有一套for循环，所有也有了从后往前回溯，成立的话摆下一个皇后，不成立的话将当前皇后摆到下一列继续判断，
  17.     // 假如当前行都不成立，回到上一行进行如此循环的判断，直到全部走通，简直amazing
  18.     private void check(int n){
  19.         if (n==max){//n==8，已经放了8个皇后
  20.             print();
  21.             return;
  22.         }
  23.         //依次放入皇后，并判断是否冲突
  24.         for (int i = 0; i < max; i++) {
  25.             //先把当前皇后n，放到改行的第1列
  26.             array[n] = i;
  27.             //判断当放置第n个皇后到i列时，是否冲突
  28.             if(judge(n)){//不冲突
  29.                 //接着放n+1和皇后，开始递归
  30.                 check(n+1);
  31.             }
  32.             //如果冲突就继续执行循环，放到下一列
  33.         }
  34.     }
  36.     //当我们放置第n个皇后去检测是否与前面摆放的皇后有冲突
  37.     //n表示第n个皇后，i表示n前面的某个皇后，array[n]表示第n个皇后的位置，array[i]表示n前面的某个皇后的位置
  38.     private boolean judge(int n){
  39.         for (int i = 0; i < n; i++) {
  40.             if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i])){
  41.                 //在同一列或者在同一斜线上
  42.                 //在同一斜线上：Math.abs(n-i)表示相差的列数，Math.abs(array[n] - array[i])表示相差的行数，如果二者相等，说明在一条斜线上
  43.                 return false;
  44.             }
  45.         }
  46.         return true;
  47.     }
  49.     //写一个方法，可以讲皇后摆放的位置打印出来
  50.     private void print(){
  51.         count++;
  52.         System.out.print("第" + count + "种解法：");
  53.         for (int value : array) {
  54.             System.out.print(value + " ");
  55.         }
  56.         System.out.println();
  57.     }
  58. }

4、运行结果

  1. 第1种解法：0 4 7 5 2 6 1 3 
  2. 第2种解法：0 5 7 2 6 3 1 4 
  3. 第3种解法：0 6 3 5 7 1 4 2 
  4. 第4种解法：0 6 4 7 1 3 5 2 
  5. 第5种解法：1 3 5 7 2 0 6 4 
  6. 第6种解法：1 4 6 0 2 7 5 3 
  7. 第7种解法：1 4 6 3 0 7 5 2 
  8. 第8种解法：1 5 0 6 3 7 2 4 
  9. 第9种解法：1 5 7 2 0 3 6 4 
  10. 第10种解法：1 6 2 5 7 4 0 3 
  11. 第11种解法：1 6 4 7 0 3 5 2 
  12. 第12种解法：1 7 5 0 2 4 6 3 
  13. 第13种解法：2 0 6 4 7 1 3 5 
  14. 第14种解法：2 4 1 7 0 6 3 5 
  15. 第15种解法：2 4 1 7 5 3 6 0 
  16. 第16种解法：2 4 6 0 3 1 7 5 
  17. 第17种解法：2 4 7 3 0 6 1 5 
  18. 第18种解法：2 5 1 4 7 0 6 3 
  19. 第19种解法：2 5 1 6 0 3 7 4 
  20. 第20种解法：2 5 1 6 4 0 7 3 
  21. 第21种解法：2 5 3 0 7 4 6 1 
  22. 第22种解法：2 5 3 1 7 4 6 0 
  23. 第23种解法：2 5 7 0 3 6 4 1 
  24. 第24种解法：2 5 7 0 4 6 1 3 
  25. 第25种解法：2 5 7 1 3 0 6 4 
  26. 第26种解法：2 6 1 7 4 0 3 5 
  27. 第27种解法：2 6 1 7 5 3 0 4 
  28. 第28种解法：2 7 3 6 0 5 1 4 
  29. 第29种解法：3 0 4 7 1 6 2 5 
  30. 第30种解法：3 0 4 7 5 2 6 1 
  31. 第31种解法：3 1 4 7 5 0 2 6 
  32. 第32种解法：3 1 6 2 5 7 0 4 
  33. 第33种解法：3 1 6 2 5 7 4 0 
  34. 第34种解法：3 1 6 4 0 7 5 2 
  35. 第35种解法：3 1 7 4 6 0 2 5 
  36. 第36种解法：3 1 7 5 0 2 4 6 
  37. 第37种解法：3 5 0 4 1 7 2 6 
  38. 第38种解法：3 5 7 1 6 0 2 4 
  39. 第39种解法：3 5 7 2 0 6 4 1 
  40. 第40种解法：3 6 0 7 4 1 5 2 
  41. 第41种解法：3 6 2 7 1 4 0 5 
  42. 第42种解法：3 6 4 1 5 0 2 7 
  43. 第43种解法：3 6 4 2 0 5 7 1 
  44. 第44种解法：3 7 0 2 5 1 6 4 
  45. 第45种解法：3 7 0 4 6 1 5 2 
  46. 第46种解法：3 7 4 2 0 6 1 5 
  47. 第47种解法：4 0 3 5 7 1 6 2 
  48. 第48种解法：4 0 7 3 1 6 2 5 
  49. 第49种解法：4 0 7 5 2 6 1 3 
  50. 第50种解法：4 1 3 5 7 2 0 6 
  51. 第51种解法：4 1 3 6 2 7 5 0 
  52. 第52种解法：4 1 5 0 6 3 7 2 
  53. 第53种解法：4 1 7 0 3 6 2 5 
  54. 第54种解法：4 2 0 5 7 1 3 6 
  55. 第55种解法：4 2 0 6 1 7 5 3 
  56. 第56种解法：4 2 7 3 6 0 5 1 
  57. 第57种解法：4 6 0 2 7 5 3 1 
  58. 第58种解法：4 6 0 3 1 7 5 2 
  59. 第59种解法：4 6 1 3 7 0 2 5 
  60. 第60种解法：4 6 1 5 2 0 3 7 
  61. 第61种解法：4 6 1 5 2 0 7 3 
  62. 第62种解法：4 6 3 0 2 7 5 1 
  63. 第63种解法：4 7 3 0 2 5 1 6 
  64. 第64种解法：4 7 3 0 6 1 5 2 
  65. 第65种解法：5 0 4 1 7 2 6 3 
  66. 第66种解法：5 1 6 0 2 4 7 3 
  67. 第67种解法：5 1 6 0 3 7 4 2 
  68. 第68种解法：5 2 0 6 4 7 1 3 
  69. 第69种解法：5 2 0 7 3 1 6 4 
  70. 第70种解法：5 2 0 7 4 1 3 6 
  71. 第71种解法：5 2 4 6 0 3 1 7 
  72. 第72种解法：5 2 4 7 0 3 1 6 
  73. 第73种解法：5 2 6 1 3 7 0 4 
  74. 第74种解法：5 2 6 1 7 4 0 3 
  75. 第75种解法：5 2 6 3 0 7 1 4 
  76. 第76种解法：5 3 0 4 7 1 6 2 
  77. 第77种解法：5 3 1 7 4 6 0 2 
  78. 第78种解法：5 3 6 0 2 4 1 7 
  79. 第79种解法：5 3 6 0 7 1 4 2 
  80. 第80种解法：5 7 1 3 0 6 4 2 
  81. 第81种解法：6 0 2 7 5 3 1 4 
  82. 第82种解法：6 1 3 0 7 4 2 5 
  83. 第83种解法：6 1 5 2 0 3 7 4 
  84. 第84种解法：6 2 0 5 7 4 1 3 
  85. 第85种解法：6 2 7 1 4 0 5 3 
  86. 第86种解法：6 3 1 4 7 0 2 5 
  87. 第87种解法：6 3 1 7 5 0 2 4 
  88. 第88种解法：6 4 2 0 5 7 1 3 
  89. 第89种解法：7 1 3 0 6 4 2 5 
  90. 第90种解法：7 1 4 2 0 6 3 5 
  91. 第91种解法：7 2 0 5 1 4 6 3 
  92. 第92种解法：7 3 0 2 5 1 6 4

发表评论

表情：
评论列表 （有 0 条评论，71人围观）

还没有评论，来说两句吧...

相关阅读

    相关 递归解决八皇后回溯算法

    问题简述：八皇后问题是一个古来而著名的问题，该问题是19世纪著名的数学家高斯同学提出来的。在8\8的国际象棋上摆放八个皇后，使其不能互相的攻击，也就是说，任意的两个皇后不能放在

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 21 阅读