果洛州wap网站建设公司,国外设计素材网站,乐亭网站建设,手机单页网站教程题目描述
从 1−n这 n个整数排成一排并打乱次序#xff0c;按字典序输出所有可能的选择方案。 输入
输入一个整数 n。#xff08;1≤n≤8#xff09;
输出
每行一组方案#xff0c;每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例…
题目描述
从 1−n这 n个整数排成一排并打乱次序按字典序输出所有可能的选择方案。 输入
输入一个整数 n。1≤n≤8
输出
每行一组方案每组方案中两个数之间用空格分隔。
注意每行最后一个数后没有空格。
样例输入
3
样例输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
#include iostream // 输入输出流
#include cstdio // 标准输入输出库
#include cstdlib // 标准库函数包含通用工具函数
#include queue // 队列容器
#include stack // 栈容器
#include algorithm // 算法库包含各种算法函数
#include string // 字符串库
#include map // 映射容器
#include set // 集合容器
#include vector // 动态数组容器
using namespace std;int arr[10], vis[10] {0}; // 定义一个数组arr用于存放排列vis数组用于标记数字是否被使用过// 打印一个排列结果
void print_one_result(int n) {for (int i 0; i n; i) {if (i) cout ; // 输出空格分隔数字cout arr[i]; // 输出当前位置的数字}cout endl;return ;
}// 递归生成全排列
void f(int i, int n) {if (i n) { // 当已经填满所有位置print_one_result(n); // 打印这个排列return ;}for (int k 1; k n; k) {if (vis[k]) continue; // 如果数字k已经被使用跳过arr[i] k; // 将数字k放入当前位置vis[k] 1; // 标记数字k已被使用f(i 1, n); // 递归生成下一个位置的数字vis[k] 0; // 恢复数字k的未使用状态以便后续排列生成}return ;
}int main() {int n;cin n; // 输入n表示生成1到n的全排列f(0, n); // 调用排列生成函数return 0; // 返回0表示程序正常结束
}这段代码的目的是生成从1到n的所有全排列。全排列是指从n个不同元素中取出n个元素也就是全部元素进行排列的不同排列方式的总数。这里使用了回溯算法进行全排列的生成。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解或者至少不是最后一个回溯算法会通过在上一步进行一些变化来舍弃该解。
