数据结构与算法--递归

递归有助于解决复杂的问题 ,但是容易陷入回溯验证

递归

自己的方法调用自己的方法 , 递归有助于解决复杂的问题

1. 程序执行到一个方法的时候 , 就会去开辟一个独立的空间栈
2. 每一个空间的数据(局部变量) 都是独立的 ;
3. 如果方法中使用的引用类型变量(数据) ,就会共享该引用类型的数据
4. 递归必须于出口

迷宫寻址

代码实现

package 递归recursion;

import java.util.Random;

/**
 * author:小刘
 * 日期: 2020/3/5 10:54
 */
public class Recursion {
    public static void main(String[] args) {
        //设置一个行8 , 列8的地图, 并将外围围上墙,1代表墙
        int row = 8;
        int col = 8;
        int[][] map = new int[row][col];
        for (int i = 0; i < col; i++) {
            map[0][i] = 1;
            map[row - 1][i] = 1;
        }
        for (int i = 0; i < row; i++) {
            map[i][0] = 1;
            map[i][col - 1] = 1;
        }
        //为地图随机生成路障[3,8)
        int time = new Random().nextInt(5) + 3;
        boolean flag = true;
        for (int i = 0; i < time; i++) {
            flag = true;
            while (flag) {
                int randomRow = new Random().nextInt(row - 2) + 1;
                int randomCol = new Random().nextInt(col - 2) + 1;
                if (map[randomRow][randomCol] == 0 && randomRow != 1 && randomCol != 1) {
                    map[randomRow][randomCol] = 1;
                    flag = false;
                }
               randomRow+=1;
                randomCol+=1;
            }
        }
        System.out.println("=========原始地图路径========");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println(" ");
        }
        setWay(map, 1, 1, row, col);
        System.out.println("=========搜寻地图路径========");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println(" ");
        }

    }

    /**
     * 地图的起始点 , 起点为map[1][1] ,终点为map[row-2][col-2]
     * 搜索策略为 下 - 右 - 上 - 左
     * @param map     初始地图
     * @param initRow 定义的初始行
     * @param initCol 定义的初始列
     */
    public static boolean setWay(int[][] map, int initRow, int initCol, int row, int col) {
        //终点为出口
        if (map[row - 2][col - 2] == 2) {
            return true;
        } else {
            if (map[initRow][initCol] == 0) {
                map[initRow][initCol] = 2;
                if (setWay(map, initRow + 1, initCol, row, col)) {
                    return true;
                } else if (setWay(map, initRow, initCol + 1, row, col)) {
                    return true;
                } else if (setWay(map, initRow - 1, initCol, row, col)) {
                    return true;
                } else if (setWay(map, initRow, initCol - 1, row, col)) {
                    return true;
                } else {
                    map[initRow][initCol] = 3;
                    return false;
                }
            }else {
                return false;
            }
        }
    }
}

八皇后

代码实现

package 递归recursion;

/**
 * author:小刘
 * 日期: 2020/3/25 21:31
 */
public class Queue {

    int[] array =  new int[8];
    static  int count = 0;
    static  int countJudge = 0;
    public static void main(String[] args) {

        new Queue().put(0);
        System.out.printf("一共有%d解法",count);
        System.out.println("");
        System.out.printf("一共冲突%d次",countJudge);
    }

    /**
     * 检查第n+1个皇后
     * @param n
     */
    private void put(int n){
        //类比整体为1 ,出口
        if(n==8){
            count++;
            print();
            return;
        }
        //循环8次
        for (int i = 0; i < 8; i++) {
            //将当前皇后放到列上面
            array[n]=i;
            //判断是否冲突
            if(judge(n)){
                put(n+1);
            }

        }
    }

    /**
     * 判断第n+1个皇后是否和第n个有冲突
     * @param n
     * @return
     */
    private boolean judge(int n){
        for (int i = 0; i < n; i++) {
            //判断第n+1个皇后是否和之前皇后的列 和 斜线是否冲突
            if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])){
                countJudge++;
                return false;
            }
        }
        return true;
    }
    public void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
        System.out.println("");
    }
}

赏

小劉感谢您的赞赏

微信