C/C++递归实现全排列
2023-06-13 09:16:47 时间
前言
本文介绍如何用递归实现全排列。
全排列
参考题目:递归实现排列型枚举
两种方法,一是枚举每个位置,看每个位置能放哪些数。以A33为例,同是第一个位置,可以放1、2、3,三种元素。
二是枚举每个数,看每个数能放在哪些位置。即同是元素1,可以放在第一、第二、第三的位置上。
两种方法的思维和代码极其相似,本文展示第一种方法。
首先,我们创建一个数组arr,用来保存每个位置的数。
int arr[10] = { 0 };//保存已被固定的数
对于第一个位置arr【0】来说,有三种选择,分别是1、2、3,在每种选择的前提下,进行第二个位置的选择。
因为我们在固定第一个位置时已经用掉了一个数,所以在固定第二个位置arr【1】时,就不能再次使用这个数。
于是,我们创建一个数组used,利用哈希表的思想,保存每个数是否被用过。
int used[10] = { 0 };// 判断一个数是否被用过,用过则为1,没用过则为0
比如说,当我们arr【0】被固定为数字1,那么就让used【1】++,当我们进行第二、三个位置的固定时,先检测used【要固定的数】是否为0,是0才可以使用。
为了没有遗漏,我们要保证每一个位置都要对三个数进行遍历,一旦某个数可以用,就马上固定它,且每个位置的遍历顺序必须一致。
以上也是博主理解的为什么递归算法又叫深度优先搜索的原因。
深度,在本题中是代表遍历的顺序必须一致,要么从前往后,要么从后往前,只有这样才可以从一开始就一条路走到最深,才可以没有遗漏情况。
优先,在本题中是代表在每个位置对数据进行遍历的时候,只要这个数能用,就马上使用,以保证没有遗漏。
详细代码及注释如下:
//枚举每个位置放不同的数
int arr[10] = { 0 };//保存已被固定的数
int used[10] = { 0 };// 判断一个数是否被用过,用过则为1,没用过则为0
void f(int n,int h)
{
if (n == h)//如果三个数都被固定好了,则打印,可以先略过打印部分
{
int i = 0;
for (i = 0; i < h; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return;
}
int i = 0;
for (i = 0; i < h; i++)
{
if (used[i + 1] == 0)//此语句代表i+1这个数还没被用过
{
used[i + 1]++;//没被用过就马上使用它
arr[n] = i + 1;
f(n + 1,h);
used[i + 1]--;//在一种情况下的分支结束后,到另一种情况时,需要恢复原样
}
}
}
int main()
{
int h = 0;
scanf("%d", &h);
f(0,h);
return 0;
}
感谢您的阅读与耐心~
相关文章
- C++学习之路——名字空间与模板
- EasyC++75,继承(二)
- c++发送post请求_request的post方法作用
- 【C++学习五】STL库的应用
- 汉罗塔c++递归_栈与递归的区别
- a星算法c++实现_递归算法理解
- 清除 Cu002FC++ 中的输入缓冲区
- C++类和对象(上)
- C/C++ 实现正向CMDShell
- C/C++ 目录递归与结束递归
- C/C++ 递归遍历文件并计算MD5
- C/C++递归实现组合数
- 【C++ 语言】智能指针 引入 ( 内存泄漏 | 智能指针简介 | 简单示例 )
- C++ partial_sort(STL partial_sort)排序算法详解
- 什么是常量,C++常量及用法(无师自通)
- C++快速排序(递归)算法详解
- C++关于STL中sort()对struct排序的方法
- 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)
- 浅析c++宏#val在unicode下的使用
- C++基于对话框的程序的框架实例
- C++类基本语法实例分析