合肥市蜀山区做个网站多少钱,欧美系列,苏州建站免费模板,网页qq空间题目
把 1∼ n n n 这 n n n 个整数排成一行后随机打乱顺序#xff0c;输出所有可能的次序。
输入格式
一个整数 n n n。
输出格式
按照从小到大的顺序输出所有方案#xff0c;每行 1 个。
首先#xff0c;同一行相邻两个数用一个空格隔开。
其次#xff0c;对于两…题目
把 1∼ n n n 这 n n n 个整数排成一行后随机打乱顺序输出所有可能的次序。
输入格式
一个整数 n n n。
输出格式
按照从小到大的顺序输出所有方案每行 1 个。
首先同一行相邻两个数用一个空格隔开。
其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面。
数据范围 1 ≤ n ≤ 9 1≤n≤9 1≤n≤9
输入样例
3输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1思路
该问题也被称为全排列问题所有可能的方案总数是 n ! n! n! 种。在这里递归需要求解的问题是 “把指定的 n n n 个整数按照任意次序排列”在每次递归中尝试把每个可用的数作为数列中的下一个数求解 “把剩余 n − 1 n-1 n−1 个整数按照任意次序排列” 这个规模更小的子问题。
代码
#include cstdio
using namespace std;int order[15]; //按顺序依次记录被选择的整数
bool chosen[15]; //标记被选择的整数
int n;void dfs(int cur) {if (cur n 1) { //问题边界for (int i 1; i n; i) {printf(%d , order[i]);}puts();return ;}for (int i 1; i n; i) {if (chosen[i]) continue;order[cur] i;chosen[i] true; //标记i被选择了dfs(cur 1);chosen[i] false; //回溯到上一个问题前恢复现场order[cur] 0; //本行可以省略因为每次都会被重新赋值}
}int main() {scanf(%d, n);dfs(1);return 0;
}
