数据结构与算法——Java实现递归、迷宫回溯问题、八皇后问题

谁践踏了优雅 2024-03-30 09:21 55阅读 0赞

**目录**

一、递归

1.1 介绍递归

二、迷宫回溯问题

2.1 代码实现

三、八皇后问题

3.1 基本介绍

3.2 分析思路

3.3 代码实现

--------------------

## 一、递归 ##

### 1.1 介绍递归 ###

**简单的说：递归就是方法自己调用自己，每次传入不同的变量。**

递归有助于编程者解决复杂的问题，同时可以让代码变得简洁。

![f1cedcb778d7481bb33b7d5a489738e5.png][]

**递归可以解决什么样的问题？**

*  八皇后问题、汉诺塔、阶乘、迷宫、球和蓝子
 *  各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等
 *  把用栈解决的问题编程递归代码比较简洁

**递归重要的规则**

*  执行一个方法时，就创建一个新的受保护的独立空间（栈空间）
 *  方法的局部变量是独立的，不会相互影响的
 *  如果方法中使用的是引用数据类型变量（比如数组，每一次递归都是用的同一个数据，修改的同一个数据），就会共享该引用数据类型的数据
 *  递归必须向退出递归的条件逼近，否则死循环
 *  当一个方法执行完毕，或者遇到return，就会返回。遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕。

## 二、迷宫回溯问题 ##

**最短路径和程序员找的策略有关**

### 2.1 代码实现 ###

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;
            }
    //      第一列和第七列全是墙
            for(int i=0;i<8;i++){
                map[i][0]=1;
                map[i][6]=1;
            }
    //      除此之外还有挡板
            map[3][1]=1;
            map[3][2]=1;
    
    //      模型输出一下
            for(int i=0 ;i<8 ; i++){
                for (int j=0; j<7;j++){
                    System.out.print(map[i][j]+"   ");
                }
                System.out.println();
            }
            System.out.println("***********************递归回溯开始！！！！！！*********************");
    //      递归回溯
            setWay(map,1,1);
    //      输出小球走过的路
            for(int i=0 ;i<8 ; i++){
                for (int j=0; j<7;j++){
                    System.out.print(map[i][j]+"   ");
                }
                System.out.println();
            }
        }
    
        /**
         * 递归开始处是11  结束处是65
         * 约定： map[i][j]=0时没有走过，1表示墙，2表示走过，是通路,3表示走过了这个路走不通
         *      如果能走到map[6][5]位置，既map[6][5]，说明路能通
         * 确定策略：在走迷宫的时候按照 先走下面，走不通走右面，再走不通走上面，再走不通走左面 ，如果该点走不通再回溯
         *使用递归回溯给小球找路 找到为true
         * @param map 地图
         * @param i   从哪个位置开始找
         * @param j   从哪个位置开始找
         * @return    找到路返回true
         */
        public static  boolean setWay(int[][] map,int i ,int j){
               if(map[6][5] ==2 ){
    //             到终点了
                   return true;
               }else {
    //              没有到终点，继续走
                    if(map[i][j] ==0){
    //                  先假定能走通，我们走走试试
                        map[i][j] =2;
                        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 {
    //                      运行到这里肯定是走不通
                            map[i][j] =3;
                            return false;
                        }
    
                    }else {
    //                  map[i][j] ！=0  代表着可能是1,2,3,这三个都不满足我们走的条件
                        return false;
                    }
               }
        }
    
    
    }

![a812eb41159a48d1af86ba1a111aa4bb.png][]

## 三、八皇后问题 ##

### 3.1 基本介绍 ###

八皇后问题：是回溯算法的基本案例。在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，**即任意两个皇后不能处于同一行、同一列或同一斜线，问有几种摆法**

**答案是92种**

### 3.2 分析思路 ###

首先说明：回溯的效率并不高，因为这就好像是每个路都走走试试行不行，这种方法就类似我们上学时学的穷举法，一个一个的试。比如我们这个8\*8的棋盘就要执行一万五千多次，可见效率情况

![237e522a96134859a88c6ecc83d4b489.png][]

**解题说明：理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法简化。用一个一维数组即可解决问题，arr\[8\]=\{0,4,7,5,2,6,1,3\},其中数组下标对应第几列，数组下标对应的数值对应皇后放在哪个位置。比如arr\[i\]=var，var表示第i+1个皇后放在第i+1行的第val+1列**

### 3.3 代码实现 ###

public class Queue8 {
    //  定义一个max，表示共有多少个皇后
        int max =8;  //8*8的棋盘，有8个皇后
        int[] array = new int[max];  //定义数组，存放皇后存在的位置
        int count =0;
        public static void main(String[] args) {
    //        测试
            Queue8 queue8 = new Queue8();
            queue8.check(0);
    
    
    
    
    
        }
    
    //   编写放置皇后的方法(n从0开始计数）
    //  check每一次递归时进入到check都会有for循环，可以理解为多层for循环，这个想法太好了
        private void check(int n){
            if(n == max){
                count++;
                System.out.println(count);
                print();  //我们自己编写的，输出
    //          //n=8,表示对数组来说就是第九个，很显然已经超出范围了，故我们的棋盘已经找出结果了
                return;
            }
    //      依次放入皇后，并判断是否冲突
            for(int i=0;i<max;i++){
    //          放置当前皇后n，放到改行的第一列
    //          第n行第i列
                array[n] =i;
    //          我们应该判断一下，第n行第i列放了行不行
                if (judge(n)){
    //              运行到这里说明不冲突,然后再放下一个
                    check(n+1);  //for循环结束或者n==max之后，就会产生回溯
                }
    //          上面是不冲突的，万一冲突怎么办？
    //              就会i++，又放到此行的下一个位置再次重试
            }
    
        }
    
    
    
        /**
         * 查看当我们放置第n个皇后，就去检测该皇后是否与前面已经摆放的皇后冲突
         *    这个地方我们不需要判断是否在同一行，因为我们使用了数组，数组下标代表行，故每行只能放一个
         *  n从零开始计数
         * @param n  表示第几个皇后
         * @return
         */
         private  boolean judge(int n){
            for(int i=0;i<n;i++){
                if(array[i]==array[n] ||Math.abs(n-i)==Math.abs(array[n]-array[i])){
    //               array[i]==array[n]  表示在同一列
    //               Math.abs(n-i)==Math.abs(array[n]-array[i])表示判断第n个皇后是否和第i皇后在同一个斜线上
    //                  其实最后一个很好理解   把上面的式子变形，我们带入一下初中学的平面直角坐标系，
    //                  (n-i)/(array[n]-array[i]) = -1 或1  通俗的来说就行y的变化量比上x的变化量等于正一或负一
    //                  这样就是在同一个斜线上，这个地方真的有点巧妙
                    return  false;
                }
            }
    //      返回true说明冲突
            return true;
         }
    
    
    
    //  写一个方法，可以将皇后摆放的位置输出
        private void print(){
            for(int i=0; i<array.length;i++){
                System.out.print(array[i]+"");
            }
            System.out.println();
        }
        
    }

![95dce6e402304a579e3eb68d9e98f392.png][]

**我们可以仔细的看一下下面这个图，我们看下标为0的数，是从0开始逐渐增大的，说明我们在分析阶段分析的没毛病。先把皇后在第一行的所有情况都找到，然后再把第二行的所有情况都找到，就这样依次执行到第八行，最终完成**

![3f134482c708458b8dd432c46040bca8.png][]

[f1cedcb778d7481bb33b7d5a489738e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c268e7e0b58b4b278f22169b755feb97.png
[a812eb41159a48d1af86ba1a111aa4bb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b86966b0dc2e45a891efda971b573813.png
[237e522a96134859a88c6ecc83d4b489.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/17c46b1aa7dc42f5a23096b50028a1bf.png
[95dce6e402304a579e3eb68d9e98f392.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fed028912763486dbc840742ed1d3859.png
[3f134482c708458b8dd432c46040bca8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/1504066359124eb98ccad0976e07e296.png