首页 > 其他分享 >【递归】 递归实现排列型枚举

【递归】 递归实现排列型枚举

时间:2024-05-26 20:59:47浏览次数:28  
标签:10 arr 排列 递归 int 枚举 本题

题目描述

​ 从 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

数据规模与约定

​ 时间限制:1 s

​ 内存限制:256 M

​ 100% 的数据保证 1≤n≤8


解题分析

本题与前两篇相比,递归函数类似,但是可见在本题中,同一方案中前面的数是可以大于后面的数的(譬如“1 3 2”)。为实现这一点,我们会希望能够通过某种方法得知现在将要枚举的数是否已经被枚举过了。这是解决本题的关键所在。

【递归】递归实现指数型枚举-CSDN博客

【递归】递归实现组合型枚举-CSDN博客

第一步、照常定义输出函数,输出每一个解决方案

void print_arr(int n) {
	for (int i = 0; i < n; i++) {
		if (i)cout << " ";
		cout << arr[i];
	}
	cout << endl;
	return;
}

第二步、设置数组标记该数字是否被使用过

这一步该如何实现?由题知本题n<=8,我们不妨定义数组vis[10],当数字k未被枚举时,vis[k]=0;当枚举数字k时,同时标记vis[k]=1,从而满足本题要求。

int vis[10]={0};

第三步、设计递归函数

在学会指数型枚举和组合型枚举后,这一步将变得十分熟悉。

首先定义数组arr[10]来存放一个解决方案中的n个数字;

设计f(i,n),其中i表示现在枚举到arr数组的第i位,f(i,n)表示第i位置到第n位置的枚举方案集合。

f(i,n)=\left\{\begin{matrix} & &v[1]+f(i+1,n) \\ & & v[2]+f(i+1,n)\\ &&v[3]+f(i+1,n)\\ &&... \end{matrix}\right.

其中,v[1]代指第1个未被枚举过的数,v[2]代指第2个未被枚举过的数...以此类推

显然边界条件为:当i==n时,输出该方案。

那么我们不难写出该递归函数:

void f(int i,int n) {
	if (i == n) {
		print_arr(n);
		return;
	}
	for (int k = 1; k <= n; k++) {
		if (vis[k])continue;//判断k是否被枚举过
		arr[i] = k;
		vis[k] = 1;
		f(i + 1, n);
		vis[k] = 0;//此时已经输出完所有第i位置等于k的结果,我们可以设置vis[k]=0使k可以在后面的枚举继续被使用
		
	}
	return;
}

补全程序,获得完整代码如下:

#include <iostream>
using namespace std;

int arr[10], vis[10] = {0};
void print_arr(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_arr(n);
		return;
	}
	for (int k = 1; k <= n; k++) {
		if (vis[k])continue;//判断k是否被枚举过
		arr[i] = k;
		vis[k] = 1;
		f(i + 1, n);
		vis[k] = 0;//此时已经输出完所有第i位置等于k的结果,我们可以设置vis[k]=0使k可以在后面的枚举继续被使用
		
	}
	return;
}
int main()
{
	int n;
	cin >> n;
	f(0, n);
	return 0;
}

标签:10,arr,排列,递归,int,枚举,本题
From: https://blog.csdn.net/weixin_74873063/article/details/139120009

相关文章

  • 字符串的排列
    描述输入一个长度为n字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。示例1输入:"ab"返回值:["ab","ba"]说明:返回["ba","ab"]也是正确的......
  • 复习递归------拆开了输出整数
    问题1:题目概述    这次带来的例题是一道简单题,题目概述如下:     题目要求输入一个整数n,然后从高位到低位输出每位的数字,假设我输入123,则输出必须为123。就是那么简单(数字之间用空格分开)。问题2:思路     我们之前说过递归二要素是停止条件和规......
  • 每日一练——两数之和(暴力枚举)
     1.两数之和-力扣(LeetCode)/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){//i遍历下标for(inti=0;i<numsSize;++i){//j遍历i之后......
  • 自定义类型:联合和枚举
    目录1.联合体1.1联合体类型的声明1.2联合体的特点1.3相同成员的结构体和联合体对比1.4联合体大小的计算1.5联合的⼀个练习2.枚举类型2.1枚举类型的声明2.2枚举类型的优点2.3枚举类型的使用1.联合体1.1联合体类型的声明像结构体⼀样,联合体也是由⼀个或......
  • MyBatis Plus 实现枚举类型转化 步骤
    1.在yaml文件中添加枚举处理器 2.编辑枚举项这里的@JsonValue对privatefinalStringdesc;注解,前端返回的值就是”正常“或”冻结“  3.将这里实体类的类型按照需要改为枚举类型 4.这时就可以将你的代码替换成枚举值了......
  • MySQL8.0新特性CTE表达式递归实现累加运算 1+2+…+n 等于多少?
    上一篇内容,通过MySQL存储过程实现累加运算1+2+…+n等于多少的需求,使用当前主流版本MySQL5.7.x和MySQL8.0.x,以及最新的MySQL8.4LST版本。WITHAS子句在MySQL8.0.x及更高版本中得到支持,而在MySQL5.7及以下版本中则不支持。参考地址如下:https://blog.csdn.net/zxrhhm/......
  • 头歌05-排列树实验-批处理作业调度
    """题目:给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理,然后由机器2处理。所有任务必须先由机器1处理完成后,才能由机器2处理,并且在机器2的处理顺序必须与机器1的处理顺序一致,处理顺序一旦确定不能改变。设作业Ji需要机器1的处理时间为Ai,需要机器2的处理时间为Bi......
  • 【c语言】一篇文章搞懂函数递归
    ......
  • 打印9*9乘法表(递归或压缩矩阵)python
    打印9*9表defprint_multiplication_table(row,col):ifrow>10:return#递归结束条件ifcol==row:print()#换行print_multiplication_table(row+1,1)#递归调用下一行else:print(f"{row-1}*{col}={(......
  • 【Algorithm算法章】递归&&搜索&&回溯&&算法思路总结概括
    文章目录......