Comment utiliser les structures de données et les algorithmes Java pour implémenter la récursivité et le retour en arrière

1. Qu'est-ce que la récursivité ?

En termes simples : la récursion signifie que la méthode s'appelle elle-même, en passant différentes variables à chaque fois qu'elle est appelée. La récursion aide les programmeurs à résoudre des problèmes complexes et en même temps rend le code concis.

Regardez un scénario d'application pratique, problème de labyrinthe (backtracking), récursion (Recursion)

# 🎜 🎜#Je vais énumérer deux petits cas pour vous aider à comprendre la récursivité. Ici, je vais passer en revue le mécanisme d'appel récursif

• Imprimer la question

  #. 🎜🎜#

Problème factoriel

• public static void test(int n) {
      if (n > 2) {
  	    test(n - 1);
      }
      System.out.println("n=" + n);
  }
   
  public static int factorial(int n) {
      if (n == 1) {
          return 1;
      } else {
          return factorial(n - 1) * n;
      }
  }

Quels types de problèmes la récursivité est-elle utilisée pour résoudre ? 🎜 #

Divers problèmes mathématiques tels que : problème des 8 reines, Tour de Hanoï, problème factoriel, problème du labyrinthe, problème du ballon et du panier (concours de programmation Google).

• La récursion est également utilisée dans divers algorithmes, tels que le tri rapide, le tri par fusion, la recherche binaire, l'algorithme diviser pour régner, etc.

• Le problème qui sera résolu avec la stack-->Le code est relativement concis.

• Règles importantes à suivre pour la récursion

Lorsqu'une méthode est exécutée, une nouvelle méthode protégée est créée espace indépendant (espace pile).

• Les variables locales de la méthode sont indépendantes et ne s'affecteront pas, comme par exemple n variables.

• Si une variable de type référence (comme un tableau) est utilisée dans la méthode, les données du type référence seront partagées.

• La récursion doit s'approcher des conditions de sortie de la récursion, sinon ce sera une récursivité infinie, une StackOverflowError apparaîtra, et vous serez mort :).

• Lorsqu'une méthode termine son exécution ou rencontre un retour, le résultat sera renvoyé à celui qui l'appelle en même temps, lorsque la méthode terminera son exécution ou. renvoie , la méthode sera exécutée.

• 2. Cas de code 1 - Problème de labyrinthe

Description : Le chemin emprunté par la balle, lié à la stratégie de recherche de chemin définie par le programmeur, c'est-à-dire : liée à l'ordre haut, bas, gauche et droite lors de la recherche du chemin. Lorsque vous obtenez le chemin de la balle, vous pouvez d'abord utiliser (en bas à droite, en haut à gauche) , puis remplacez-le par (en haut à droite, en bas à gauche) et voyez si le chemin n'est pas qu'il y a un changement. Test des phénomènes de retour en arrière.

package com.szh.recursion;
 
/**
 * 走迷宫问题
 */
public class MiGong {
 
    //使用递归回溯来给小球找路, 说明:
    //1. map 表示地图
    //2. i,j 表示从地图的哪个位置开始出发 (1,1)
    //3. 如果小球能到 map[6][5] 位置，则说明通路找到.
    //4. 约定：当 map[i][j] 为 0 表示该点没有走过; 当为 1 表示墙; 2 表示通路可以走;
    //5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
    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 { //左
                    return true;
                }
            } else { //map[i][j] != 0, 即只能为1、2。 1表示墙（无法走），2表示已经走过了，所以此时直接返回false
                return false;
            }
        }
    }
 
    //修改找路的策略，改成 上->右->下->左
    public static boolean setWay2(int[][] map, int i, int j) {
        if(map[6][5] == 2) { // 通路已经找到ok
            return true;
        } else {
            if(map[i][j] == 0) { //如果当前这个点还没有走过
                //按照策略 上->右->下->左
                map[i][j] = 2;
                if(setWay2(map, i - 1, j)) { //上
                    return true;
                } else if (setWay2(map, i, j + 1)) { //右
                    return true;
                } else if (setWay2(map, i + 1, j)) { //下
                    return true;
                } else { //左
                    return true;
                }
            } else {
                return false;
            }
        }
    }
 
    public static void main(String[] args) {
        //先创建一个二维数组，模拟迷宫 (地图)
        int[][] map = new int[8][7];
        //使用迷宫中的部分格子表示墙体（置1）
        //第一行和最后一行置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //第一列和最后一列置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }
        //多添加两块墙体
        map[3][1] = 1;
        map[3][2] = 1;
//      map[1][2] = 1;
//		map[2][2] = 1;
        //输出地图查看
        System.out.println("原始迷宫地图为：");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
 
        //使用递归回溯走迷宫
        setWay(map, 1, 1);
//        setWay2(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] + " ");
            }
            System.out.println();
        }
    }
}

3. Cas de code 2——Problème des huit reines

八Le Le problème de la Reine est un problème ancien et célèbre et un cas typique d'algorithme de retour en arrière. Ce problème a été soulevé par le joueur d'échecs international Max Bethel en 1848 : placez huit dames sur une grille d'échecs 8×8 afin qu'elles ne puissent pas s'attaquer, c'est-à-dire : il n'y a pas deux dames dans la même position. en lignes, colonnes ou diagonales ?

La première reine est placée en premier dans la première rangée et dans la première colonne.

Placez la deuxième reine dans la deuxième rangée et la première colonne, puis déterminez si elle est OK. Sinon, continuez à la placer dans la deuxième colonne et la troisième colonne. Placez toutes les colonnes dans l'ordre et trouvez. Un modèle approprié.

Continuez vers la troisième reine, ou la première colonne, la deuxième colonne... jusqu'à ce que la 8ème reine puisse être placée dans une position non conflictuelle, j'ai trouvé une solution correcte.

Lorsqu'une solution correcte est obtenue, lorsque la pile revient à la pile précédente, elle commencera à revenir en arrière, c'est-à-dire qu'elle mettra la première reine dans la première colonne et toutes les solutions correctes seront obtenues.

Puis revenez en arrière et continuez à placer la première reine dans la deuxième colonne, et continuez à effectuer les étapes 1, 2, 3 et 4 en boucle.

package com.szh.recursion;
 
/**
 * 八皇后问题
 */
public class Queue8 {
 
    //定义max表示共有多少个皇后
    private int max = 8;
    //定义数组，保存皇后放置的位置结果，比如 arr = {0, 4, 7, 5, 2, 6, 1, 3}
    int[] array = new int[max];
    //共有多少种解法
    private static int count = 0;
    //共有多少次冲突
    private static int judgeCount = 0;
 
    //编写一个方法，放置第n个皇后
    //特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
    private void check(int n) {
        if (n == max) { //n = 8 , 表示这8个皇后已经全部放好了
            print();
            return;
        }
        //依次放入皇后，并判断是否冲突
        for (int i = 0; i < max; i++) {
            //先把当前这个皇后 n , 放到该行的第1列
            array[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if (judge(n)) { // 不冲突
                //接着放n+1个皇后,即开始递归
                check(n + 1);
            }
            //如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行第i列向后的那一列
        }
    }
 
    //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的n-1个皇后冲突
    private boolean judge(int n) {
        //每摆放一个皇后，就循环去和之前摆好的皇后位置相比较，看是否冲突
        for (int i = 0; i < n; i++) {
            //1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
            //2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
            //3. 判断是否在同一行, 没有必要，n 表示第几个皇后，这个值每次都在递增，所以必然不在同一行
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                judgeCount++;
                return false;
            }
        }
        return true;
    }
 
    //打印皇后摆放的具体位置
    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.printf("一共有%d解法\n", count);
        System.out.printf("一共判断冲突的次数%d次", judgeCount);
    }
}

En fait, vous pouvez voir le processus de retour en arrière en débogant le code ici, donc je ne dirai pas plus.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!