「学习笔记」递推 & 递归
引入
假设我们想计算 \(f(x) = x!\)。除了简单的 for 循环，我们也可以使用递归。
递归是什么意思呢？我们可以把 \(f(x)\) 用 \(f(x – 1)\) 表示，即 \(f(x) = x \times f(x – 1)\)。这样，我们就可以不断地递归下去。
但是，这是永远不会停止的。我们需要设立一个边界条件，\(f(0) = 1\)。这样，我们就可以写出代码了。
int f(int x) {return x ? x * f(x - 1) : 1;}
实际上，递归有两大要点：
- 自己调用自己；
- 回溯时还原现场。
如果你看到这里，你或许已经懂了递归。那么，递推是什么呢？把上面的计算阶乘的递归改成递推就是这样的：
f[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = f[i - 1] * i;
一个有趣的例子：什么是递归？
「例题」数楼梯
原题目链接：Link。
我们用递推的视角思考一下。假设我们要走到第 \(i\) 阶台阶，我们应该怎样走？
记走第 \(i\) 阶台阶的走法为 \(f_i\)，则显然，我们可以从第 \(i – 1\) 阶台阶上一阶台阶到第 \(i\) 阶台阶，也可以从第 \(i – 2\) 阶台阶上二阶台阶到第 \(i\) 阶台阶。根据加法原理，有 \(f_i = f_{i – 1} + f_{i – 2}\)。
递推边界可以根据题意得到。一阶台阶有 \(1\) 种走法，二阶台阶有 \(2\) 种走法，即 \(f_1 = 1, f_2 = 2\)。
// Python Version
n = int(input())
a, b = 1, 2
if n < 3:
print(n)
for i in range(n - 2):
c = a + b
a, b = b, c
if n >= 3:
print(c)
# 可以使用滚动数组来优化，这里 a 相当于 f[i - 2]，b 相当于 f[i - 1]，c 相当于 f[i]
# 注意特判
// C++ Version
#include <bits/stdc++.h>
using namespace std;
int n;
long long f[5005] = {0, 1, 2};
int main() {
cin >> n;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 2];
cout << f[n] << endl;
return 0;
}
这里 C++ 只能得到 \(60\) 分。这是因为我们得到的结果超出了 long long 的表示范围，需要使用高精度。
五大递推模型
Fibonacci 数列
Fibonacci 数列，一般译为斐波那契数列。Fibonacci 数列的边界为 \(f_1 = f_2 = 1\)，递推柿为 \(f_i = f_{i – 1} + f_{i – 2}\)。上面的数楼梯就是 Fibonacci 数列从第 \(2\) 项开始的数列。
Fibonacci 数列还有一种表现形式，就是可爱的小兔子。
「例题」兔子的数量
原题目链接：Link。
可以轻松写出代码。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int a[MAXN] = {0, 1, 1}, n;
int main() {
cin >> n;
for (int i = 3; i <= n; i++)
a[i] = a[i - 1] + a[i - 2];
cout << a[n] << endl;
return 0;
}
Fibonacci 数列还有一个通项公式：\(f_n = \frac1{\sqrt5}[(\frac{1 + \sqrt5}{2}) ^ n – (\frac{1 – \sqrt5}{2}) ^ n]\)。
Catalan 数
Catalan 数的实际应用很多。这里我们来通过一道 NOIP 的题目来引出 Catalan 数。
「例题」栈
原题目链接：Link。
我们可以设 \(i\) 个小球时，出管方式为 \(h_i\)。我们于是可以按最后一个出管的小球来讨论。假设最后一个出管的为第 \(k\) 个小球，那么比 \(k\) 早入管的小球为 \(k – 1\) 个，比 \(k\) 晚入管的小球为 \(n – k\) 个。这些小球全部出管之后，第 \(k\) 个小球才出管。根据乘法原理，最后一个出管的小球为第 \(k\) 个时，取法总数为 \(h_{k – 1} \times h_{n – k}\)。而 \(k\) 可以取 \(1\) 到 \(n\)。所以总共的取法总数就是 \(h_n = \sum_{i = 1} ^ n h_{i – 1} \times h_{n – i}\)。这就是 Catalan 数的递推柿了。递推边界显然：\(f_0 = f_1 = 1\)。
#include <bits/stdc++.h>
using namespace std;
int n, h[20] = {1, 1};
int main() {
cin >> n;
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
h[i] += h[j - 1] * h[i - j];
cout << h[n] << endl;
return 0;
}
Catalan 数列的应用：
- 把一个凸 \(n\) 边形划分为数个三角形的方案数（不相交）。
- 一个栈的进栈序列为 \(1, 2, 3, \dots, n\)，不同的出栈序列数。
- \(n\) 个节点可以构造多少个不同的二叉树的方案数。
- 在圆上选择 \(2 \times n\) 个点，把这些点成对连接起来使得所得到的 \(n\) 条线段不相交的方法数。
- 从点 \((0, 0)\) 到点 \((n, n)\)，不穿越但可以碰到对角线的最短走法数。
除了递推，Catalan 数 \(h_n\) 还可以通过通项公式得到：\(h_n = \frac{C_{2n} ^ n}{n + 1} = C_{2n} ^ n – C_{2n} ^ {n – 1}\)。
Hanio 塔
Hanio 塔是一个非常经典的递推（递归）问题。或许很多人在感受 C++ 的强大时，教练展示的第一个程序就是 Hanio 塔。
「例题」Hanio 塔问题
原题目链接：Link。
我们设 \(h_i\) 为移动 \(i\) 个盘子所需要的次数。显然地，我们可以先把上面的 \(i – 1\) 个盘子移动到 B 柱上，再把第 \(i\) 的盘子移到 C 柱上，最后把 B 盘上的 \(i – 1\) 个盘子移到 C 柱上。那么，递推柿就出来了：\(h_i = 2 \times h_{i – 1} + 1\)，边界 \(h_1 = 1\)。Hanio 塔同样有通项公式 \(h_n = 2 ^ n – 1\)。
# Python Version
n = int(input())
# print(2 ** n - 1)
# 这样可以直接输出
a = 1
for i in range(n - 1):
a = a * 2 + 1
print(a)
// C++ version
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 65;
long long a[MAXN] = {0, 1};
int n;
int main() {
cin >> n;
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] << 1 | 1;
cout << a[n] << endl;
return 0;
}
第二类 Stirling 数
「例题」合理放球
原题目链接：Link。
我们可以设 \(S_{n, m}\) 为 \(n\) 个不相同的球放入 \(m\) 个相同的盒子（不为空）里的放法总数。
思考对于第 \(n\) 个球的放法。我们可以把这第 \(n\) 个球单独放一个盒子，那么前面的 \(n – 1\) 个球就要挤占 \(m – 1\) 个盒子，方案数为 \(S_{n – 1, m – 1}\)；也可以把这第 \(n\) 个球与其他的球共占一个盒子，那么前面的 \(n – 1\) 个球就要挤占 \(m\) 个盒子（第 \(n\) 个球没有额外占用盒子），那么方案数为 \((n – 1) \times S_{n – 1, m}\)。由加法原理知，\(S_{n, m} = S_{n – 1, m – 1} + (n – 1) \times S_{n – 1, m}\)。
递推边界：\(S_{n, n} = S_{n, 1} = S_{1, m} = 1\)。
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long S(int n, int m) {
if (n == 1 || m == 1 || n == m) return 1;
return S(n - 1, m - 1) + m * S(n - 1, m);
}
int main() {
scanf("%d %d", &n, &m);
printf("%lld\n", S(n, m));
return 0;
}
分割平面问题
这类问题比较多变，有时很困难，重点是要去找到规律（废话）。
「例题」分割平面
题意简述：设有 \(n\) 条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。
数据范围：\(1 \leq n \leq 46314\)。
观察图片，可以发现，如果设 \(f_n\) 表示由 \(n\) 条封闭曲线时，题意中的区域个数，则有 \(f_n = f_{n – 1} + 2 \times (i – 1)\)。\(f_1 = 2\)。
证明也比较显然。当画第 \(n\) 条曲线时，会与每条之前画的 \(n – 1\) 条曲线形成 \(2\) 个交点，多一个交点就多一个区域，由此可得。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 46350;
int n;
long long a[MAXN] = {0, 2};
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++)
a[i] = a[i - 1] + ((i - 1) << 1);
printf("%lld\n", a[n]);
return 0;
}
让我们再来看一道题，加深印象。
「例题」分割平面之二
题意简述：同一平面内有 \(n\) 条直线，已知其中 \(p\) 条直线相交于同一点，则这 \(n\) 条直线最多能将平面分割成多少个不同的区域？
数据范围：\(2 \leq p \leq n \leq 500\)。
与上一题类似地设出 \(f_n\)。画图容易发现 \(p\) 条直线相交于同一点会产生 \(2p\) 个区域，第 \(i\) 条直线会相交多产生 \(i\) 个区域，所以有 \(f_i = f_{i – 1} + i (i > p)\)，边界为 \(f_p = 2p\)。
#include <bits/stdc++.h>
using namespace std;
int n, p;
int f[505];
int main() {
cin >> n >> p;
f[p] = p << 1;
for (int i = p + 1; i <= n; i++)
f[i] = f[i - 1] + i;
cout << f[n] << endl;
return 0;
}
记忆化
有些时候，使用递归会超时，原因是进行了大量的重复运算导致效率低下。而记忆化就可以提升效率。甚至于你可以用记忆化搜索来代替 DP。
「例题」Function
原题目链接：Link。
我们可以按题意容易地写出朴素代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
#define LL long long
LL a, b, c;
int w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
return w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
while (~scanf("%lld %lld %lld", &a, &b, &c)) {
if (a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}
试一试样例，哇，只用了 \(22\) 毫秒就过了！
然后交上去，快乐 TLE。
这是为什么呢？如果我们把 \(w\) 函数加上 cout << a << " " << b << " " << c << endl;，再运行，你会发现输出了很多行，但其中有许多是重复的。
这启发我们，可以用一个数组 \(f\) 来存储 \(w_{a, b, c}\)，如果已经得到过这个值就可以直接返回，避免无效运算。这就是记忆化。在这道题中，我们使用 \(-1\) 表示没有算过。具体地说，如果 \(f_{a, b, c} = -1\)，那么没有计算过，我们就直接计算，并把结果存储在 \(f_{a, b, c}\) 中；否则算过就直接 return \(f_{a, b, c}\) 即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
#define LL long long
int f[MAXN][MAXN][MAXN];
LL a, b, c;
int w(LL a, LL b, LL c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
if (a < b && b < c) {
if (f[a][b][c] != -1) return f[a][b][c];
// 如果已经得到值，直接返回
return f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
// 否则计算这个值，并存储起来，下一次就不会继续递归了
}
if (f[a][b][c] != -1) return f[a][b][c];
// 同上
return f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
int main() {
memset(f, -1, sizeof(f)); // 全部初始化为 -1 表示没有得到值
while (~scanf("%lld %lld %lld", &a, &b, &c)) {
if (a == -1 && b == -1 && c == -1) break;
printf("w(%lld, %lld, %lld) = %d\n", a, b, c, w(a, b, c));
}
return 0;
}
怎么样，你学废了吗？
让我们一起来看一道 IOI 的题目（好吧是 \(1994\) 年的）。
「例题」数字三角形 Number Triangles
原题目链接：Link。
假设你不会递推。我们可以设 \(f_{i, j}\) 表示从 \((i, j)\) 走到最底下的最大的和。那么，显然有 \(f_{i, j} = w_{i, j} + \max(f_{i + 1, j}, f_{i + 1, j + 1})\)。写成代码就是这样的：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int w[MAXN][MAXN];
int f(int i, int j) {
if (i == n) return w[i][j]; // 已经不能再走了，直接返回 w[i][j]
return w[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
cout << f(1, 1) << endl;
return 0;
}
但这还是会超时，怎么办呢？
没错，我们可以使用记忆化。类似地，我们用 \(-1\) 表示没搜过 \((i, j)\)，如果不等于 \(-1\) 直接 return 即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int w[MAXN][MAXN], ans[MAXN][MAXN];
int f(int i, int j) {
if (i == n) return w[i][j];
if (ans[i][j] != -1) return ans[i][j];
return ans[i][j] = w[i][j] + max(f(i + 1, j), f(i + 1, j + 1));
}
int main() {
memset(ans, -1, sizeof(ans));
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> w[i][j];
cout << f(1, 1) << endl;
return 0;
}
其实，这已经有点 DP 的意味了。
杂题
「例题」铺砖
题意简述：有一个 \(2 \times n\) 的走道，现在用 \(1 \times 2\)，\(2 \times 2\) 的砖去铺满。问有多少种不同的铺法？
数据范围：多组数据，\(0 \leq n \leq 250\)。
先设 \(f_n\) 表示铺成 \(2 \times n\) 的走道的方案数。\(2 \times n\) 的走道是怎么铺成的？可以由一个 \(1 \times 2\) 的砖竖着铺在最右边，问题就转化为了铺剩下的 \(2 \times (n – 1)\) 的走道，方案数即为 \(f_{n – 1}\)；也可以由两个 \(1 \times 2\) 的砖横着铺在最右边，问题就转化为了铺剩下的 \(2 \times (n – 2)\) 的走道，方案数即为 \(f_{n – 2}\)；还可以直接由一个 \(2 \times 2\) 的砖铺在最右边，问题就转化为了铺剩下的 \(2 \times (n – 2)\) 的走道，方案数也为 \(f_{n – 2}\)。综上，我们可以得到递推柿 \(f_i = f_{i – 1} + f_{i – 2} \times 2\)。边界显然为 \(f_1 = 1, f_2 = 3\)。
注意这里是多测，所以可以提前处理出 \(f_3\) 至 \(f_{250}\)，一一回答即可。需要使用高精度。
「例题」统计奇数和偶数个 3
原题目链接：Link。
这里有两个维度：位数和奇偶。我们就可以把这两个维度设出来：设 \(f_{n, 0}\) 表示 \(n\) 位正整数中有多少个数含偶数个数字 \(3\)，\(f_{n, 1}\) 表示 \(n\) 位正整数中有多少数含个奇数个数字 \(3\)。
\(n\) 位正整数中，含偶数个数字 \(3\) 的数是怎么来的呢？有两种情况：
- 前面 \(n – 1\) 位含奇数个数字 \(3\)，第 \(n\) 位是 \(3\)。个数为 \(f_{n – 1, 1}\)。
- 前面 \(n – 1\) 位含偶数个数字 \(3\)，第 \(n\) 位不是 \(3\)（是 \(0, 1, 2, 4, 5, 6, 7, 8, 9\)）。个数为 \(f_{n – 1, 0} \times 8\)。
所以可以得到 \(f_{n, 0} = f_{n – 1, 1} + f_{n – 1, 0} \times 8\)。同理有 \(f_{n, 1} = f_{n – 1, 0} + f_{n – 1, 1} \times 8\)。
「例题」螺旋矩阵
原题目链接：Link。
思考如何递归，发现矩阵外面那一圈儿都是可以直接算出来的（知道 \(n\)）。接着观察除去外面那一圈儿后剩下的矩阵，发现只要减去 \(4n – 4\) 后就是一个新的矩阵。
拿这个图举个例子：
\(1 \sim 12\) 可以直接算出，而剩下的 \(13, 14, 15, 16\) 就相当于 \(12 + 1, 12 + 2, 12 + 3, 12 + 4\)。
代码如下：
#include <cstdio>
int n, i, j;
int f(int m, int x, int y) {
if (x == 1) return y;
if (x == m) return 3 * m - y - 1;
if (y == 1) return 4 * m - x - 2;
if (y == m) return m + x - 1; // 边界情况，可以自己推导
return f(m - 2, x - 1, y - 1) + 4 * m - 4;
// 规模缩小，记得加上 4 * m - 4
}
int main() {
scanf("%d %d %d", &n, &i, &j);
printf("%d\n", f(n, i, j));
return 0;
}
「例题」无限的路
原题目链接：Link。
给出两个点 \((x_1, y_1), (x_2, y_2)\)，要求连接的折线长度，为了方便计算，我们可以统一成到点 \((0, 0)\) 的折线长度，两者相减就会抵消，剩下我们要求的答案。
现在，问题就转化为给出点 \((x, y)\)，求它到点 \((0, 0)\) 的折线长度。
我们可以发现（结合图食用更佳）：
- 当 \(x = 0\) 时，我们可以从 \((0, y)\) 走到 \((y – 1, 0)\)，再加上点 \((y – 1, 0)\) 到点 \((0, 0)\) 的折线长度。
- 当 \(y = 0\) 时，我们可以从 \((x, 0)\) 走到 \((0, x)\)，再加上点 \((0, x)\) 到点 \((0, 0)\) 的折线长度。
- 当 \(x \not= 0\) 且 \(y \not= 0\) 时，我们可以从 \((x, y)\) 走到 \((0, x + y)\)，再加上点 \((0, x + y)\) 到点 \((0, 0)\) 的折线长度。
然后用上我们小学二年级就学过的两点间直线距离 \(\sqrt{(x_1 – x_2) ^ 2 + (y_1 – y_2) ^ 2}\) 就行了。边界显然是 \((0, 0)\)。
由于这里是 double 类型，不好直接记忆化，所以我们可以开一个 bool 数组打标记。代码如下：
#include <cstdio>
#include <cmath>
double ans[205][205];
bool flag[205][205];
double f(int x1, int my1, int x2, int y2) {
return sqrt(pow(x1 - x2, 2) + pow(my1 - y2, 2));
} // 两点间直线距离
int n, x1, x2, my1, y2; // y1 是关键字，随便加个字母
double g(int x, int y) {
if (!x && !y) return 0; // (0, 0) 边界
if (flag[x][y]) return ans[x][y]; // 已经搜过
flag[x][y] = true;
if (!x) return ans[x][y] = g(y - 1, 0) + f(x, y, y - 1, 0);
if (!y) return ans[x][y] = g(0, x) + f(x, y, 0, x);
return ans[x][y] = g(0, x + y) + f(x, y, 0, x + y); // 三种情况
}
int main() {
scanf("%d", &n);
while (n--) {
scanf("%d %d %d %d", &x1, &my1, &x2, &y2);
printf("%.3lf\n", fabs(g(x1, my1) - g(x2, y2))); // 记得加绝对值
}
return 0;
}
「例题」最大奇约数
原题目链接：Link。
每一个数都能表示成 \(x = 2 ^ k \times a\) 的形式（\(2 \nmid a\)），这道题的 \(f(x)\) 相当于求出 \(a\)。答案为 \(\sum _ {i = 1} ^ n f(i)\)。
如果老老实实地算 \(\sum _ {i = 1} ^ N f(i)\) 会超时，加上记忆化又会 MLE，这启发我们令一个函数 \(g(n) = \sum _ {i = 1} ^ n f(i)\)。
然后我们推公式。
- 当 \(2 \nmid n\)，显然 \(g(n) = n + g(n – 1)\)。
- 当 \(2 \mid n\)，发现 \(f(i)\) 可以根据奇偶性分成两类，\(f(2k) = f(k)\)，而 \(f(2k + 1) = 2k + 1\)。从而也可以把 \(\sum _ {i = 1} ^ n f(i)\) 分成两类，一类是 \(f(1) + f(3) + f(5) + \dots + f(n – 1) = 1 + 3 + 5 + \dots + (n – 1)\)，一类是 \(f(2) + f(4) + f(6) + \dots + f(n) = f(1) + f(2) + f(3) + \dots + f(\frac{n}{2})\)；前者可以等差数列求和暴算，而后者发现就等于 \(f(\frac{n}2)\)，直接递归即可。
#include <cstdio>
int n;
long long f(int x) {
if (x == 1) return 1; // 边界条件
if (x & 1) return f(x - 1) + x;
return f(x >> 1) + (long long)x * x / 4;
// 因为 x * x 可能会溢出，所以先转换成 long long 再乘
}
int main() {
scanf("%d", &n);
printf("%lld\n", f(n));
return 0;
}
「例题」Strange Towers of Hanoi
原题目链接：Link。
题目要求我们求 Hanoi 塔的移动步数。这个简单，秒了！——真的这么简单吗？啊，是 \(4\) 座塔！（一般的 Hanoi 塔是 \(3\) 座。）
不过，题目中有这样一段话：
此算法适用于 \(n \leq 12\)：塔 A 上的 \(k\)（\(k \geq 1\)）个盘子是固定的，其余 \(n – k\) 个盘子使用四塔算法从 A 移到 B。然后用三塔算法把 A 上的 \(k\) 个盘子移到 D，最后使用四塔算法将 B 上的 \(n – k\) 个盘子再次移动到 D。
可以设 \(n\) 个盘子时用三塔需要 \(g_n\) 步，我们有这样的方案：把 A 最上面的 \(n – 1\) 个盘子移到 B，A 上的第 \(n\) 个盘子移到 C，然后把 B 上的 \(n – 1\) 个盘子移到 C。从而有 \(g_n = 2 \times g_{n – 1} + 1\)。
再设 \(n\) 个盘子时用四塔需要 \(f_n\) 步。因为题目已经告诉了我们公式，遍历 \(k\) 取 \(\min\) 即可，不用白不用哇：
\]
「例题」棋子移动
原题目链接：Link。
首先，我们发现 \(n = 4\) 时仅有这一种固定移动方法：
4,5-->9,10
8,9-->4,5
2,3-->8,9
7,8-->2,3
1,2-->7,8
这显然就是递归边界。那当 \(n > 4\) 时呢（下面设 \(n = 5\)）？
〇〇〇〇〇●●●●●
容易想到，先把中间的移到最右边。
〇〇〇〇[ ][ ]●●●●〇●
然后把最右边的两个黑棋子移到空位里去。
〇〇〇〇●●●●[ ][ ]〇●
发现左边缩小规模成了 \(n – 1 = 4\) 的情况，继续递归即可。
代码十分简单：
#include <cstdio>
#include <iostream>
int n;
void print(int n) {
if (n == 4) {
puts("4,5-->9,10\n\n8,9-->4,5\n\n2,3-->8,9\n\n7,8-->2,3\n\n1,2-->7,8");
return;
}
std::cout << n << "," << n + 1 << "-->" << (n << 1 | 1) << "," << (n * 2 + 2) << std::endl << std::endl;
std::cout << 2 * n - 1 << "," << (n << 1) << "-->" << n << "," << n + 1 << std::endl << std::endl;
print(n - 1);
}
int main() {
std::cin >> n;
print(n);
return 0;
}
By the way，建议大家输出复杂格式时还是用 printf，cout 要打死了。。。
「例题」分形图1
原题目链接：Link。
题目要求我们输出一个奇怪的 X 形分形图。观察发现，当规模为 \(n\) 时，其实就是由 \(5\) 个规模为 \(n – 1\) 的 X 形组合而成。一般对于这种分形图，我们都会递归规模和坐标。
代码非常简单：
#include <bits/stdc++.h>
using namespace std;
int n;
char ch[735][735];
void print(int n, int x, int y) { // n 是规模，(x, y) 是图形左上角坐标
if (n == 1) {
ch[x][y] = 'X';
return;
} // 边界情况
int t = pow(3, n - 2); // n - 1 规模图形的长（宽）
print(n - 1, x, y); // 打印左上
print(n - 1, x + (t << 1), y); // 打印左下
print(n - 1, x + t, y + t); // 打印中间的
print(n - 1, x, y + (t << 1)); // 打印右上
print(n - 1, x + (t << 1), y + (t << 1)); // 打印右下
}
int main() {
while (cin >> n) {
memset(ch, 0, sizeof(ch)); // 记得清零
print(n, 1, 1);
int len = pow(3, n - 1);
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= len; j++)
if (ch[i][j]) putchar(ch[i][j]);
else putchar(' ');
// 没填充到的地方默认是 0，直接输出的话，肉眼看不出与空格的差别，但是会 WA
// 所以这里特判一下
putchar('\n');
}
putchar('-');
putchar('\n');
}
return 0;
}
附上一个奇怪分形图的代码：
#include <iostream>
using namespace std;
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
putchar((i & j) ? '#' : ' ');
putchar('\n');
}
return 0;
}
可以试试用递归实现。
