电商网站创办过程,php与mysql网站开发全接触,没有网站seo怎么做,网站的视频怎么下载本篇博客将聚焦于通过递归来实现两种经典的枚举方法#xff1a;指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用#xff0c;无论是在解题中#xff0c;还是在实际工作中都极具价值。 目录
前言
斐波那契数列递归
递归实现指数型枚举
算法思… 本篇博客将聚焦于通过递归来实现两种经典的枚举方法指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用无论是在解题中还是在实际工作中都极具价值。 目录
前言
斐波那契数列递归
递归实现指数型枚举
算法思路
代码如下
递归实现排列型枚举
算法思路 代码如下 总结 前言
在编程的世界里递归是一种优雅且强大的技术它能让复杂问题变得更加简洁和易于理解。无论是数学中的公式推导还是计算机科学中的算法设计递归都扮演着不可或缺的角色。在数据结构与算法中递归不仅能帮助我们高效地解决问题还能展现出代码的简洁性和表达力。
本篇博客将聚焦于通过递归来实现两种经典的枚举方法指数型枚举和排列型枚举。这两种枚举方式在计算机科学和算法竞赛中都有广泛应用无论是在解题中还是在实际工作中都极具价值。 斐波那契数列递归 递归最经典的就是斐波那契数列其中第1个数是1第2个数是2第3个数是前两个数字之和。 java代码如下
package AcWingLanQiao;import java.util.*;public class 递归 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();System.out.println(f(n));}public static int f(int n){if(n1){ return 1;}if(n2){ return 2;}return f(n-1)f(n-2);}
}递归实现指数型枚举
从 1∼n 这 n 个整数中随机选取任意多个输出所有可能的选择方案。
输入格式
输入一个整数 n。
输出格式
每行输出一种方案。
同一行内的数必须升序排列相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案输出空行。
数据范围
1≤n≤15
输入样例
3
输出样例 3
2
2 3
1
1 3
1 2
1 2 3
算法思路 每一个位置都有两种情况分别是选和不选。
当有n个数时结果就有中情况。 当n为对的时候上述对应的是递归搜索树。从第一个位置开始分两种情况选和不选后续每个位置一次类推。
我们用一个数组flag数组下标表示从1到nflag[i]表示该值在每个位置的状态0表示还未考虑1表示选2表示这个位置不选通过dfs深度优先搜索用u来表示当前在哪个位置先思考递归的出口当当前位置u要大于n时即u n就说明n个位置每个位置的情况都处理好了就说明最后flag[i] 1对应的下标就是结果所需的序列。
当u n时我们只需处理两种情况一种是选一种是不选。当选时将flag[u] 1然后递归的处理下一个位置dfs(u1)最后再恢复现场flag[u] 0即相当于是当前的位置都处理完了将位置恢复为未处理然后再走另一种情况当不选时将flag[u] 2,后递归的处理下一个位置dfs(u1)最后再恢复现场flag[u] 0。
代码如下
package AcWingLanQiao;
import java.io.*;
import java.util.*;public class 递归实现指数型枚举 {static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st new StreamTokenizer(br);static int N 16;/*状态数据记录每个位置的当前状态0表示还未考虑1表示选它2表示不选它*/static int[] flag new int[N];static int n;public static void main(String[] args)throws Exception {n nextInt();dfs(1);pw.flush();}public static void dfs(int u){if(u n){for(int i 1;i n;i){if(flag[i] 1){pw.print(i );}}pw.println();pw.flush();return;}flag[u] 2;dfs(u1); //第一个分支不选flag[u] 0;//恢复现场flag[u] 1;dfs(u1); //第二个分支选flag[u] 0;}public static int nextInt() throws Exception {st.nextToken();return (int)st.nval;}
}递归实现排列型枚举
把 1∼n 这 n 个整数排成一行后随机打乱顺序输出所有可能的次序。
输入格式
一个整数 n。
输出格式
按照从小到大的顺序输出所有方案每行 1 个。
首先同一行相邻两个数用一个空格隔开。
其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面。
数据范围
1≤n≤9
输入样例
3
输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 注字典序排序是一种按照字典中单词出现的顺序来排列元素的方法。在计算机科学中它被用来比较两个字符串的大小关系即比较它们从左到右第一个不同字符的ASCII值的大小关系。这种排序方式不仅适用于英文单词也适用于任意字符串的比较。 算法思路 用整型数组arr来存储数列的结果布尔类型数组flag其中flag[i]若为true表示数字i已被使用若为false表示数字i未被使用。使用深度优先搜索dfs来解决此问题。我们可以通过每个位置放置哪个数字来进行思考。
我们先来思考递归的出口当当前位置u大于n时即u n说明所有的位置上数字都以排好所以此时只需打印arr数组就可以得到结果。当n为3时说明一个位置有3种情况所以要有一个外层循环然后来判断flag[i]是否被使用未被使用则将当前位置复制为i即arr[u] i还需将该数字对应的flage数组设置为已使用即flag[i] true然后递归的处理下一个位置即dfs(u1)最后再进行回溯操作flag[i] false。如果flag[i]已经被使用则接着进行下一次数字进行判断n个数字都被使用也可说明数列已被排完序。
算法时间复杂度为On*n! 代码如下
import java.io.*;public class Main {static PrintWriter pw new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st new StreamTokenizer(br);static int N 10;static int[] arr new int[N];static boolean[] flag new boolean[N]; //true表示用过 false表示未被用过static int n;public static void main(String[] args) throws IOException {n nextInt();dfs(1);pw.flush();}public static void dfs(int u) {if(u n){ //边界for(int i 1; i n;i){pw.print(arr[i] );}pw.println();return;}//枚举每个分支for(int i 1; i n;i){if(!flag[i]){arr[u] i;flag[i] true;dfs(u1);//恢复现场flag[i] false;}}}public static int nextInt() throws IOException {st.nextToken();return (int) st.nval;}
}代码输入
4
代码输出结果
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1 总结
通过本篇博客的学习我们可以看到递归作为一种经典的编程技巧不仅能够简化问题的解决过程还能提高代码的可读性和执行效率。递归在指数型枚举和排列型枚举中的应用展示了它在不同场景中的灵活性与强大功能。
无论是初学者还是有一定编程经验的开发者理解并掌握递归的精髓对于解决实际问题都有很大的帮助。希望通过这篇博客能够带给大家一些启发并鼓励大家在实际编程过程中善于运用递归解锁更多的编程奥秘。
