洛谷 P1706 全排列问题 ：STL / dfs
2024-08-24 06:58:25
题目描述
输出自然数1到n所有不重复的排列，即n的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
输入输出格式
输入格式：
n(1≤n≤9)
输出格式：
由1～n组成的所有不重复的数字序列，每行一个序列。每个数字保留5个常宽。
输入输出样例
输入样例#1：
3
输出样例#1：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路描述：
第一种：用stl函数库里next_permutation（升序），prev_permutation（降序），头文件：#include<algorithm>
返回值：如果有一个更高的排列，它重新排列元素，并返回true；如果这是不可能的（因为它已经在最大可能的排列），它按升序排列重新元素，并返回false。
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main() {
int a[1000], n;
cin >> n;
for (int i = 1; i <= n; i++)
a[i] = i;
do{
for (int i = 1; i <= n; i++) {
printf("%5d", a[i]);
}
cout << "\n";
} while (next_permutation(a + 1, a + n + 1));
return 0;
}
第二种：用dfs实现全排列
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int n, a[10], book[10];//a[i]代表第i个数，book标记用没用过，0就没用过
void dfs(int c) {
if (c == n + 1) {//搜索结束
for (int i = 1; i <= n; i++)
printf("%5d", a[i]);
cout << "\n";
return;
}
for (int i = 1; i <= n; i++) {
if (book[i] == 0) {//若没用过
a[c] = i;//赋值
book[i] = 1;//标记
dfs(c + 1);
book[i] = 0;//取消标记 回溯
}
}
return;
}
int main() {
cin >> n;
dfs(1);
return 0;
}
最新文章
- Unity iOS混合开发界面切换思路
- 求n!最后一位非零数
- mybatis generator使用（基于maven）
- Co-saliency-Huazhu Fu
- UVA 10066 The Twin Towers
- Step by Step：Linux C多线程编程入门(基本API及多线程的同步与互斥)
- 阿里云ECS(云服务器)之产品简介
- Java邮件服务学习之四：邮箱服务客户端Spring Mail
- Netty多线程处理机制
- Delphi文件映射
- SQL Server 添加一条数据获取自动增长列的几种方法
- shu_1186 字符排列问题
- wince平台下使用log4net记录日志
- InkImageDataSetGenerator-开源一个可用于机器学习的书写轨迹图片生成的小工具
- YARN的基础配置
- 764. Largest Plus Sign
- Python基础之模块与包
- python常见面试题（mark）
- 被included或者被required的文件都来自哪里呢
- windows从0开始学golang--0--安装golang+git+自己写包