基本算法-枚举、模拟、递推（上）

目录

递归实现指数型枚举

题目描述

运行代码

代码思路

递归实现组合型枚举

题目描述

运行代码

代码思路

递归实现排列型枚举

题目描述

运行代码

代码思路

递归实现指数型枚举

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include
using namespace std;
int n,a[17],m;
void p(int n)
{
    if(!n)return;
    p(n/10);
   cout<n)
    {
        for(int j=1;j<=m;++j)
        {
            p(a[j]);
            cout<<" ";
        }
        cout<>n;
    dfs(1);
    return 0;
}

代码思路

• p函数用于将一个整数按位输出，通过递归的方式逐位取出并输出。
• dfs函数是深度优先搜索的主要函数。
• 从 1 开始进行深度优先搜索，当搜索到超过给定的 n 时，就输出当前已选择的数字序列。
• 在搜索过程中，有两种选择：一种是不选择当前数字，直接进入下一层搜索（dfs(i+1)）；另一种是选择当前数字，将其添加到数组 a 中（通过递增 m 并赋值），然后再进行下一层搜索（dfs(i+1)），之后再回溯（通过 m-- 恢复状态）。通过深度优先搜索生成并输出所有可能的数字组合情况。

递归实现组合型枚举

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include 
#include  
using namespace std;
vector a;
int n,m;
void dfs(int x)
{
	if( a.size() == m )
	{
		for (int i = 0; i < a.size(); i++)
		{
			cout << a[i];
			if( i != a.size() - 1 ) cout << ' ';
		}
		cout < m || a.size() + n - x + 1 > n >> m;
	dfs(1);
	return 0;
}

代码思路

1. 变量定义:vector a; 用于存储当前搜索路径上的数字，即当前组合。

   int n, m; 分别表示可选择的数字范围（1到n）和每个组合需要的数字个数。

2. 主函数main():读入用户输入的n和m，然后调用dfs(1)开始深度优先搜索，从数字1开始探索所有可能的组合。

3. 函数dfs(int x):

   • 基础情况：如果当前组合a的大小等于目标组合长度m，说明已经找到一个有效的组合，这时遍历并打印a中的所有数字，然后返回。
   • 剪枝：如果当前组合的大小已经超过目标长度m，或者即使把剩下的所有数字都加入当前组合也无法达到目标长度，说明此路不通，直接返回。
   • 递归搜索：先做选择：将当前数字x加入到组合a中，然后递归调用dfs(x+1)继续搜索下一个数字。撤销选择：在递归调用返回后，从组合a中移除最后一个数字（即撤销之前的选择），然后继续尝试下一个可能的数字，即再次调用dfs(x+1)。

程序能够遍历所有可能的组合，而不会重复，并且有效地跳过了不可能构成有效组合的搜索路径，这就是剪枝操作的作用，保证了算法的高效执行。

递归实现排列型枚举

题目描述

登录—专业IT笔试面试备考平台_牛客网

运行代码

#include
#include
#include
using namespace std;
int n = 0;
int arr[10];
void FN(string & s) {
    if (s.size() < 2 * n) {
        for (int i = 1; i <= n; ++i) {
            if (arr[i] == 0)
                continue;
            s += to_string(i) + " ";
            arr[i] = 0;
            FN(s);
            s.pop_back();
            s.pop_back();
            arr[i] = 1;
        }
        return;
    }
    s.pop_back();
    cout << s <> n;
    for (int i = 1; i <= n; ++i) {
        arr[i] = 1;
    }
    string s;
    FN(s);
    return 0;
}

代码思路

1. 全局变量定义:int n: 存储用户输入的整数，用于确定序列中数字的取值范围（1到n）。

   int arr[10]: 记录每个数字是否已被使用。初始化为1，表示所有数字都可以被使用。

2. 函数FN(string &s):

   • 参数：string &s 是一个引用类型字符串，用于构建当前搜索路径上的序列。
   • 基本思路：递归生成序列，当序列长度达到2*n时，输出该序列。
   • 递归条件：若s.size()小于2*n，则继续添加数字。遍历1到n之间的数字，检查当前数字是否可用（arr[i]==1）。回溯：从s中移除刚添加的数字及其尾随的空格，并恢复数字的可用状态(arr[i]=1)。递归调用FN(s)继续构建序列。若可用，则将其转换为字符串形式添加到s中，并标记该数字已使用(arr[i]=0)。
   • 输出条件：当s的长度达到2*n时，从s中移除最后一个空格，输出序列，并在序列末尾添加一个空格准备下一轮的添加（虽然这里的添加空格在最终输出时并无实际作用）。

3. 主函数main():读取用户输入的n。初始化数组arr，允许所有数字最初都被使用。调用FN(s)开始递归生成并输出所有满足条件的序列，初始传入一个空字符串s。

利用深度优先搜索遍历所有可能的序列组合，并通过数组arr跟踪每个数字的使用状态，确保序列中任意两个相邻数字不相同。