数据结构和算法--5递归(迷宫问题和八皇后问题)

递归

1.递归的概念

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

2.递归需要遵守的重要规则

1)执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
2)方法的局部变量是独立的,不会相互影响
3)如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据
4)递归必须向退出递归的条件逼近,否则就是无限递归,出现StackOverflowError
5)当一个方法执行完毕,或者遇到return,就会返回。遵守谁调用就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕

3.迷宫问题

思路:

map表示地图,i,j表示从地图的那个位置出发(i,j)
如果球能到map[6][5]位置,说明找到出口
约定:map[i][j]为0表示此路还没有走过,2表示道路走过了是通的,3表示道路走过了但是没走通
在走迷宫时,需要确定一个策略:下->右->上->左,如果走不通,就回溯

具体代码

package com.ujiuye.recursion;

public class MiGong {
    public static void main(String[] args) {
        //先创建一个二维数组,模拟迷宫
        int[][] map = new int[8][7];
        //1代表是墙,把上下设置为墙
        for(int i = 0;i < 7;i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //把左右也设置为墙
        for(int i = 0;i < 7;i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //设置两个挡板
        map[3][1] = 1;
        map[3][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);
        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();
        }
    }
    public static boolean setWay(int[][] map,int i,int j) {
        //如果map[6][5]已经走了并且能走通,表示出了迷宫
        if(map[6][5] == 2) {
            return true;
        }else {
            //如果没有出迷宫,需要看哪条路能走
            //1 如果为0,表示没有走过,需要尝试走一遍
            if(map[i][j] == 0) {
                //先把路设置为已经走过的,2或3都代表走过,假如能走通
                //如果走不通,最后再更改这条线的值为3
                map[i][j] = 2;
                //按照下右上左的顺序走
                //1下,i+1,递归调用看这条线是否能走通
                if(setWay(map,i+1,j)) {
                    return true;
                //2右,j+1,递归调用看这条线是否能走通
                }else if(setWay(map,i,j+1)) {
                    return true;
                //3上,i-1,递归调用看这条线是否能走通
                }else if(setWay(map,i-1,j)) {
                    return true;
                //4左,j-1,递归调用看这条线是否能走通
                }else if(setWay(map,i,j-1)) {
                    return true;
                }else {
                    //下右上左都没有走通
                    map[i][j] = 3;
                    return false;
                }
            //表示这条路走过了,1或2或3,走过的路就不再走了
            }else {
                return false;
            }
        }
    }
}

4.八皇后问题

思路;

1)第一个皇后先放第一行第一列
2)第二个皇后放在第二行第一列,然后判断是否ok,如果不OK,继续放在第二列,第三列。。。依次把所有列都放完,找到一个合适的位置
3)。。。
4)当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后放到第一列的所有正确解全部得到
5)然后继续吧第一个皇后放在第二列,继续循环

具体代码

package com.ujiuye.recursion;

public class Queue8 {
    //定义有几个皇后
    int max = 8;
    static int count = 0;
    //定义一个一维数组,行数没有显示,数组显示的是列数
    //arr[i] i 表示第i+1个皇后,arr[i]表示在arr[i]+1列
    int[] array = new int[max];
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        //从第一个皇后开始放置
        queue8.check(0);
        System.out.printf("总共有%d种放置方式",count);
    }
    
    //写一个方法放置第n个皇后
    private void check(int n) {
        //n最大值为7,如果等于8说明全部摆放完毕
        if(n == max) {
            print();
            return;
        }
        //依次放入皇后,判断是否冲突,i表示第i+1列
        for(int i = 0;i < max;i++) {
            //第n+1个皇后放在第一列
            array[n] = i;
            //判断放置第n+1个皇后到第i+1列时,是否冲突
            if(judge(n)) {
                //如果不冲突,放下一个皇后
                check(n+1);
                
            }
            //如果冲突,就把该皇后放的位置的列数加1,即for循环
        }
    }
    //查看当放置第n个皇后,判断位置是否冲突
    //每个皇后在一行,所以判断列的位置有没有直线或者斜线
    private boolean judge(int n) {
        
        //加入第四个皇后,n=3,就要跟前三个比较,次数就是n次
        for(int i = 0;i < n;i++) {
            //||前表示在一个列,是个竖线
            //||后表示行距等于列举,是个斜线
            if(array[i] == array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])){
                return false;
            }
        }
        return true;
    }
    //输出皇后摆放的位置array={0,4,7,5,2,6,1,3}
    //h1:1,h2:5,h3:8,h4:6,h5:3,h6:7,h7:2,h8:4
    private void print() {
        count++;
        for(int i = 0;i < array.length;i++) {
            System.out.print(array[i]+"");
        }
        System.out.println();
    }
}

相关推荐