递归
1、斐波那契额数列
基础代码
#include <iostream>
using namespace std;
int f(int n)
{
if (n == 1) return 1;
if (n == 2) return 2;
return f(n - 1) + f(n - 2);
}
int main()
{
int n;
cin >> n;
cout << f(n) << endl;
return 0;
}
递归实现指数型枚举（递归）
题目描述
从 1~n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。
输入格式
输入一个整数n。
输出格式
每行输出一种方案。同一行内的数必须升序排列，相邻两个数用恰好1个空格隔开。对于没有选任何数的方案，输出空行。
本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。
数据范围
1 ≤ n ≤ 15
输入样例
3
输出样例
3
2
2 3
1
1 3
1 2
1 2 3
基础代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20;
int n;
int st[N];// 0 表示还未考虑 1表示已经选择 2表示不选择
void dfs(int u) // u是指到那个位置了
{
if (u == n) // 超过最后一个数字了
{
//输出
for (int i = 0; i < n; i++)
if (st[i] == 1) cout << i + 1<< ' ' ;
puts("");
return;
}
st[u] = 2;
dfs(u + 1);
st[u] = 0;
st[u] = 1;
dfs(u + 1);
st[u] = 0;//恢复现场
}
int main()
{
cin >> n;//从1 - n 个数字
dfs(0);
return 0;
}
所有的递归过程都可以画一个递归搜索树
递归实现排列型枚举(递归)
题目描述
把 1~n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。
输入格式
一个整数n。
输出格式
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。
数据范围
1 ≤ n ≤ 9
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
基础代码：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10;
int n;
int path[N];//记录路径
bool st[N];// 0表示没有放置数字 1表示放置了数字
void dfs(int u) //比较到第几个位置
{
if (u == n)//比较到最后一个位置的时候
{
for (int i = 0; i < n; i++)
cout << path[i] << ' ';//输出结果
puts("");
return;
}
//比较的过程
for (int i = 0; i < n; i++) // 比较的数字
{
if (st[i] == 0)//如果当前数字没有被使用
{
st[i] = 1;
path[u] = i + 1;
dfs(u + 1);
st[i] = 0;
}
}
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
递归实现组合型枚举
从 1∼n1∼n 这 nn 个整数中随机选出 mm 个，输出所有可能的选择方案。
输入格式
两个整数 n,mn,m ,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案，每行 11 个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。
其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。
数据范围
n>0n>0 ,
0≤m≤n0≤m≤n ,
n+(n−m)≤25n+(n−m)≤25
输入样例：
5 3
输出样例：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 30;
int n, m;
int path[N]; //记录方案的路径
int st[N];//0表示当前数字没有被使用 1表示已经被使用
void dfs(int u)
{
//当排序到最后一位的时候
if (u == m)
{
for (int i = 0; i < m; i++)
{
cout << path[i] << ' ';
}
puts("");
return;
}
//排序的过程中
for (int i = path[u - 1];i < n; i++)
{
if (st[i] == 0)
{
st[i] = 1;
path[u] = i + 1;
dfs(u + 1);
st[i] = 0;
}
}
}
int main()
{
cin >> n >> m; // 1-n 个数字 取m个数字
dfs(0);
return 0;
}