目录
1递归
1.1递归定义
1.它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
2.一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
1.2前n项求和问题
1.3斐波那契数列问题
1.3.1斐波那契数列问题代码
package P4.分治回溯;
public class RecursionDemo03 {
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);
}
}1.4分治算法
分治算法就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治算法的递归实现中，每一层递归都会涉及这样三个操作：
分解：将原问题分解成一系列子问题
解决：递归地求解各个子问题，若子问题足够小，则直接求解
合并：将子问题的结果合并成原问题
分治算法能解决的问题，一般需要满足下面这几个条件：
原问题与分解成的小问题具有相同的模式
原问题分解成的子问题可以独立求解，子问题之间没有相关性
具有分解终止条件，也就是说，当问题足够小，可以直接求解
可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了
1.5回溯算法
回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就回退再走的技术称为回溯法，而满足回溯条件的某个状态的点称为“回溯”点。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
从一条路往前走，能进则进，不能进则退回来，换一条路再试。
1.5全排列
package P4.分治回溯;
import java.util.HashSet;
//全排列
public class FullPermutation {
public static void main(String[] args) {
String s = "ABC";
char[] arr = s.toCharArray();
HashSet<String> set = new HashSet<>();
permutation(set ,arr,0,arr.length-1);
System.out.println(set);
}
private static void permutation(HashSet<String> set, char[] arr, int from, int to) {
if(from == to){
set.add(String.valueOf(arr));
}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 from) {
char temp = arr[i];
arr[i] = arr[i];
}
}1.6棋盘覆盖问题
1.6棋盘覆盖问题代码
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);
}
}
}1.7汉诺塔问题
汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
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.8迷宫问题
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, 1, 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}, {1, 0}, {0, -1}
};
//存储路径的栈
private static LinkedList<String> 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;
}
}1.9N皇后问题
在一个8×8的棋盘中，放入8个皇后棋子 要求同行同列同斜线不能有重复的皇后棋子
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();
}
}
}
1.10数独问题
每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复
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();
}
}
}