递归算法的实际应用 

1. 

    

    

   1. package com.model.recursion;
      
      import java.util.Arrays;
      
      /**
       * @Description:测试类
       * @Author: 张紫韩
       * @Crete 2021/7/10 16:15
       * 递归算法实现迷宫问题
       */
      public class RecursionDemo02 {
          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 < 8; i++) {
                  map[i][0] = 1;
                  map[i][6] = 1;
              }
              map[3][1] = 1;
              map[3][2] = 1;
              //输出地图
              for (int i = 0; i < 8; i++) {
                  for (int j = 0; j < 7; j++) {
                      System.out.print(map[i][j] + "\t");
                  }
                  System.out.println();
              }
              findWay(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] + "\t");
                  }
                  System.out.println();
              }
      
              findWay2(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] + "\t");
                  }
                  System.out.println();
              }
      
          }
      //        使用递归回溯，来给小球找路
      
          /**
           * map[i][j]:出发点
           * map[6][5]:终点
           * 找最短路径
           * 走过的点数值变为2
           * 已经走过了但是走不通的点数值为3
           * 还没有走过的点为0
           * 不能走的点位1
           */
          public static boolean findWay(int[][] map, int i, int j) {
              if (map[6][5] == 2) {
                  return true;
              } else {
                  if (map[i][j] == 0) {
                      map[i][j] = 2;
                      if (findWay(map, i + 1, j)) {
                          return true;
                      } else if (findWay(map, i, j + 1)) {
                          return true;
                      } else if (findWay(map, i - 1, j)) {
                          return true;
                      } else if (findWay(map, i, j - 1)) {
                          return true;
                      } else {
                          map[i][j] = 3;//说明当前路为死路
                          return false;
                      }
                  } else {//如果当前点是 1 ，2，3 说明当前的点位思路返回false
                      return false;
                  }
              }
          }
          public static boolean findWay2(int[][] map,int i,int j){
              if (map[6][5]==2){
                  return true;
              }else {
                  if (map[i][j]==0){
                      map[i][j]=2;
                      if(findWay2(map, i+1, j)){
                          return true;
                      }else if (findWay2(map,i, j+1)){
                          return true;
                      }else if (findWay2(map, i-1, j)){
                          return true;
                      }else if(findWay2(map, i, j-1)){
                          return true;
                      }else {
                          map[i][j]=3;
                          return false;
                      }
                  }else {
                      return false;
                  }
              }
          }
      }

2.  

   1.  

   2.  

   3. package com.model.recursion;
      
      /**
       * @Description:测试类
       * @Author: 张紫韩
       * @Crete 2021/7/10 17:27
       * 递归实现八皇后问题
       */
      public class RecursionDemo03 {
          public static void main(String[] args) {
              RecursionDemo03 recursionDemo03 = new RecursionDemo03();
              recursionDemo03.place(0);
              System.out.println("一共有几种摆放方式："+count);
          }
      
          int max=8;
          int[] arr=new int[max]; //保存结果的数组
          static int count=0;
          public void print(){
              for (int i = 0; i < arr.length; i++) {
                  System.out.print(arr[i]+"\t");
              }
              System.out.println();
          }
          //检查是否和前面的棋子同列或同斜线
          public  boolean check(int n){
              for (int i = 0; i < n; i++) {
                  if (arr[i]==arr[n]||Math.abs(n-i)==Math.abs(arr[n]-arr[i])){
                      return false;
                  }
              }
              return true;
          }
      //    放置棋子
          public  void place(int n){
              if (n==max){
                  print();
                  count++;
                  return;
              }
              for (int i = 0; i < max; i++) {
                  arr[n]=i;
                  if (check(n)){
                      place(n+1);
                  }
              }
          }
      }