山西太原制作网站人有吗,wordpress模板 菜谱,青岛网站建设企业建站,网站 后台 数据 下载题目描述
取1到N共N个连续的数字#xff08;1≤N≤9#xff09;#xff0c;组成每位数不重复的所有可能的N位数#xff0c;按从小到大的顺序进行编号。当输入一个编号M时#xff0c;就能打印出与该编号对应的那个N位数。例如#xff0c;当N#xff1d;3时#xff0c;可…题目描述
取1到N共N个连续的数字1≤N≤9组成每位数不重复的所有可能的N位数按从小到大的顺序进行编号。当输入一个编号M时就能打印出与该编号对应的那个N位数。例如当N3时可组成的所有三位数为 那么输入编号M2时则输出132。
输入 包括两个数即正整数N1 N 9和正整数M1 M 362880。 输出 只有一行即与输入的编号M对应的那个N位数。 样例输入 3 2 样例输出 Copy 132
分析
N 9所以可以直接将n全排列时间复杂度为O(n!)9! 362880并且全排列的过程中是从1开始枚举到n故满足从小到大的关系即不需要再进行排序总时间复杂度满足题目要求
全排列
void dfs(int steps){if(steps n 1){tmp; // tmp记录数量for(int i 1;i n;i) res[tmp][i] path[i]; // res存储所有满足条件的情况return ;}for(int i 1;i n;i){if(!st[i]){st[i] true;path[steps] i;dfs(steps 1);st[i] false;}}
}代码
#includebits/stdc.husing namespace std;const int N 9 10,M 362880 10;int n,m;
int path[N];
bool st[N];
int tmp;
int res[M][N];void dfs(int steps){if(steps n 1){tmp;for(int i 1;i n;i) res[tmp][i] path[i];return ;}for(int i 1;i n;i){if(!st[i]){st[i] true;path[steps] i;dfs(steps 1);st[i] false;}}
}int main(){ios::sync_with_stdio;cin.tie(0),cout.tie(0);cin n m;dfs(1);for(int i 1;i n;i) cout res[m][i];return 0;
}
