算法 一、分治回溯

目录

一、递归

定义1、求前n项和

思路代码 2、斐波那契数列

思路代码 3、二分查找

思路代码 二、分治算法

定义1、文件夹遍历

思路代码 2、棋盘覆盖问题（重点）

问题说明思路代码 3、汉诺塔（重点）

问题说明思路代码 三、回溯算法

1、全排列

代码 2、迷宫问题

问题说明代码 3、八皇后问题

问题说明思路代码 3、数独问题（重点）

问题说明思路代码

代码说明

一、递归 定义

程序调用自身的编程技巧称为递归( recursion)

//比如
public static void show() {
show();
}

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。如果没有边界条件，就会一直调用下去，会栈溢出报错。

当边界条件不满足时，便会一直调用自己，直到边界条件，为递归前进段。

到边界条件之后就开始逐渐弹栈，为递归返回段

1、求前n项和 思路

比如5的前n项和是5+4+3+2+1，即

前5项和=5+前4项和

前4项和=4+前3项和

…

所以求前n项和，便可以使用递归

代码

package p4.分治回溯;

public class RecursionDemo01 {
    public static void main(String[] args) {
        int ret = f(100);
        System.out.println(ret);
    }

    private static int f(int n) {
        if (n == 1) {   //递归边界条件
            return 1;
        }
        return f(n - 1) + n;
    }
}

这里可以看出时间复杂度便是On

2、斐波那契数列 思路

有个很经典的问题就是不死神兔的问题，这里就不讲了，数列规则

1，1，2，3，5，8…

就是后面的数等于前面两个数之和。f(n)表示第n个元素

所以就有f(n)=f(n-1)+f(n-2);

又f(n-1)=f(n-2)+f(n-3)，f(n-2)=f(n-3)+f(n-4)

…

递归便体现出来了

代码

package p4.分治回溯;

public class RecursionDemo02 {
    public static void main(String[] args) {
        int ret = f(50);
        System.out.println(ret);
    }

    private static int f(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return f(x - 1) + f(x - 2);
    }
}

时间复杂度O(n²)

3、二分查找 思路

首先给你一个顺序数组，然后对比中间的数，

大了就把前面一段在当成数组，再次对比…

代码

package p4.分治回溯;

public class RecursionDemo03 {
    public static void main(String[] args) {
        //二分查找 折半查找
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        int index = binarySearch(arr,0, arr.length - 1, 13);
        System.out.println(index);
    }
    //在数组arr中 L~R区间内进行二分搜索查找key的角标
    private static int binarySearch(int[] arr, int L, int R, int key) {
        if (L > R) {    //元素key不存在
            return -1;
        }
        int M = (L + R) / 2;
        if (arr[M] == key) {
            return M;
        }
        if (arr[M] < key) {
            return binarySearch(arr,M + 1, R, key);
        } else {
            return binarySearch(arr,L, M - 1, key);
        }
    }
}

---

二、分治算法 定义

分治算法就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治算法的递归实现中，每一层递归都会涉及这样三个操作

分解：将原问题分解成一系列子问题
解决：递归地求解各个子问题，若子问题足够小，则直接求解.
合并：将子问题的结果合并成原问题

分治算法能解决的问题，一般需要满足下面这几个条件

◆ 原问题与分解成的小问题具有相同的模式
◆ 原问题分解成的子问题可以独立求解，子问题之间没有相关性

◆ 具有分解终止条件，也就是说，当问题足够小，可以直接求解
◆ 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了

1、文件夹遍历 思路

打印该目录下的所有文件和文件夹

先将第一层遍历，文件直接打印名字

遍历到子文件夹便再次遍历值文件夹

…

代码

package p4.分治回溯;

import java.io.File;

public class RecursionDemo05 {
    public static void main(String[] args) {
        File dir = new File("ceshi");//同目录下的ceshi文件夹
        traversal(dir);
    }

    private static void traversal(File dir) {
        File[] files = dir.listFiles();
        if (files.length == 0) {
            return;
        }
        for (File file : files) {
            if (file.isFile()) {
                System.out.println(file.getName());
            } else {
                System.out.println("【" + file.getName() + "】");
                traversal(file);
            }
        }
    }
}

2、棋盘覆盖问题（重点） 问题说明

在一个2kx2k (k≥0)个方格组成的棋盘中，恰有一一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4k种，因而有4k种不同的棋盘。棋盘覆盖问题要求用4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

思路

首先2×2方格，很简单

然后把2成2扩展到4成4，我们先把4×4方格分成2×2方格，然后在没有特殊方格的边角添上L型骨牌，分别覆盖三个2×2方格，然后再次像2×2那样操作

接下来8×8。首先拆分成4×4，然后一样的思路

…

所以有没有发现一样的思路呢？

代码

我们把这个方格当成数组，特殊方格用0表示，不同的L型骨牌，用不同的数组表示，一个L型骨牌，用三个相同的数组表示。

package p4.分治回溯;

import java.util.Scanner;

//棋盘覆盖问题
public class ChessBoardCoverage {
    private static int BOARD_SIZE = 8;
    private static int[][] board = new int[BOARD_SIZE][BOARD_SIZE];
    //代表颜色 同一组L骨牌 编号应该是一样的
    private static int title = 0;   // 0就是特殊方格的存在

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print(">>>请输入特殊方格的角标信息：");
        //dr dc 指的是特殊方格的坐标
        int dr = input.nextInt();
        int dc = input.nextInt();

        chessBoard(0, 0, dr, dc,BOARD_SIZE);
        printBoard();
    }

    private static void printBoard() {
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                System.out.print(board[i][j] + "t");
            }
            System.out.println();
        }
    }

    //在size*size的矩阵中 以tr tc为四部分子矩阵的基点 dr dc是特殊矩阵的位置 进行填充
    private static void chessBoard(int tr, int tc, int dr, int dc, int size) {
        //判断递归结束 如果尺寸为1 则不可继续拆分 则返回 归
        if (size == 1) {
            return;
        }

        //该层要填充L型骨牌 编号是一致的
        int num = ++title;
        //该层要继续分四个部分 每个部分的尺寸是多少
        int s = size / 2;

        //判断特殊方格在四个部分中 那个部分里

        //左上
        if (dr < tr + s && dc < tc + s) {
            chessBoard(tr,tc,dr,dc,s);
        } else {
            board[tr + s - 1][tc + s - 1] = num;
            chessBoard(tr,tc,tr + s - 1,tc + s - 1,s);
        }

        //右上
        if (dr < tr + s && dc >= tc + s) {
            chessBoard(tr,tc + s,dr,dc,s);
        } else {
            board[tr + s - 1][tc + s] = num;
            chessBoard(tr,tc + s,tr + s - 1,tc + s,s);
        }

        //左下
        if (dr >= tr + s && dc < tc + s) {
            chessBoard(tr + s,tc,dr,dc,s);
        } else {
            board[tr + s][tc + s - 1] = num;
            chessBoard(tr + s,tc,tr + s,tc + s - 1,s);
        }

        //右下
        if (dr >= tr + s && dc >= tc + s) {
            chessBoard(tr + s,tc + s,dr,dc,s);
        } else {
            board[tr + s][tc + s] = num;
            chessBoard(tr + s,tc + s,tr + s,tc + s,s);
        }
    }

}

输出

3、汉诺塔（重点） 问题说明

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

简单的说，就是需要把这边所有的圆盘按原来从大到小顺序放在另一根柱子上，规则：每次只能移动一个圆盘，并且大圆盘不能放在小圆盘之上。

很多小程序都有这个游戏，可以多玩玩，找找规律

思路

如果把64个圆盘从X移到Z，那么，就要先将前63个圆盘移到Y，这样第64 个圆盘才能移到Z

那么前63个圆盘怎么移到Y？那就需要将前62个圆盘移到Z，然后第63个圆盘才能移到Y

…

那现在第64个圆盘已经移到Z了，那么需要将前53个圆盘移到Z，就是和上面一样的方法了…

如果不好理解，那就先玩几局，玩的时候对照着讲的这个理解一下

代码

package p4.分治回溯;

public class Hanoi {
    public static void main(String[] args) {
        String x = "X";
        String y = "Y";
        String z = "Z";
        hanoi(3,x,y,z);
    }
    private static void hanoi(int n, String begin, String mid, String end) {
        if (n == 1) {
            System.out.println(begin + "->" + end);
        } else {
            hanoi(n - 1,begin, end, mid);
            System.out.println(begin + "->" + end);
            hanoi(n - 1,mid, begin, end);
        }
    }
}

---

三、回溯算法

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索，以达到目标。但当探索到某一步时， 发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就回退再走的技术称为回溯法，而满足回溯条件的某个状态的点称为“回溯”点。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法"的美称

简而言之：就是从一条路往前走，能进则进，不能进则退回来，换一条路再试。

直接在案例中理解。

1、全排列

比如实现A B C的全排列

代码执行过程

首先确定第一个字母A
  然后确定第二个字母B
​    然后确定第三个字母C
​    第一个排序可能
​    在看第三个字母是否还有其他个可能，没有了
​  回溯到第二个字母
​  第二个字母还可以是C
​​    再看第三个字母是B
​​    第二个排序可能
​​    在看第三个字母是否还有其他个可能，没有了
​  回溯到第二个字母
​  看第二个字母还是否有其他可能，没有了
回溯到第一个字母
第一个字母还可以是B
  然后确定第二个字母
…

代码

package p4.分治回溯;

import java.util.HashSet;

//全排列
public class FullPermutation {
    public static void main(String[] args) {
        String s = "ABB";
        char[] arr = s.toCharArray();
        HashSet set = new HashSet<>();
        permutation(set, arr, 0, arr.length - 1);
        System.out.println(set);
    }
    private static void permutation(HashSet set, char[] arr, int from, int to) {
        if (from == to) {
            set.add(String.valueOf(arr));    //[A,B,C] => "ABC"
        } else {
            for (int i = from; i <= to; i++) {
                swap(arr, i, from);
                permutation(set, arr, from + 1, to);
                swap(arr, i, from);
            }
        }
    }
    private static void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2、迷宫问题 问题说明

规则就不用讲了吧，如果我们走的路这条路不通，我们就会回到上一个路口进行下一次尝试

按上右下左的顺序，如果上面是路就走上面，如果上面是墙或者已经尝试过，就走右面
我们需要一个栈，把做过的路压入栈中，这样，若这条路不通，便弹栈，到上一个路口，若此路通，便按顺序弹栈，便是迷宫路线

代码

还是用数组代表方格，1代表墙，0代表路，还需要定义一个数组，代表这条路是否走过了

package p4.分治回溯;

import p3.链式结构.linkedList;

public class Maze {
    private static int[][] maze = {
            {1, 1, 1, 1, 1, 1, 1, 1, 1},
            {0, 0, 1, 0, 0, 0, 1, 1, 1},
            {1, 0, 1, 1, 1, 0, 1, 1, 1},
            {1, 0, 0, 1, 0, 0, 1, 1, 1},
            {1, 1, 0, 1, 1, 0, 0, 0, 1},
            {1, 0, 0, 0, 0, 0, 1, 0, 1},
            {1, 0, 1, 1, 1, 0, 0, 0, 1},
            {1, 1, 0, 0, 0, 0, 1, 0, 0},
            {1, 1, 1, 1, 1, 1, 1, 1, 1}
    };
    //入口信息
    private static int entryX = 1;
    private static int entryY = 0;
    //出口信息
    private static int exitX = 7;
    private static int exitY = 8;
    //路径访问状态表
    private static boolean[][] vistied = new boolean[9][9];
    //方向的变化量
    private static int[][] direction = {
            {1, 0}, {0, 1}, {0, -1}, {-1, 0}
    };
    //存储路径的栈
    private static linkedList stack = new linkedList<>();

    public static void main(String[] args) {
        boolean flag = go(entryX, entryY);
        if (flag) {
            for (String path : stack) {
                System.out.println(path);
            }
        } else {
            System.out.println("迷宫不通！");
        }
    }

    //以x,y为入口 看是否能够向下找到出口 返回false找不到
    private static boolean go(int x, int y) {
        stack.push("(" + x + "," + y + ")");
        vistied[x][y] = true;
        if (x == exitX && y == exitY) {
            return true;
        }
        //考虑四个方向 上 右 下 左
        for (int i = 0; i < direction.length; i++) {
            int newX = direction[i][0] + x;
            int newY = direction[i][1] + y;
            if (isInArea(newX, newY) && isRoad(newX, newY) && !vistied[newX][newY]) {
                if (go(newX, newY)) {
                    return true;    //某一个方向能通 则向上返回true 表示此层次x y能通
                }
            }
        }
        stack.pop();
        return false;   //四个方向都不通 则向上返回false 表示此次层x y 不通
    }

    private static boolean isRoad(int x, int y) {
        return maze[x][y] == 0;
    }

    private static boolean isInArea(int x, int y) {
        return x >= 0 && x < 9 && y >= 0 && y < 9;
    }
}

3、八皇后问题 问题说明

在一个方格中，问皇后有几种排列法

要求：

1：皇后的个数要和方格的阶数相同，比如8×8方格，皇后就要是8个

2：每一行只能有一个皇后

3：每一列只能有一个皇后

4：每一个斜边只能有一个皇后

思路

首先确定第一行的皇后位置
​  再确定第二行的皇后位置
  第一个位置不行，第二个位置不行，第三个位置可以，便确定位置
    再确定第三行皇后位置
    发现遍历完方格，没有可以放皇后的位置
  回溯到第二层，皇后还可以放在第四个位置
    再确定第三层皇后，发现不行
  回溯到第二层，发现没有其他情况了
回溯到第一层
第一层皇后还可以在第二个位置
  第二层…

这里我们可以看出，我们是以行为一个单元，确定一行之后，就开始确定下一行

代码

还是把数组当成方格，0表示方格，1表示皇后

package p4.分治回溯;
//N皇后问题
public class NQueen {
    private static int count = 0;   //记录解的个数
    private static final int N = 8; //N皇后 矩阵的尺寸
    private static int[][] arr = new int[N][N]; //棋盘数据 0表示空 1表示皇后
    public static void main(String[] args) {
        queen(0);
    }
    //递归的解决row角标行 皇后的问题 如果row == N 说明一个解就出来了
    private static void queen(int row) {
        if (row == N) {
            count++;
            System.out.println("第" + count + "个解：");
            printArr();
        } else {
            //遍历当前行的列
            for (int col = 0; col < N; col++) {
                if (!isDangerous(row, col)) {
                    //每次要放置皇后的时候 都先对该行进行清空
                    for (int c = 0; c < N; c++) {
                        arr[row][c] = 0;
                    }
                    arr[row][col] = 1;
                    queen(row + 1);
                }
            }
        }
    }
    private static boolean isDangerous(int row, int col) {
        //向上
        for (int r = row - 1; r >= 0; r--) {
            if (arr[r][col] == 1) {
                return true;
            }
        }
        //左上
        for (int r = row - 1, c = col - 1; r >= 0 && c >= 0; r--, c--) {
            if (arr[r][c] == 1) {
                return true;
            }
        }
        //右上
        for (int r = row - 1, c = col + 1; r >= 0 && c < N; r--, c++) {
            if (arr[r][c] == 1) {
                return true;
            }
        }
        return false;
    }

    private static void printArr() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}

3、数独问题（重点） 问题说明

给你一个如图所示的数据，需要你在空格地方添上数字

规则

1：填写内容，数字1~9

2：每行、每列不能有相同数字

3：每一个三元格（即图中3×3的加粗方格）中不能有相同数组

思路

和上面的皇后问题相似，只不过皇后问题是确定一行后看下一行，数独是确定一个格子，看下一个格子

这里就不细讲

当确定这个格子时，需要看这个数字是否符合往下走，还是回溯，如果这个格子是给了数字，就直接跳到下一个格子

代码 代码说明

数据使用读文本的方式

在同目录下，新建一个suduku_data_01.txt文件

里面内容：

530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

这就相当于数独的数据，0表示我们需要填写的位置

package p4.分治回溯;

import java.io.*;
//数独
public class Sudoku {
    private static int i = 0;
    private static int[][] board = new int[9][9];

    public static void main(String[] args) throws IOException {
        readFile("sudoku_data_01.txt");
        solve(0, 0);
    }

    //求解x-y格子的解 再继续向下递归求解下一个格子
    //本质求多个解 但实际 数独问题只能有一个解 如果没解 程序啥也不输出！
    private static void solve(int row, int col) {
        if (row == 9) {
            i++;
            System.out.println("===========" + i + "==========");
            printBoard();
            //System.exit(0);
        } else {
            if (board[row][col] == 0) {
                //需要填数字1~9
                for (int num = 1; num <= 9; num++) {
                    if (!isExist(row, col, num)) {
                        board[row][col] = num; //8
                        //解决下一个格子
                        solve(row + (col + 1) / 9, (col + 1) % 9);
                    }
                    //如果此处没解 必须清零
                    board[row][col] = 0;
                }
            } else {
                //已经存在一个已知数字 直接跳过去解决下一个格子
                solve(row + (col + 1) / 9, (col + 1) % 9);
            }
        }
    }

    private static boolean isExist(int row, int col, int num) {
        //同行
        for (int c = 0; c < 9; c++) {
            if (board[row][c] == num) {
                return true;
            }
        }

        //同列
        for (int r = 0; r < 9; r++) {
            if (board[r][col] == num) {
                return true;
            }
        }

        //同九宫 3*3
        int rowMin = 0;
        int colMin = 0;

        int rowMax = 0;
        int colMax = 0;

        if (row >= 0 && row <= 2) {
            rowMin = 0;
            rowMax = 2;
        }
        if (row >= 3 && row <= 5) {
            rowMin = 3;
            rowMax = 5;
        }
        if (row >= 6 && row <= 8) {
            rowMin = 6;
            rowMax = 8;
        }
        if (col >= 0 && col <= 2) {
            colMin = 0;
            colMax = 2;
        }
        if (col >= 3 && col <= 5) {
            colMin = 3;
            colMax = 5;
        }
        if (col >= 6 && col <= 8) {
            colMin = 6;
            colMax = 8;
        }

        for (int r = rowMin; r <= rowMax; r++) {
            for (int c = colMin; c <= colMax; c++) {
                if (board[r][c] == num) {
                    return true;
                }
            }
        }

        return false;
    }

    private static void readFile(String fileName) throws IOException {
        File file = new File(fileName);
        FileReader fr = new FileReader(file);
        BufferedReader br = new BufferedReader(fr);
        String line = null;
        int row = 0;
        while ((line = br.readLine()) != null) {
            for (int col = 0; col < 9; col++) {
                board[row][col] = Integer.parseInt(line.charAt(col) + "");
            }
            row++;
        }
    }

    private static void printBoard() {
        for (int i = 0 ; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }
}