数据结构和算法--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(); } }
。
相关推荐
steeven 2020-11-10
Tips 2020-10-14
nongfusanquan0 2020-08-18
yedaoxiaodi 2020-07-26
清溪算法君老号 2020-06-27
pengkingli 2020-06-25
yishujixiaoxiao 2020-06-25
清溪算法 2020-06-21
RememberMePlease 2020-06-17
nurvnurv 2020-06-05
SystemArchitect 2020-06-02
码墨 2020-05-29
清溪算法 2020-05-27
choupiaoyi 2020-05-27
清溪算法 2020-05-25
bluewelkin 2020-05-19
dbhllnr 2020-05-15
steeven 2020-05-09
baike 2020-05-09