DFS

思路：
从初始状态出发，下一步可能有多种状态；选其中一个状态深入，到达新的状态；直到无法继续深入，回退到前一步，转移到其他状态，然后再深入下去。最后，遍历完所有可以到达的状态，并得到最终的解。

以下情况下不适合使用递归：

数据量过大：递归需要在每次调用时保存当前状态，并将其压入函数调用栈中。当数据量非常大时，递归可能会导致栈溢出的问题。（见下面第十四题）
重复计算：递归通常会涉及到重复计算相同的子问题。如果这些子问题的计算结果可以被缓存并重复使用，那么使用迭代或其他非递归方法可能更高效。
递归深度过大：递归的深度是指递归调用的层数。当递归深度过大时，可能会导致函数调用栈溢出或者程序崩溃。

在这些情况下，可以考虑使用迭代、循环或其他非递归的方法来解决问题。

递归

递归方法就是直接或间接地调用其自身

注意：

避免进入死循环，栈溢出

容易超时

递归 <——> 非递归，相互转化

迭代和递归的区别

迭代法（Iteration）：

迭代法是通过循环结构来重复执行某段代码，达到解决问题的目的。
在迭代中，程序员需要显式地控制循环的终止条件，以防止无限循环。
迭代通常使用循环结构（如 for 循环、while 循环）来实现。
迭代法通常需要借助一些辅助变量来保存中间结果。

递归（Recursion）：

递归是指一个函数调用自身的过程。
递归问题通常具有递归定义，即问题可以被分解为更小的同类型的子问题。
递归函数需要有递归基（base case），即递归结束的条件，以防止无限递归。
递归函数通常包含两个部分：递归调用和递归基。

总的来说，迭代是通过循环结构重复执行代码解决问题，而递归则是通过函数调用自身来解决问题。在一些情况下，递归代码可能更简洁、易于理解，但可能会导致性能上的一些损失，因为递归调用会增加函数调用的开销和内存消耗。而迭代通常更为直接，并且可以通过优化来提高性能。

回溯

回溯法是一种采用深度优先方式进行搜索的算法，当搜索到某一步时，如果发现原先的选择不是最优选择或者达不到目标，就退回一步重新选择。
剪枝函数：（在回溯中用于减少子结点扩展的函数）
1、约束函数：是问题的可行解吗？
2、限界函数：确定是问题的可行解，但，是问题的最优解吗？
解题步骤：
1、如何递归
2、如何剪枝与回溯

一、计算阶乘

阶乘函数： $n!=\left\{\begin{matrix} 1 &,n=0 \\ n\times (n-1)! & ,n> 0 \end{matrix}\right.$

比如

3！=6
3！= 3*2*1 = 6
4！=24
4！= 4*3*2*1 = 24
5！=120
5！= 5*4*3*2*1 = 120

分析：


package no1_1;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		System.out.println(factorial(n));
	}
	public static int factorial(int n) {
		if(n==0) {
			return 1;
		}else {
			return n*factorial(n-1);
		}
	}
}

二、试题算法训练数字游戏

　　给定一个1～N的排列a[i]，每次将相邻两个数相加，得到新序列，再对新序列重复这样的操作，显然每次得到的序列都比上一次的序列长度少1，最终只剩一个数字。
　　例如:
　　3 1 2 4
　　4 3 6
　　7 9
　　16
　　现在如果知道N和最后得到的数字sum，请求出最初序列a[i]，为1～N的一个排列。若有多种答案，则输出字典序最小的那一个。数据保证有解。

分析：


package no1_1;
 
import java.util.Scanner;
 
public class Main {
	//main()方法是静态方法，它只能调用静态方法，所以dfs()也是静态方法
	//因为两个方法都是静态方法，所以它们共用的属性sum,N等都得是静态的
	static int sum;
	static int N;
	static int arr1[];
	static boolean flag = true;
 
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		N = input.nextInt();
		sum = input.nextInt();
		int array[] = new int[N];
		int usedArray[] = new int[N + 1];
		//开始递归
		dfs(0, array, usedArray, flag);
	}
 
	public static void dfs(int step, int arr[], int usedArray[], Boolean flag) {
		//首先检查当前步数是否等于N，如果是，则表示已经生成了一个完整的排列(最顶层，有N个数的数组)
		if (step == N) {
			//复制该排列到新数组中
			int arr1[] = new int[N];
			for (int i = 0; i < N; i++) {
				arr1[i] = arr[i];
			}
			//从上往下，计算该排列最终得到的数字
			for (int i = 1; i < N; i++) {
				for (int j = 0; j < N - i; j++) {
					arr1[j] = arr1[j] + arr1[j + 1];
				}
			}
			//某排列计算出的数字与题目符合
			if (arr1[0] == sum) {
				//把该排列输出到控制台
				for (int x : arr) {
					System.out.print(x + " ");
				}
				//停止递归
				flag = false;
				//回溯，但不再递归
				return;
 
			} else
				//条件不满足，
				//回溯，继续递归生成下一步的排列
				return;
		}
		//继续递归，生成可能的排列
		if (flag == true) {
			//最初序列arr[i]，为1～N的一个排列
			//在递归生成排列时，使用usedArray数组来标记已经使用过的数字，避免重复使用
			for (int i = 1; i <= N; i++) {
				if (usedArray[i] == 0) {
					arr[step] = i;
					usedArray[i] = 1;
					dfs(step + 1, arr, usedArray, flag);
					usedArray[i] = 0;//取消标记
				}
			}
		}
		return;
	}
}

三、试题算法训练粘木棍

分析：


package no1_1;
import java.util.*;
public class Main {
	static int n,m,result=Integer.MAX_VALUE;
	static int[] array;
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        n=input.nextInt();
        m=input.nextInt();
        array=new int[n];
        for(int i=0;i<n;i++) {
        	array[i]=input.nextInt();
        }
        dfs(n);
        System.out.println(result);
    }
    public static void dfs(int n) {
    	if(n==m) {//到达底部，先验证这次分组是否正确，如果不正确就回溯
            //不用Arrays.sort()方法找最大值和最小值，是为了方便回溯，如果随便改变了数组元素的顺序，就无法正常回溯了
    		int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
    		for(int i=0;i<m;i++) {
    			if(array[i]<min) min=array[i];
    			if(array[i]>max) max=array[i];
    		}
    		result=Math.min(result, max-min);//维护一个最小的差值
    		return ;//停止递归，返回
    	}
    	for(int i=0;i<n;i++) {
    		for(int j=i+1;j<n;j++) {
    			array[i]+=array[j];//合并元素
    			swap(j,n-1);//将废弃的元素丢到数组后面
    			dfs(n-1);//数组长度减一
    			swap(j,n-1);//回溯，交换回来
    			array[i]-=array[j];//把合并的两个元素和拆开
    		}
    	}
    }
    //交换函数
    public static void swap(int a,int b) {
    	int temp=array[a];
    	array[a]=array[b];
    	array[b]=temp;
    }
}

四、试题算法训练 24点

分析：

一组数据里有4个数字
递归，每次处理2个数字，加减乘除（加乘各自只有一种方法，而乘除各自有两种）
把处理结果存放在card[1]的位置，再把最后一个有效数字挪到card[0]的位置，数组有效数字长度-1
每种方法都维护一个不大于24的最大值


package no1_1;
import java.util.*;
public class Main {
	static int max;
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] cards=new int[4];
    	int[] res=new int[n];//存储结果
        for(int i=0;i<n;i++) {
        	//每次只取一组输入数据进行处理，处理完成，再接收下一组输入数据
        	for(int j=0;j<4;j++) {
        		cards[j]=input.nextInt();
        	}
        	max=0;
        	dfs(cards,4);
        	res[i]=max;
        }
        for(int i=0;i<n;i++) {
        	System.out.println(res[i]);
        }
    }
    public static void dfs(int cards[],int n) {
    	//维护一个不大于24的最大值
    	if(n==1) {
    		if(cards[n-1]<=24) {//最终结果保存在数组的第一个位置上，此时有效数据只有一个，其他都运算过舍弃了
        		max=Math.max(max, cards[n-1]);
    		}
    		return;
    	}
    	for(int i=0;i<n-1;i++) {
    		for(int j=i+1;j<n;j++) {
    			int a=cards[i],b=cards[j];
    			
    			//a+b=b+a，加法具有交换律
    			cards[j]=a+b;
    			cards[i]=cards[n-1];
    			dfs(cards,n-1);
    			//n数字，其中两个数字相处理后会导致j位置的数字被更新而i位置的数字无效，
				//此时将最后一个数调到i位置，这样有效数字正好变成了前n-1个数字
    			
    			//a*b=b*a，乘法具有交换律
    			cards[j]=a*b;
    			cards[i]=cards[n-1];
    			dfs(cards,n-1);
    			
    			//减法不具有交换律
    			cards[j]=a-b;
    			cards[i]=cards[n-1];
    			dfs(cards,n-1);
    			
    			cards[j]=b-a;
    			cards[i]=cards[n-1];
    			dfs(cards,n-1);
    			
    			//除法不具有交换律
    			if(b!=0 && a%b==0) {//除数不能为0，且是整除时才可以除
    				cards[j]=a/b;
        			cards[i]=cards[n-1];
        			dfs(cards,n-1);
    			}
    			if(a!=0 && b%a==0) {
    				cards[j]=b/a;
        			cards[i]=cards[n-1];
        			dfs(cards,n-1);
    			}
    			//这两个数处理得不合适，恢复这两个数的原始状态
    			cards[i]=a;
    			cards[j]=b;
    		}
    	}
    	
    }
}

五、试题算法训练序列

分析：

对1~n的数字进行全排列，然后遍历每一种排列，找出逆序对的对数
这1~n的数字不需要用数组或链表来存储，直接在遍历0~n-1时，用下标 i +1即得到

1、用递归进行全排列

2、从前端开始遍历，当前数字前面的数字里大于它的数字的个数，即为当前数字的逆序数个数，所有数字的逆序数相加即为当前排列的逆序数对数和


package no1_1;
import java.util.*;
 
public class Main {
	static int n;
	static int count=0;//逆序数一共有count对
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        List<Integer> tempList=new ArrayList<>();//存储每一种排列
        permute(tempList);
        System.out.println(count);
    }
    // 递归方法，用于计算1到n的所有数字的全排列
    private static void permute(List<Integer> tempList) {
        if (tempList.size() == n) {
            reverseLogarithm(tempList);//得到一种排列，统计该排列的逆序对数
        } else {
            for (int i = 0; i < n; i++) {
                if (tempList.contains(i+1)) {
                	continue; // 如果当前数字已经在排列中，则跳过
                }else {
	                tempList.add(i+1); // 将当前数字加入排列
	                permute(tempList); // 递归调用，继续生成排列
	                tempList.remove(tempList.size() - 1); // 回溯，移除最后一个数字，尝试其他数字
                }
            }
        }
    }
    //统计每种排列中的逆序数对数
    public static void reverseLogarithm(List<Integer> list) {
    	for(int i=0;i<n;i++) {
    		for(int j=0;j<i;j++) {
    			// 从前端开始遍历，当前数字前面的数字里大于它的数字的个数，即为当前数字的逆序数个数，
          	     //所有数字的逆序数相加即为当前排列的逆序数对数和
    			if(list.get(j)>list.get(i)) {
    				count++;
    			}
    		}
    	}
		count=count%1007;
    }
}

六、试题算法训练选数

分析：

使用回溯法找到所有组合


package no1_1;
import java.util.*;
 
public class Main {
    private static int count = 0; // 符合条件的方案数
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x = scanner.nextInt();
        scanner.nextLine();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        Arrays.sort(a);//数组从小到大排序
        backtrack(a, x, 0, 0);
        System.out.println(count);
    }
 
    //回溯
    private static void backtrack(int[] a, int x, int sum, int i) {
        if (sum == x) {
            count++; // 找到一种符合条件的方案
            return;
        }
 
        if (i == a.length || sum > x) {
            return; // 已经考虑完了所有的数，或者当前已选数的和已经大于目标和
        }
 
        // 不选第i个数
        backtrack(a, x, sum, i + 1);
 
        // 选第i个数
        backtrack(a, x, sum + a[i], i + 1);
    }
}

七、试题算法训练球员安排

分析：

分成两种情况处理：
一：只愿意去一个位置踢足球
二：愿意去多个位置踢足球
先安排好情况一的队员，再用回溯法处理情况二的队员，安插到剩余位置
遍历所有组合


package no1_1;
import java.util.*;
 
public class Main {
    private static int count = 0; // 符合条件的方案数
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int goalkeeper=1;//门将
        int defender=4;//后卫
        int midfield=3;//中场
        int tackle=3;//前锋
        List<String> list=new ArrayList<>();
        for(int i=0;i<11;i++) {
        	String string=scanner.nextLine();
        	list.add(string);
        }
 
        backtrack(list, goalkeeper, defender, midfield, tackle, 0);
        System.out.println(count);
    }
    //回溯法
    private static void backtrack(List<String> list, int goalkeeper, int defender, int midfield, int tackle, int playerIndex) {
        if(playerIndex == list.size()) {//通过一种方案
            if(goalkeeper == 0 && defender == 0 && midfield == 0 && tackle == 0) {
                count++;
            }
            return;
        }
 
        String player = list.get(playerIndex);
        if(player.equals("1000") && goalkeeper > 0) {//只愿意去一个位置
        	
            backtrack(list, goalkeeper - 1, defender, midfield, tackle, playerIndex + 1);
            
        } else if(player.equals("0100") && defender > 0) {
        	
            backtrack(list, goalkeeper, defender - 1, midfield, tackle, playerIndex + 1);
            
        } else if(player.equals("0010") && midfield > 0) {
        	
            backtrack(list, goalkeeper, defender, midfield - 1, tackle, playerIndex + 1);
            
        } else if(player.equals("0001") && tackle > 0) {
        	
            backtrack(list, goalkeeper, defender, midfield, tackle - 1, playerIndex + 1);
            
        } else { // 多个位置都愿意
        	
            for (int i = 0; i < 4; i++) {
                if (player.charAt(i) == '1') {
                    if (i == 0 && goalkeeper > 0) {
                    	
                        backtrack(list, goalkeeper - 1, defender, midfield, tackle, playerIndex + 1);
                        
                    } else if (i == 1 && defender > 0) {
                    	
                        backtrack(list, goalkeeper, defender - 1, midfield, tackle, playerIndex + 1);
                        
                    } else if (i == 2 && midfield > 0) {
                    	
                        backtrack(list, goalkeeper, defender, midfield - 1, tackle, playerIndex + 1);
                        
                    } else if (i == 3 && tackle > 0) {
                    	
                        backtrack(list, goalkeeper, defender, midfield, tackle - 1, playerIndex + 1);
                        
                    }
                }
            }
        }
    }
}

八、试题算法训练 N皇后问题

问题描述

　　在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。你的任务是，对于给定的N，求出有多少种合法的放置方法。

输入格式

　　输入中有一个正整数N≤10，表示棋盘和皇后的数量

输出格式

　　为一个正整数，表示对应输入行的皇后的不同放置数量。

样例输入

5

样例输出

10

数据规模和约定

　　N≤10

分析：

逐行放
然后从下往上，回溯，再递归，遍历所有可能的放置方案


package no1_1;
import java.util.*;
 
public class Main {
    private static int count = 0;
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] queenPos = new int[N]; // queenPos[i] 表示第 i 行皇后所在的列位置
        backtrack(queenPos, 0);
        System.out.println(count);
    }
 
    private static void backtrack(int[] queenPos, int row) {
        if (row == queenPos.length) {//放完最后一行了，通过一种方案
            count++;
            return;
        }
 
        for (int col = 0; col < queenPos.length; col++) {
            if (isSafe(queenPos, row, col)) {
                queenPos[row] = col;
                backtrack(queenPos, row + 1);//下一行
            }
        }
    }
 
    private static boolean isSafe(int[] queenPos, int row, int col) {
    	
        for (int i = 0; i < row; i++) {
        	//queenPos[i] == col，在同一列
        	//queenPos[i] - col == i - row，检查当前位置是否与之前任意一行的皇后在从左上到右下的对角线上（斜率为 1）
        	//queenPos[i] - col == row - i，检查当前位置是否与之前任意一行的皇后在从左下到右上的对角线上（斜率为 -1）
            if (queenPos[i] == col || queenPos[i] - col == i - row || queenPos[i] - col == row - i) {
                return false;
            }
        }
        return true;
    }
}

九、试题算法训练盾神与困难数独

问题描述

　　有一天，盾神接触到了风靡世界的小游戏——数独！！！盾神非常感兴趣，不惜翘课用了一天的时间把数独玩得出神入化！！！于是他要过来考考你。经过“盾神与简单数独”的磨练后，你会做9*9的了。

输入格式

　　输入为9*9的矩阵，如果第i行第j列为0，则该格子未填数；否则该格子已经有数。

输出格式

　　输出为1个9*9的矩阵，表示字典序最小的方案。如无解则输出NO。
　　矩阵大小关系的定义：第一关键字为a[1][1]，第二关键字为a[1][2]，……第四关键字为a[1][4]，第五关键字为a[2][1]，以此类推。矩阵A小于矩阵B，当且仅当存在k，A和B的前k-1个关键字的值都相等，而A的第k个关键字的值小于B的第k个关键字的值。矩阵A等于矩阵B，当且仅当A小于B和B小于A都不成立。
　　字典序升序的定义：在矩阵序列a中，对于任意的i<=j，有a[i]<=a[j]。

样例输入

1 2 3 4 5 6 7 8 9
2 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0

样例输出

NO

样例输入

1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

样例输出

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

数据规模和约定

　　矩阵中所有数的值为0到9。

分析：

字典序（Lexicographical Order）是一种对字符串或其他数据进行排序的方法。在字典序中，字符串或数据按照字母顺序或数字大小顺序进行排列，类似于字典中单词的排列顺序。
9*9数独玩法：
每一行、每一列、每一宫（3*3空格）内的数字均包含1~9这九个数字。由于每一行、每一列或每个宫仅有9个空格，所以，每一行、每一列或每个宫不会出现重复数字。
思路：
从上到下，从左到右遍历数组，如果当前位置为空，就遍历1~9的数字，如果目标数字在该行、该列、该宫是唯一的，就可以填入。
下面的代码有一例运行超时，只拿了80分


package no1_1;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        int[][] sudoku = new int[9][9]; // 存储数独矩阵
 
        // 读入数独矩阵
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = scanner.nextInt();
            }
            scanner.nextLine();
        }
 
        if (solve(sudoku, 0, 0)) {
            // 输出解决后的数独矩阵
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudoku[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("NO");
        }
    }
 
    // 递归求解数独
    private static boolean solve(int[][] sudoku, int row, int col) {
        if (row == 9) {
            return true; // 所有行都已填完，返回true
        }
 
        if (col == 9) {
            return solve(sudoku, row + 1, 0); // 当前行已填完，转到下一行
        }
 
        if (sudoku[row][col] != 0) {
            return solve(sudoku, row, col + 1); // 当前位置已有数字，继续下一个位置
        }
 
        for (int num = 1; num <= 9; num++) {//查看sudoku[row][col]可以填入1~9中哪个数
            if (isValid(sudoku, row, col, num)) {
                sudoku[row][col] = num; // 尝试填入数字num
 
                if (solve(sudoku, row, col + 1)) {
                    return true; // 成功找到解
                }
 
                sudoku[row][col] = 0; // 回溯
            }
        }
 
        return false; // 无解
    }
 
    // 检查填入的数字是否合法，在该行，该列，该宫不能重复出现 
    private static boolean isValid(int[][] sudoku, int row, int col, int num) {
        // 检查row行和col列
        for (int i = 0; i < 9; i++) {
            if (sudoku[row][i] == num || sudoku[i][col] == num) {
                return false;
            }
        }
        // 检查小九宫格3*3
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (sudoku[i][j] == num) {
                    return false;
                }
            }
        }
        return true; // 合法
    }
}

十、1004: 母牛的故事

题目描述
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
输入格式
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。
输出格式
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

样例输入
2
4
5
0
样例输出
2
4
6

分析：

用四个变量记录生长到第一年、第二年、第三年、第四年的母牛数量
然后使用递归方法，监测每过一年，这四个变量数值的变化
最后把第 n 年的四个变量的值相加即为最终答案


package no1_1;
 
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextLine()) {
        	int n=scanner.nextInt();
        	if(n==0) {
        		break;
        	}
    		int sum=factorial(n,0,0,0,1);
        	System.out.println(sum);
        }
    }
    public static int factorial(int n,int firstYear,int secondYear,int thirdYear,int fourthYear) {
    	if(n==1) {
    		return firstYear+secondYear+thirdYear+fourthYear;//第n年，所有阶段的小牛数量相加即为答案
    	}
    	n--;//过去一年了
    	fourthYear+=thirdYear;//第三年的小牛到了生育的年龄了
    	thirdYear=secondYear;//第二年的小牛升到第三年了
    	secondYear=firstYear;//第一年的小牛长到第二年了
    	firstYear=fourthYear;//刚出生的小牛等于能生育的母牛数量
    	return factorial(n,firstYear,secondYear,thirdYear,fourthYear);
    }
}

十一、1104: Jam的计数法

题目描述
Jam是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数，而是使用小写英文字母计数，他觉得这样做，会使世界更加丰富多彩。在他的计数法中，每个数字的位数都是相同的（使用相同个数的字母），英文字母按原先的顺序，排在前面的字母小于排在它后面的字母。我们把这样的“数字”称为Jam数字。在Jam数字中，每个字母互不相同，而且从左到右是严格递增的。每次，Jam还指定使用字母的范围，例如，从2到10，表示只能使用{b,c,d,e,f,g,h,i,j}这些字母。如果再规定位数为5，那么，紧接在Jam数字“bdfij”之后的数字应该是“bdghi”。（如果我们用U、V依次表示Jam数字“bdfij”与“bdghi”，则U<V< span>，且不存在Jam数字P，使U<P<V< span>）。你的任务是：对于从文件读入的一个Jam数字，按顺序输出紧接在后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。

输入格式
输入有2行，第1行为3个正整数，用一个空格隔开：s t w

（其中s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，这3个数满足：1≤s<T< span>≤26, 2≤w≤t-s ）

第2行为具有w个小写字母的字符串，为一个符合要求的Jam数字。

所给的数据都是正确的，不必验证。

输出格式
输出最多为5行，为紧接在输入的Jam数字后面的5个Jam数字，如果后面没有那么多Jam数字，那么有几个就输出几个。每行只输出一个Jam数字，是由w个小写字母组成的字符串，不要有多余的空格。

样例输入
2 10 5
bdfij
样例输出
bdghi
bdghj
bdgij
bdhij
befgh


package no1_1;
import java.util.Scanner;
 
public class Main {
    static int s, t, w, cnt;//s为所使用的最小的字母的序号，t为所使用的最大的字母的序号。w为数字的位数，cnt为组成的字符串数量
    static char[] p = new char[30]; //存储单词
    static boolean[] vis = new boolean[30]; //标记字母是否已使用
    static final String M = " abcdefghijklmnopqrstuvwxyz"; //字母表
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        s = scanner.nextInt();
        t = scanner.nextInt();
        w = scanner.nextInt();
        String input = scanner.next();
        for (int i = 0; i < input.length(); i++) {
            p[s + i] = input.charAt(i);
        }
        dfs(s);
    }
 
    public static void dfs(int x) {
        if (x == w + s) {//x表示当前位置
            if (cnt > 0) {
                System.out.println(new String(p, s, w));
            }
            //输出数量达到5个，结束程序
            if (++cnt == 6) {
                System.exit(0);
            }
            return;
        }
        for (int i = s; i <= t; ++i) { //遍历字母表
            if (cnt == 0) { //找到题目给出的单词的第一个字母，从它的下一个字母开始搜索组合，可以直接跳过比已知字母小的字母，加快搜索速度
                i = p[x] - 'a' + 1;//p[x]为题目字符串的第一个字母
            }
            //该字母未使用，且比前面的字母大，且不超过字符串长度范围
            if (!vis[i] && M.charAt(i) > p[x - 1] && i <= t - w + 1 + x - s) {
                vis[i] = true;
                p[x] = M.charAt(i); //将该字母加入字符串中
                dfs(x + 1); //向下一层搜索
                vis[i] = false; //回溯，将该字母标记为未使用
            }
        }
    }
 
}

十二、排列

题目描述
有4个互不相同的数字，输出由其中三个不重复数字组成的排列。

输入格式
4个整数。

输出格式
所有排列
样例输入
1 2 3 4
样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 2 4
1 4 2
2 1 4
2 4 1
4 1 2
4 2 1
1 3 4
1 4 3
3 1 4
3 4 1
4 1 3
4 3 1
2 3 4
2 4 3
3 2 4
3 4 2
4 2 3
4 3 2

分析：

下列代码通过了测试用例，但不知为何提交后无法通过，提示答案错误，检查了好久也没找到问题。


import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] arr = new int[4];// 存放输入的4个数字
        for (int i = 0; i < 4; i++) {
            arr[i] = scanner.nextInt();
        }
        for(int i=3;i>=0;i--) {
        	int k=0;
            int[] nums = new int[3];
        	for(int j=0;j<4;j++) {
        		if(j!=i) {//去掉1个数字，只取3个数字生成排列
            		nums[k++]=arr[j];
        		}
        	}
            permute(nums, 0, 2);
        }
    }
 
    // 递归函数生成排列组合
    private static void permute(int[] nums, int start, int end) {
        if (start == end) {
            // 输出排列结果
            for (int i = 0; i <= end; i++) {
                System.out.print(nums[i] + " ");
            }
            System.out.println();
        } else {
            for (int i = start; i <= end; i++) {
                swap(nums, start, i); // 交换元素
                permute(nums, start + 1, end); // 递归生成下一个位置的排列
                swap(nums, start, i); // 恢复原来的顺序，进行回溯
            }
        }
    }
 
    // 交换数组中两个位置的元素
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

十三、1163: 排队买票

题目描述
有M个小孩到公园玩，门票是1元。其中N个小孩带的钱为1元，K个小孩带的钱为2元。售票员没有零钱，问这些小孩共有多少种排队方法，使得售票员总能找得开零钱。注意：两个拿一元零钱的小孩，他们的位置互换，也算是一种新的排法。（M<=10）

输入格式
输入一行，M,N,K(其中M=N+K,M<=10).

输出格式
输出一行，总的排队方案。

样例输入
4 2 2
样例输出
8

分析：

分成两部分处理：
1、对带不同钱数的小孩进行排序（此时带相同钱数的小孩看成无差异个体）
2、对带相同钱数的小孩进行内部排序，组合数学里，n个元素的排列数为n!


import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int a=sc.nextInt();
    int b=sc.nextInt();
        System.out.println(dfs(a,b)*internalArrangement(a)*internalArrangement(b));//所有可行情况
    }
    public static int dfs(int a,int b) {//带不同钱数的小孩的相对位置排列
        if(b>a) return 0;//带1元的小孩排完了，零钱不够找
        if(b==0)  return 1;//带1元的小孩多于或等于带2元的小孩，零钱够找
        return dfs(a-1,b)+dfs(a,b-1);
    }
    public static int internalArrangement(int x) {//带相同钱数的小孩的内部排列数
        //组合数学里，n个元素的排列数为n!，（阶乘）
        int sum=1;
        for (int i = 1; i <=x; i++) {
            sum*=i;
        }
        return sum;
    }
}
//上为网友答案

十四、1168: 简单计算（使用递归会栈溢出）

题目描述
有一个n+2个元素a[0], a[1], ..., a[n+1] (n <= 3000, -1000 <= a[i] <=1000)构成的数列.
已知对i=1, 2, ..., n有a[i] = (a[i-1] + a[i+1])/2 - c[i].

给定a0, a[n+1], c[1], ... , c[n]. 写一个程序计算a[1].

输入格式
第一行是整数n. 接下来两行是a[0]和a[n+1], 其小数点后有两位数字. 其后的n行为c[i](同样是两位小数), 每行一个数.

输出格式
输出为a[1], 格式与a[0], a[n+1]相同.

样例输入
1
50.50
25.50
10.15
样例输出
27.85

分析：

第一步：a[i]=(a[i-1]+a[i+1])/2-c[i]

   2 * a[1] = a[0] + a[2] - 2 * c[1]
2 * a[2] = a[1] + a[3] - 2 * c[2]
        .......
2 * a[n-1] = a[n-2] + a[n] - 2 * c[n-1]
2 * a[n] = a[n-1] + a[n+1] - 2 * c[n]
左边所有项相加等于右边所有项相加, 消除后即可得到：
a[1] + a[n] = a[0] + a[n+1] - 2*sum(c{1..n})，再想办法消去a[1]

第二步：a[1] + a[n] = a[0] + a[n+1] - 2*sum(c{1..n})

a[n] = a[0] + a[n+1] - 2*sum(c{1..n}) - a[1]
a[n-1] = a[0] + a[n] - 2*sum(c{1..n-1}) - a[1]
        .......
a[2] = a[0] + a[3] - 2*sum(c{1..2}) - a[1]
a[1] = a[0] + a[2] - 2*sum(c{1..1}) - a[1]
左边所有项相加等于右边所有项相加, 消除后即可得到最后的解：

a[1] = (n * a[0] + a[n+1] - 2*(sum(c{1..1}) + sum(c{1..2}) + .... + sum(c{1..n})))/(n+1)


import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double a0 = sc.nextDouble(), an1 = sc.nextDouble();
        double[] c = new double[n+1];
        for(int i = 1; i <= n; i++)
            c[i] = sc.nextDouble();
         
        double sum = 0;//sum(c{1..1}) + sum(c{1..2}) + .... + sum(c{1..n})
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                sum += c[j];
            }
        }
        //a[1] = (n * a[0] + a[n+1] - 2*(sum(c{1..1}) + sum(c{1..2}) + .... + sum(c{1..n})))/(n+1)
        System.out.printf("%.2f\n", (n*a0 + an1 - 2*sum) / (n+1));
    }
     
}

十五、1218: 排列

题目描述
Ray又对数字的列产生了兴趣: 现有四张卡片，用这四张卡片能排列出很多不同的4位数，要求按从小到大的顺序输出这些4位数。

输入格式
第一行是一个整数N，表示数据的组数。每组数据占一行，代表四张卡片上的数字（保证四个数字都不同，且0<数字<10）。

输出格式
对每组卡片按从小到大的顺序输出所有能由这四张卡片组成的4位数，千位数字相同的在同一行，同一行中每个四位数间用空格分隔，每组输出数据间空一行，最后一组数据后面没有空行。

样例输入
2
1 2 3 4
1 2 3 5
样例输出
1234 1243 1324 1342 1423 1432
2134 2143 2314 2341 2413 2431
3124 3142 3214 3241 3412 3421
4123 4132 4213 4231 4312 4321

1235 1253 1325 1352 1523 1532
2135 2153 2315 2351 2513 2531
3125 3152 3215 3251 3512 3521
5123 5132 5213 5231 5312 5321

分析：

代码是仿着上面的第六题写的


import java.util.Scanner;
 
public class Main {
	static int[] arr=new int[4];
	static int count=0;//一行输出6个
	public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n=scanner.nextInt();
        while(n-->0) {
        	int[] usedArray=new int[4];
        	arr[0]=scanner.nextInt();
        	arr[1]=scanner.nextInt();
        	arr[2]=scanner.nextInt();
        	arr[3]=scanner.nextInt();
        	dfs(0,usedArray,0);
        	System.out.println();
        }
    }
	public static void dfs(int num,int[] usedArray,int step) {
		if(step==4) {//递归终止条件：生成一个完整的排列
			System.out.print(num+" ");
			count++;
			if(count==6) {//6个一行
				System.out.println();//换行
				count=0;//重置计数器
			}
		}
		for(int i=0;i<4;i++) {
			if(usedArray[i]==0) {//该数字未被使用过，可以用
				num=num*10+arr[i];//比如12，变成了120+3=123
				usedArray[i]=1;//标记用过的数字
				dfs(num,usedArray,step+1);//递归
				num/=10;//回溯
				usedArray[i]=0;//取消标记
			}
		}
	}
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/478062

算法——深度优先搜索（DFS）/ 递归 / 回溯_dfs递归调用

DFS

递归

迭代和递归的区别

回溯

一、计算阶乘

二、试题 算法训练 数字游戏

三、试题 算法训练 粘木棍

四、试题 算法训练 24点

五、试题 算法训练 序列

六、试题 算法训练 选数

七、试题 算法训练 球员安排

八、试题 算法训练 N皇后问题

九、试题 算法训练 盾神与困难数独

十、1004: 母牛的故事

十一、1104: Jam的计数法

十二、排列

十三、1163: 排队买票

十四、1168: 简单计算（使用递归会栈溢出）

十五、1218: 排列

二、试题算法训练数字游戏

三、试题算法训练粘木棍

四、试题算法训练 24点

五、试题算法训练序列

六、试题算法训练选数

七、试题算法训练球员安排

八、试题算法训练 N皇后问题

九、试题算法训练盾神与困难数独