编程知识 cdmana.com

Data structure and algorithm (XI) -- algorithm recursion

One 、 Introduce

1、 Introduce

   recursive : Recursion is a method that calls itself , Different variables are passed in each call . Recursion helps programmers solve complex problems , At the same time, it can make the code concise .
The difference between iteration and recursion : Iterations use the loop structure , Selection structure used recursively . Using recursion can make the structure of the program clearer 、 More concise 、 It's easier to understand , This reduces the time to read the code . Its time complexity is the number of recursions .
   But a lot of recursive calls create copies of functions , It will consume a lot of time and memory , Iteration does not require this effort .
   Recursive functions are divided into call and fallback stages , The fallback order of recursion is the reverse order of its call order .

   Divide and conquer : When a problem is large and difficult to solve , You can consider dividing the problem into several small modules , One by one .

2、 Case study

  • The problem of rabbit reproduction .( Fibonacci sequence ).
  • Calculation n! .
  • Reverse output of any length string .
  • Recursive implementation of half search algorithm .
  • The hanotta problem
  • Eight queens question

Two 、 Maze problem

   problem : Find an effective path from the beginning to the end .

   Code example : maze

  1 public class MiGong {
  2 
  3     /**
  4      * 0: This point has not been passed , 1: Represents a wall , 2: You can go , 3: This point has passed , But it doesn't work \
  5      *  Strategy :  Next -> Right -> On -> Left ,  If that doesn't work , Backtracking 
  6      */
  7     private int[][] map;
  8     private int desX;
  9     private int desY;
 10 
 11     /**
 12      *  structure  row*col The maze of 
 13      *
 14      * @param row  That's ok 
 15      * @param col  Column 
 16      */
 17     public MiGong(int row, int col) {
 18         if (row <= 0 || col <= 0) {
 19             return;
 20         }
 21 
 22         map = new int[row][col];
 23 
 24         //  Default   The up and down or so   All walls 
 25         for (int i = 0; i < col; i++) {
 26             map[0][i] = 1;
 27             map[row - 1][i] = 1;
 28         }
 29 
 30         for (int i = 0; i < row; i++) {
 31             map[i][0] = 1;
 32             map[i][col - 1] = 1;
 33         }
 34 
 35     }
 36 
 37     /**
 38      *  Add a baffle inside the maze 
 39      *
 40      * @param i  Abscissa 
 41      * @param j  Ordinate 
 42      */
 43     public void addBaffle(int i, int j) {
 44         if (map == null) {
 45             return;
 46         }
 47 
 48         //  There are walls all week 
 49         if (i > 0 && i < map.length - 1 && j > 0 && j < map[0].length - 1) {
 50             map[i][j] = 1;
 51         }
 52     }
 53 
 54     /**
 55      *  Set the end position of the maze 
 56      *
 57      * @param desX  Abscissa 
 58      * @param desY  Ordinate 
 59      */
 60     public void setDes(int desX, int desY) {
 61         this.desX = desX;
 62         this.desY = desY;
 63     }
 64 
 65     public boolean setWay(int i, int j) {
 66         //  Access has been found 
 67         if (map[desX][desY] == 2) {
 68             return true;
 69         } else {
 70             if (map[i][j] != 0) {
 71                 return false;
 72             }
 73 
 74             // map[i][j] == 0  According to the strategy   Next -> Right -> On -> Left   recursive 
 75             //  Suppose that the point is accessible .
 76             map[i][j] = 2;
 77             if (setWay(i + 1, j)) {
 78                 return true;
 79             } else if (setWay(i, j + 1)) {
 80                 return true;
 81             } else if (setWay(i - 1, j)) {
 82                 return true;
 83             } else if (setWay(i, j - 1)) {
 84                 return true;
 85             } else {
 86                 //  It shows that this point is not feasible , It's a dead end 
 87                 map[i][j] = 3;
 88                 return false;
 89             }
 90         }
 91     }
 92 
 93     //  Show map 
 94     public void show() {
 95         for (int i = 0; i < map.length; i++) {
 96             for (int j = 0; j < map[0].length; j++) {
 97                 System.out.print(map[i][j] + " ");
 98             }
 99             System.out.println();
100         }
101     }
102 }

   Code example : Test class

 1 //  Test class 
 2 public class Main {
 3 
 4     public static void main(String[] args) {
 5         MiGong miGong = new MiGong(8, 7);
 6         miGong.addBaffle(3, 1);
 7         miGong.addBaffle(3, 2);
 8         miGong.setDes(6, 5); //  Set the destination 
 9 
10         System.out.println(" The initial map ");
11         miGong.show();
12         miGong.setWay(1, 1); //  Set start position 
13 
14         System.out.println(" The path of the ball , The situation of the map ");
15         miGong.show();
16     }
17 }
18 
19 //  result 
20  The initial map 
21 1 1 1 1 1 1 1
22 1 0 0 0 0 0 1
23 1 0 0 0 0 0 1
24 1 1 1 0 0 0 1
25 1 0 0 0 0 0 1
26 1 0 0 0 0 0 1
27 1 0 0 0 0 0 1
28 1 1 1 1 1 1 1
29  The path of the ball , The situation of the map 
30 1 1 1 1 1 1 1
31 1 2 0 0 0 0 1
32 1 2 2 2 0 0 1
33 1 1 1 2 0 0 1
34 1 0 0 2 0 0 1
35 1 0 0 2 0 0 1
36 1 0 0 2 2 2 1
37 1 1 1 1 1 1 1

3、 ... and 、 Eight queens question

   problem : stay 8×8 GE's chess set eight queens , Make it impossible to attack each other , namely : No two Queens can be in the same line 、 On the same column or slash , Ask how many kinds of pendulum .

   Code example : Eight queens

 1 public class Queue8 {
 2 
 3     private static final int MAX = 8;
 4     //  Save where the queen is placed , such as  arr = {0, 4, 7, 5, 2, 6, 1, 3}
 5     private final int[] array = new int[MAX];
 6 
 7     public static int count = 0;
 8     public static int judgeCount = 0;
 9 
10     public void check() {
11         this.check(0);
12     }
13 
14     // check  It's every recursion , Enter into check There are  for(int i = 0; i < max; i++), So there will be backtracking 
15     private void check(int n) {
16         // n = 8,  Express 8 The queen has put it away 
17         if (n == MAX) {
18             print();
19             return;
20         }
21 
22         for (int i = 0; i < MAX; i++) {
23             array[n] = i;
24 
25             //  Judge when placing the n A queen to i Column time , Conflict or not 
26             //  No conflict 
27             if (!judge(n)) {
28                 //  Go on n+1 A queen , It starts recursion 
29                 check(n + 1);
30             }
31         }
32     }
33 
34     private boolean judge(int n) {
35         judgeCount++;
36         for (int i = 0; i < n; i++) {
37             //  The same column   or   The same slash 
38             if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
39                 return true;
40             }
41         }
42         return false;
43     }
44 
45     private void print() {
46         count++;
47         for (int i = 0; i < array.length; i++) {
48             System.out.print(array[i] + " ");
49         }
50         System.out.println();
51     }
52 
53 }

   Code example : Test class

 1 //  Test class 
 2 public class Main {
 3 
 4     public static void main(String[] args) {
 5         Queue8 queue8 = new Queue8();
 6         queue8.check();
 7 
 8         System.out.printf(" Altogether %d solution ", Queue8.count);
 9         System.out.printf(" Judge the number of conflicts %d Time ", Queue8.judgeCount); // 1.5w
10     }
11 }

Four 、 The hanotta problem

1、 problem

2、 thought

   If n = 1,A -> C
   If n >= 2, It's always seen as two plates ,① The bottom plate .② All the disks above . be , step :
  (1) First put all the plates on it A->B
  (2) Put the bottom plate A->C
  (3) hold B All the trays of the tower from B->C

3、 Code

   Code example : The hanotta problem

 1 //  Hanoi 
 2 public class Hanoitower {
 3 
 4     //  Using divide and conquer algorithm 
 5     public static void move(int num, char a, char b, char c) {
 6         //  If there's only one dish 
 7         if (num == 1) {
 8             System.out.println(" The first 1 A dish from  " + a + "->" + c);
 9         } else {
10             // n >= 2, It's always seen as two plates ,① The bottom plate .② All the disks above . be , step :
11 
12             // 1. First put all the plates on it  A->B. The movement process will use  c
13             move(num - 1, a, c, b);
14             // 2. Put the bottom plate  A->C
15             System.out.println(" The first " + num + " A dish from  " + a + "->" + c);
16             // 3. hold  B  All the trays of the tower   from  B->C. The movement process will use  a
17             move(num - 1, b, a, c);
18         }
19     }
20 }

   Code example : Test class

 1 //  Test class 
 2 public class Main {
 3     public static void main(String[] args) {
 4         Hanoitower.move(3, 'A', 'B', 'C');
 5     }
 6 }
 7 
 8 //  result 
 9  The first 1 A dish from  A->C
10  The first 2 A dish from  A->B
11  The first 1 A dish from  C->B
12  The first 3 A dish from  A->C
13  The first 1 A dish from  B->A
14  The first 2 A dish from  B->C
15  The first 1 A dish from  A->C

 

版权声明
本文为[Craftsman-L]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/09/20210909132313688l.html

Scroll to Top