跳到主要内容

01、数据结构与算法 - 实战：递归和回溯

递归：任何调用自身的函数称为递归。
用递归方法求解的要点在于递归函数调用自身解决一个规模比原始问题小一些的问题。
函数不在递归的情况称为基本情形；而函数调用自身执行子任务的情况称为递归情形。

经典题目：汉诺塔

  • 汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。
  • 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
  • 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
  • 并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

算法思路：

  • 将源柱最上面的n-1个盘子移动到辅助的柱子上

  • 将源柱上第n个盘子移动到目标柱

  • 将辅助柱的n-1个盘子移动到目标柱

  • 假设A为源柱（此时A上有n个盘子），B为辅助柱，C为目标柱

  • 1.先将A上面的n-1个盘子移动到B上面（此时B上面有n-1个盘子）

  • 2.再将A上的第n个个盘子移动到C上面（此时A上面已经没有盘子）

  • 3.最后将B上的n-1个盘子借助A移动到C上面（此时可以把B看做源柱，A看做辅助柱，C仍然是目标柱）

Java程序如下：

/**
 * 汉诺塔
 * @param n 盘子个数
 * @param from 源柱
 * @param assist 辅助柱
 * @param to 目标柱
 */
public static void Hanio(int n, char from, char assist, char to) {
    if (n == 1) {
        // 仅有一个盘子，直接从源柱(A)移动到目标柱(C)
        System.out.println("Move disk :" + from + " ----> " + to);
    } else {
        // 先将源柱(A)上n-1盘子移动到辅助柱(B)上
        Hanio(n-1, from, to, assist);
        // 再将源柱(A)上第n个盘子移动到目标柱(C)上
        System.out.println("Move disk :" + from + " ----> " + to);
        // 最后将辅助柱(B)上的n-1个盘子移动到目标柱(C)
        Hanio(n-1, assist, from, to);
    }
}

回溯：是一种穷举搜索的方法。主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。

经典题目：生成所有n位的二进制串

输入1输出 0、1
输入2输出00、01、10、11

Java程序如下：


import java.util.Scanner;

/**
 * 题目：生成所有n位的二进制串
 * 例如：输入1
 *      输出 0、1
 *  输入2
 *  输出00、01、10、11
 */
public class Back_Track {
   
     

    // 大小为n的数组，存储二进制串
    public static int[] A;

    // 要生成的二进制串的位数
    public static int x;

    public static void main(String[] args) {
        System.out.println("功能：生成所有n位的二进制串");

        // 获取输入的位数
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入一个整数n:");
        int n = scanner.nextInt();

        // 初始化成员变量
        x = n;
        A = new int[n];

        // 生成二进制串
        System.out.println("结果如下所示：");
        binary(n);
    }

    /**
     * 生成所有n位的二进制串
     * @param n 二进制串的位数
     */
    public static void binary(int n) {
        if (n < 1) {
            print();
        } else {
            A[n-1] = 0;
            binary(n -1);
            A[n-1] = 1;
            binary(n -1);
        }
    }

    /**
     * 打印数组内容
     */
    public static void print() {
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i]);
            // 格式化输出，方便查看
            if ((i+1) % x == 0) {
                System.out.println();
            }
        }
    }
}