Open Zakariyya opened 4 years ago
public static void test(int n){ if(n>2) test(n-1); sout("n = " + n); }
输出
n = 2 n = 3 n = 4
public static int factorial(int n){ if(n==1) return 1; else return factorial(n-1) * n; }
从 X 走到 Y X = [1,1] Y = [6,5] 1 1 1 1 1 1 1 1 X 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 Y 1 1 1 1 1 1 1 1 /** * map 表示地图 * i,j 表示从地图得哪个位置开始出发（1,1） * 如果小球能到map[6][5]位置，则说明通路找到了 * 约定：当map[i][j]， 为0表示该点没有走过 为1表示墙 为2表示通路可以走 为3表示该点已经走过，但是走不通 * * 在走迷宫时，需要确定一个策略（方法），下->右->上->左，如果该点走不通，再回溯 */ 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; } } } }
问题介绍：在一个8 * 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即： 任意两个皇后都不能处于同一行、同一列或者同一斜线上，问有多少种摆法（一共92种）
思路分析
说明： 理论上应该创建一个二维数组来表示棋盘，但实际上可以通过算法用一个一维数组解决问题 ： arr[8] = {0,4,7,5,2,6,1,3}
class Queue8Test { //定义一个max表示共多少个皇后 int max = 8; int[] arr = new int[max]; // 定义数组arr，保存皇后放置位置的结果，比如arr={0,4,7,5,2,6,1,3} static int count = 0; @Test public void main(){ this.check(0); System.out.println("=========="+count); } //编写一个方法，放置第n个皇后 //特别注意：check是每一次递归时，进入check中都有 for(int i=0;i<max;i++)，因此会有回溯 public void check(int n){ if(n==max){ //n=8 ，既然第8个皇后了，说明都放好了 print(); return; } //依次放入皇后，并判断是否冲突 for (int i = 0; i < max; i++) { //先把当前这个皇后n，放到该行的第1列 arr[n] = i; //判断当前放置第 n个皇后到 i列时，是否冲突 if(judge(n)){//不冲突 //接着放 n+1个皇后，即开始递归 check(n + 1); } // 如果冲突，就继续执行arr[n]=i; 即将第 n个皇后，放置在本行的 后移的一个位置 } } /** * 查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突 * * @param n 表示第n个皇后 * @return */ private boolean judge(int n) { for (int i = 0; i < n; i++) { // 说明 // 1. arr[i] == arr[n] 表示判断第n个皇后是否和前面的n-1个皇后在同一列 // 2. Math.abs(n-i) == Math.abs(arr[n]-arr[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线上 // n=1 放置第2列1 n=1 arr[1]=1 if(arr[i] == arr[n] || Math.abs(n-i)==Math.abs(arr[n]-arr[i])){ return false; } } return true; } // 将数组打印出来 private void print(){ count++; for(int i =0;i< arr.length;i++){ System.out.print(arr[i]+" "); } System.out.println(); }
打印问题（回顾）
输出
阶乘（回顾）
应用场景
迷宫（回溯）
八皇后问题
问题介绍：在一个8 * 8格的国际象棋上摆放八个皇后，使其不能互相攻击，即： 任意两个皇后都不能处于同一行、同一列或者同一斜线上，问有多少种摆法（一共92种）
说明： 理论上应该创建一个二维数组来表示棋盘，但实际上可以通过算法用一个一维数组解决问题 ： arr[8] = {0,4,7,5,2,6,1,3}