一个实际问题的各种可能情况构成的 集合 称为 “状态空间”,递推和递归 就是程序遍历 状态空间 的两种基本方式。
我们把每个状态看作一个节点,根据递推和递归的法则:
从 状态空间 的角度来看,递归和递推 实际上就是对一个 状态图/树 的遍历,并求解 问题边界 的行为
如果我们把 同类型 的 状态节点 合并,以 一个节点 代表 一类节点,从而省掉重复的搜索分枝,那个行为就是我们常用的 记忆化搜索 算法
这也是我之前在某篇博客里提到过的,动态规划 作为具有 递推性质 的算法,本质上是在一个 DAG 上找 “问题边界” 的 变换路线
递归 算法中,程序在每个变换步骤中要执行的三个操作:
上述三个操作中有亮点颇为关键,一是 “如何尝试求解规模缩小以后的问题”。由于问题规模缩小为原问题的一个子问题,因此可以把它视为一个新的“原问题”,并由相同的程序进行求解,也就形成了“自身调用自身”的递归。二是求解子问题失败后,程序需要回到当前问题并去寻找其他的变换路线,因此把当前问题缩小为子问题时所做的对当前问题状态 产生影响的事情应该全部失效,这就是所谓的“回溯时还原现场”。
分治法 则是把一个问题划分为若干个规模更小的同类子问题,对这些子问题递归求解,然后在回溯时通过它们推导出原问题的解
枚举形式 | 状态空间规模 | 一般遍历方式 |
---|---|---|
多项式 | \(n^k\),\(k\) 为常数 | 循环(for)、递推 |
指数 | \(k^n\),\(k\) 为常数 | 递归、位运算 |
排列 | \(n!\) | 递归、C++ next_permutation |
组合 | \(C_n^m\) | 递归+剪枝 |
,
为常数 循环(for)、递推 指数
,
为常数 递归、位运算 排列
递归、C++ next_permutation 组合
递归+剪枝
从
这
个整数中随机选取任意多个,输出所有可能的选择方案。
输入格式
输入一个整数
。
输出格式
每行输出一种方案。
同一行内的数必须升序排列,相邻两个数用恰好
个空格隔开。
对于没有选任何数的方案,输出空行。
本题有自定义校验器(SPJ),各行(不同方案)之间的顺序任意。
数据范围
输入样例:
3
输出样例:
3
2
2 3
1
1 3
1 2
1 2 3
vector<int> chosen;
void calc(int x)
{
if (x == n + 1)
{
for (int i = 0; i < chosen.size(); i ++ )
printf("%d ", chosen[i]);
puts("");
return;
}
calc(x + 1);
chosen.push_back(x);
calc(x + 1);
chosen.pop_back();
}
int main()
{
scanf("%d", &n);
calc(1);
return 0;
}
从
这
个整数中随机选出
个,输出所有可能的选择方案。
输入格式
两个整数
,在同一行用空格隔开。
输出格式
按照从小到大的顺序输出所有方案,每行
个。
首先,同一行内的数升序排列,相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面(例如 1 3 5 7
排在 1 3 6 8
前面)。
数据范围
,
,
输入样例:
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
void calc(int u)
{
if (chosen.size() > m || chosen.size() + (n - u + 1) < m) return;
// 除了上面一步剪枝,剩余部分同上一题一摸一样
...
}
把
这
个整数排成一行后随机打乱顺序,输出所有可能的次序。
输入格式
一个整数
。
输出格式
按照从小到大的顺序输出所有方案,每行
个。
首先,同一行相邻两个数用一个空格隔开。
其次,对于两个不同的行,对应下标的数一一比较,字典序较小的排在前面。
数据范围
输入样例:
3
输出样例:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
int order[20];
bool chosen[20];
void calc(int u)
{
if (u == n + 1)
{
for (int i = 1; i <= n; i ++ )
printf("%d ", order[i]);
puts("");
return;
}
for (int i = 1; i <= n; i ++ )
{
if (chosen[i]) continue;
chosen[i] = true;
order[u] = i;
calc(u + 1);
order[u] = 0;
chosen[i] = false;
}
}
你玩过“拉灯”游戏吗?
盏灯排成一个
的方形。
每一个灯都有一个开关,游戏者可以改变它的状态。
每一步,游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应:和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字
表示一盏开着的灯,用数字
表示关着的灯。
下面这种状态
10111
01101
10111
10000
11011
在改变了最左上角的灯的状态后将变成:
01111
11101
10111
10000
11011
再改变它正中间的灯后状态将变成:
01111
11001
11001
10100
11011
给定一些游戏的初始状态,编写程序判断游戏者是否可能在
步以内使所有的灯都变亮。
输入格式
第一行输入正整数
,代表数据中共有
个待解决的游戏初始状态。
以下若干行数据分为
组,每组数据有
行,每行
个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式
一共输出
行数据,每行有一个小于等于
的整数,它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态,若
步以内无法使所有灯变亮,则输出
。
数据范围
输入样例:
3
00111
01011
10001
11010
11100
11101
11101
11110
11111
11111
01111
11111
11111
11111
11111
输出样例:
3
2
-1
易发现三个简单性质:
根据上述性质而生的枚举策略:先确定第一行的状态,共
种可能
然后根据第 i 行确定的状态,递推出第 i+1 行的方案
最后检查最后一行的状态是否合法,即可确定该方案是否合法
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, 1, 0, -1};
char g[N][N], b[N][N];
void turn(int i, int j)
{
for (int d = 0; d < 5; d ++ )
{
int x = i + dx[d], y = j + dy[d];
if (x < 0 || x >= n || y < 0 || y >= n) continue;
g[x][y] ^= 1;
}
}
void solve()
{
for (int i = 0; i < n; i ++ ) cin >> b[i];
int res = -1;
for (int op = 0, cnt; cnt = 0, op < 1 << n; op ++ )
{
memcpy(g, b, sizeof g);
for (int i = 0; i < n; i ++ )
if (op >> i & 1)
turn(0, i), cnt ++ ;
for (int i = 1; i < n; i ++ )
for (int j = 0; j < n; j ++ )
if (g[i - 1][j] == '0')
turn(i, j), cnt ++ ;
if (cnt > 6) continue;
bool flag = true;
for (int i = 0; i < n; i ++ )
if (g[n - 1][i] == '0')
flag = false;
if (flag && (res == -1 || res > cnt))
res = cnt;
}
cout << res << endl;
}
汉诺塔问题,条件如下:
个圆盘,
的数量是恒定的。
请你求出将所有圆盘从塔 A 移动到塔 D,所需的最小移动次数是多少。
输入格式
没有输入
输出格式
对于每一个整数
,输出一个满足条件的最小移动次数,每个结果占一行。
数据范围
易知 3 根柱子的情况下,汉诺塔的递推公式为:
即考虑最后一步:
个盘子用 B、C 两柱 轮流操作,从 A柱 移到 B柱
接着我们用 3柱 情况推导 4柱 情况
个盘子用 B、C、D 三柱 轮流操作,从 A柱 移到 B柱
个盘子用 C、D 两柱 轮流操作,从 A柱 移到 C柱
个盘子从 C柱 移到 D柱
个盘子从 B柱 移到 D柱
有递推式:
根据上述推导,继续套循环递推,可以解时间允许条件下的任意
柱
盘的问题
int f[15], d[15];
int main()
{
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int n = 1; n <= 12; n ++ )
{
d[n] = 2 * d[n - 1] + 1;
for (int i = 0; i < n; i ++ )
f[n] = min(f[n], 2 * f[i] + d[n - i]);
cout << f[n] << endl;
}
return 0;
}
假设现在有两个自然数
和
,
是
的所有约数之和
请你求出
的值
输入格式
在一行中输入用空格隔开的两个整数
和
输出格式
输出一个整数,代表
的值
数据范围
输入样例:
2 3
输出样例:
15
注意:
和
不会同时为
考虑直接模拟,有
,由此易得
由乘法分配律,易得
的所有约数之和为:
如果直接模拟这个过程,根据公式去求解
,直接迭代求,显然复杂度会爆掉
易想到的一个优化是对每一个括号用等比数列求和公式,但是公式中有除法,在模运算下做等效除法需要求逆元
不过本题的模数
是质数,可以用 费马小定理 结合 快速幂 求逆元,否则就要用 BSGS 了
不妨换一种思路考虑本题,采用 分治 的思想来求解
,不妨设
为奇数,则
状态空间 的 问题边界 为
利用该分治思想,求解本问题
int calc(int p, int c)
{
if (!c) return 1;
if (c & 1) return (calc(p, c / 2) * (power(p, (c + 1) / 2) % mod + 1)) % mod;
return (power(p, c) + calc(p, c - 1)) % mod;
}
城市的规划在城市建设中是个大问题。
不幸的是,很多城市在开始建设的时候并没有很好的规划,城市规模扩大之后规划不合理的问题就开始显现。
而这座名为 Fractal 的城市设想了这样的一个规划方案,如下图所示:
当城区规模扩大之后,Fractal 的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围,提升城市的等级。
对于任意等级的城市,我们把正方形街区从左上角开始按照道路标号。
虽然这个方案很烂,Fractal 规划部门的人员还是想知道,如果城市发展到了等级
,编号为
和
的两个街区的直线距离是多少。
街区的距离指的是街区的中心点之间的距离,每个街区都是边长为
米的正方形。
输入格式
第一行输入正整数
,表示测试数据的数目。
以下
行,输入
组测试数据,每组一行。
每组数据包括三个整数
,
,
,表示城市等级以及两个街区的编号,整数之间用空格隔开。
输出格式
一共输出
行数据,每行对应一组测试数据的输出结果,结果四舍五入到整数。
数据范围
,
,
输入样例:
3
1 1 2
2 16 1
3 4 33
输出样例:
10
30
50
显然,
级城市由四座
级城市组成,其中左上的
级城市顺时针旋转了90度再左右翻转,左下的
级城市逆时针旋转了90度再左右翻转,其余两座
级城市没有发生变化。
因此,在求解
时,因为
级城市有
座房屋
所以可以先递归求解
,找出在
级城市中,目标的位置
记为
再根据
推断出目标所在的
级城市的编号,并根据该编号对
进行坐标变换
四个编号的具体变换:(从0开始编号,
级城市边长为
)
级城市
级城市
级城市单位,坐标变为:
级城市
级城市单位,坐标变为:
级城市
级城市单位,坐标变为:
pair<long long, long long> calc(int n, long long m)
{
if (!n) return {0, 0};
long long len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
pair<long long, long long> pos = calc(n - 1, m % cnt);
long long x = pos.x, y = pos.y;
long long z = m / cnt;
if (z == 0) return {y, x};
if (z == 1) return {x, y + len};
if (z == 2) return {x + len, y + len};
if (z == 3) return {2 * len - 1 - y, len - 1 - x};
}