Data structure and algorithm (XI) -- algorithm recursion

Craftsman-L 2021-09-15 07:46:02
data structure algorithm xi algorithm


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://javamana.com/2021/09/20210909132313688l.html

  1. 小白也能看懂的dubbo3应用级服务发现详解
  2. SpringBoot异步使用@Async原理及线程池配置
  3. Questions d'entrevue de test avancé de Dachang, liste des compétences de base de l'entrevue Java,
  4. SpringBoot异步使用@Async原理及線程池配置
  5. Springboot utilise asynchrone le principe @ async et la configuration du pool de threads
  6. Détails de la découverte du Service d'application Dubbo 3 que Xiaobai peut également comprendre
  7. Springboot utilise asynchrone le principe @ async et la configuration du pool de threads
  8. 如何强大且优雅的搞定Linux文件系统,算法题 JVM,
  9. 太牛了,阿里P7架构师带你看透maven的来龙去脉,
  10. Oracle central et Oracle décentralisé
  11. java JavaBean
  12. Java wrapper type
  13. Java super keyword
  14. Java static keyword
  15. Java this keyword
  16. Java interface
  17. 太牛了,阿裏P7架構師帶你看透maven的來龍去脈,
  18. C'est génial, l'architecte Ali p7 vous montre à travers Maven.
  19. Comment traiter le système de fichiers Linux avec puissance et élégance, algorithme JVM,
  20. Java + SSM Social Insurance Pension System for Computer Graduation Design
  21. Usage of Java scanner
  22. Java inheritance
  23. Java method review
  24. java JVM
  25. Java Basics
  26. Java file operation object IO stream
  27. Java console reads multi character input and output
  28. Java simple array sorting
  29. In addition to MySQL master-slave, you have another choice, Galera
  30. Configuration standard dockerfile et docker-composer.yml
  31. 字节大神强推千页PDF学习笔记,2021Java开发学习路线,
  32. 字节大牛耗时八个月又一力作,靠这份Java知识点PDF成功跳槽,
  33. 字节大牛教你手撕Java学习,最新大厂程序员进阶宝典,
  34. Comment l'automne est - il beau?Ces 24 ensembles de modèles d'automne et d'hiver sont grands, minces et vieillissants
  35. 字節大牛教你手撕Java學習,最新大廠程序員進階寶典,
  36. 字節大牛耗時八個月又一力作,靠這份Java知識點PDF成功跳槽,
  37. Byte Bull vous apprend à déchiqueter Java à la main, le dernier dictionnaire avancé des programmeurs de grandes usines,
  38. Byte Bull a pris huit mois à travailler dur et a réussi à changer d'emploi avec ce PDF Java Knowledge point.
  39. Byte God Push 1000 pages PDF Learning notes, 2021 Java Development Learning route,
  40. Five minutes to understand MySQL index push down
  41. Spring中@within与@target的一些区别
  42. 力荐:提高千倍效率的一些 Java 代码小技巧
  43. Redis技术专题系列之帮你从底层彻底吃透RDB技术原理(基础篇)
  44. Juan Benet et vitalik buterin discutent des réflexions sur les médias sociaux décentralisés
  45. Ipfs Weekly Report 152 | pinata launched "submarining"
  46. Performance optimization issue 03 - HTTP request optimization
  47. JavaScript genrator generator
  48. 字节跳动Java面试全套真题解析在互联网火了,面试大厂应该注意哪些问题?
  49. 字节跳动Java社招,2021年阿里 腾讯 快手offer都已拿到!
  50. 用Java实现红黑树
  51. 使用Redis Stream来做消息队列和在Asp.Net Core中的实现
  52. 海量列式非关系数据库HBase 架构,shell与API
  53. Redis Technology Topic Series vous aide à comprendre les principes de la technologie rdb du Bas (Basic)
  54. Conseils: quelques conseils pour améliorer l'efficacité du Code Java
  55. Quelques différences entre @ within et @ Target au printemps
  56. 海量列式非關系數據庫HBase 架構,shell與API
  57. Architecture, Shell et API de base de données non relationnelle à grande échelle
  58. Mise en œuvre de l'arbre Rouge et noir en Java
  59. Byte Hopping Java Service Call, 2021 Alibaba Tencent Express offer a été obtenu!
  60. Byte Jump Java interview Full Set of true Problems Analysis in Internet fire, interview Factory should pay attention to what Problems?