怎样免费推广网站,小程序制作侧拉切换,wordpress网站安全性,定制网站建设服务递归 例题 递归实现指数型枚举 从 1∼n这 n个整数中随机选取任意多个#xff0c;输出所有可能的选择方案。 输入格式 输入一个整数 n。 输出格式 每行输出一种方案。 同一行内的数必须升序排列#xff0c;相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案#xff0c… 递归 例题 递归实现指数型枚举 从 1∼n这 n个整数中随机选取任意多个输出所有可能的选择方案。 输入格式 输入一个整数 n。 输出格式 每行输出一种方案。 同一行内的数必须升序排列相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案输出空行。 各行不同方案之间的顺序任意。 数据范围 1≤n≤15 输入样例 3输出样例
3
2
2 3
1
1 3
1 2
1 2 3 import java.util.*;
public class Main{static int N16;static int n;static int []stnew int[N]; //表状态0表示未考虑1表示选2表示不选static void df(int u){if(un){ //递归出口输出选择的数for(int i1;in;i){if(st[i]1)System.out.print(i );}System.out.println();return ;}//也可不恢复现场st[u] 2; //未选择递归第一个选的分支df(u1);st[u] 0; //恢复现场st[u]1;//第二个分支选了df(u1);st[u]0;//恢复现场}public static void main(String[] args){Scanner scan new Scanner(System.in);nscan.nextInt(); df(1);scan.close();}
} 递归实现排列型枚举 把 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 import java.util.*;
public class Main{static int N10;static int[] stnew int[N]; //存放第u个位置放什么数static boolean[] usenew boolean[N];//表示是否选用了istatic int n;public static void dfs(int u){if(un){ //递归出口,表示u个位置都已存放数for(int i1;in;i){System.out.print(st[i] );}System.out.println();return ;}//枚举每个分支for(int i1;in;i){if(!use[i]){ //如果数i没有用过st[u]i; //第u个位置放iuse[i]true;dfs(u1);//恢复现场st[u]0; //第u个位置未选用iuse[i] false;}} }public static void main(String[] args){Scanner scannew Scanner(System.in);nscan.nextInt();dfs(1);scan.close();}
}
时间复杂度n*(1nn(n-1)......n!)n*3n!
