数据结构递归递归
小贾嗯嗯递归
递归需要遵循的重要规则
- 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
- 方法的局部变量是独立的,不会相互影响
- 如果方法中使用的是引用类型变量(数组),就会共享该引用类型的数据
- 递归必须向退出递归的条件逼近,否则就是无限递归,死龟了
- 当一个方法执行完毕,或者遇到return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕
递归-迷宫问题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
| public class MiGong { public static void main(String[] args) { int[][] map=new int[8][7]; 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;
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(); } }
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 { return false; } } } }
|
递归-八皇后
- 第一个皇后先放第一行第一列
- 第二个皇后放在第二行第一列、然后判断是否OK, 如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
- 继续第三个皇后,还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置,算是找到了一个正确解
- 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到.
- 然后回头继续第一个皇后放第二列,后面继续循环执行 1,2,3,4的步骤
说明:理论上应该创建一个二维数组来表示棋盘,但是实际上可以通过算法,用一个一维数组即可解决问题.
arr[8] = {0 , 4, 7, 5, 2, 6, 1, 3} //对应arr 下标 表示第几行,即第几个皇后,arr[i] = val , val 表示第i+1个皇后,放在第i+1行的第val+1列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| public class Queue8 { int max=8; int[] array=new int[8]; static int count=0; public static void main(String[] args) { Queue8 queue8=new Queue8(); queue8.check(0); System.out.printf("共有%d种解法",count); }
private void check(int n) { if (n==max) { print(); return; } for (int i = 0; i < max; i++) { array[n]=i; if (judge(n)) { check(n+1); } } }
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])) { return false; } } return true; } private void print() { count++; for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } System.out.println(); } }
|