刷到《算法竞赛进阶指南》0x02 里“递推与递归”这一章的人多半会被“分形之城”这道题卡住一阵子。这题表面上是一个城市规划的图形题实际上考的却是一套非常典型的递归坐标映射给你一个 N 级城市里的两个房屋编号让你求这两座房子在现实平面上的直线距离。我第一次做这题的时候愣是盯着题面里的那张分形图看了半天还以为要模拟整座城的建造过程后来顺着“递归”“分块”“旋转”这些关键词才慢慢揭开它的底层逻辑。这篇分享就围绕“分形之城”的递归解法展开重点说清楚三个事情为什么它能用递推做、四个区块的坐标变换到底怎么来的、以及实际写代码的时候有哪些容易踩的坑。不管是刚学递归的新手还是在备战算法竞赛想快速过一遍思路的老手看完应该都能直接自己写出一份能过样例的实现。1. 题目到底在说什么一座由递归规则长出来的城市1.1 先建立 N 级城市的递归定义很多初学者一看到“分形”第一反应是图形复杂、函数复杂。其实这道题最妙的地方在于它把“城市”定义成了一个递归结构1 级城市是一个 2×2 的街区里面住着 4 户人家N 级城市是把 4 个 N-1 级城市按照特定的旋转和平移方式拼成一个 2×2 的大城区。所以 N 级城市的总边长是 2^N总房屋数是 2^(2N) 4^N。这里要特别注意“边长”和“房屋数”的区别边长是 2 的幂房屋数是 4 的幂。很多代码写错就是因为在计算子城面积的时候习惯性地用了与边长一样的幂次。这种定义方式决定了我们不需要真的把城市画出来。只要能从编号反推坐标递归结构会自动帮我们定位到每一级城市里的相对位置。而“从编号到坐标”的过程正是这题的核心。1.2 房屋编号的内部顺序题目中编号并不是随便排的它遵循着分形结构的连接顺序。以小的一级城市为例如果把 4 个房屋按照编号顺序连接起来会形成一条类似蛇形的连续曲线。我在这篇分享里统一采用如下坐标约定坐标 (x, y) 分别表示“行”和“列”都从 0 开始x 向下增长y 向右增长。那么一级城市中 4 个编号对应的坐标是编号坐标0(0, 0)1(0, 1)2(1, 1)3(1, 0)画成表格就是0 1 3 2你会发现编号 0 → 1 → 2 → 3 正好走了一条从左到右、再从上到下、最后回到左侧的“S”形路线。这条路线就是低一级城市的基本骨架也是理解整个分形递归的关键。注意有的题目版本会把编号改成 1-based也就是房屋编号从 1 到 4^N。此时只要在传参前统一把编号减 1 即可核心递归逻辑完全不用变。2. 从编号到坐标四个区块的落位逻辑2.1 为什么可以按四等份递归假设当前要求的是 N 级城市中编号为 id 的房屋坐标。先看 N-1 级城市的规模边长是 2^(N-1)房屋数是 len × len其中 len 2^(N-1)。N 级城市由 4 个 N-1 级子城拼成。我们可以直接通过一次整数除法确定编号 id 落在哪个子城子城编号 block id / (len × len)子城内部编号 rest id % (len × len)这就是“递推”的入口。只要递归求解 getPos(N-1, rest)得到它在子城内部的坐标 (x, y)再根据 block 对应的旋转和平移规则把内部坐标转换到 N 级城市的全局坐标即可。这个思路的本质是分治大问题拆成小问题小问题的结果再通过变换组合成大问题的结果。递归深度最多 N 层而 N 一般不超过 31所以时间复杂度是 O(N)空间复杂度是 O(N)完全足以应对大多数竞赛数据。2.2 四个区块的变换关系四个子城在全局中的位置分别是左上、右上、右下、左下。它们的变换方式如下区块全局位置坐标变换0左上(x, y) → (y, x)1右上(x, y) → (x, y len)2右下(x, y) → (x len, y len)3左下(x, y) → (2×len - 1 - y, len - 1 - x)这个表是整道题的核心。很多人选择直接背下来但我还是建议理解一下左上和左下两个区块的变换为什么这么写。左上区块要把子城的出口接到右上区块的入口。如果只是平移那么从编号顺序上看就会断层。通过观察一级城市的基本走向可以发现把子城的坐标做“行、列互换”也就是转置刚好能让编号连接处自然衔接。这也就是 case 0 为什么返回 (y, x) 的原因。左下区块更复杂一些。它既要保证编号从上方的右下区块接续下来又要让整个城市最终收尾在左下角。从几何上看它相当于把子城旋转了一下再平移到左下区域。公式里的2×len - 1 - y就是把原本较小的 y 反向映射到下方区域len - 1 - x则保证列方向也落在左半区。如果不理解公式最简单可靠的验证方式就是拿 N1 的子城手动套一遍得到一个 N2 的完整坐标表。下面就是我们这套公式推出来的 4×4 城市布局0 3 4 5 1 2 7 6 14 13 8 9 15 12 11 10你可以沿着编号 0 → 1 → 2 → 3 → … → 15 走一遍会发现它确实是一条连续不断的曲线。这也是我调试时最常用的小技巧用小规模数据生成整个布局表格肉眼看看编号顺序是否连通。3. 核心代码实现3.1 前置准备递归函数需要用到两个关键数值len 2^(N-1)子城的边长area len × len子城的房屋总数对应 4^(N-1)。N 最大到 31 左右时len × len 大约是 2^60已经超过 int 的范围所以这里所有相关变量都应该使用 long long。如果你还在用 int 存边长和面积N 稍微给大一点就会出问题而且这种问题往往不是编译报错而是答案莫名其妙地错。3.2 C 实现直接给出一个可供复制的核心递归函数#include bits/stdc.h using namespace std; typedef long long ll; pairll, ll getPos(int n, ll id) { if (n 0) return {0, 0}; ll len 1LL (n - 1); ll area len * len; int block id / area; ll rest id % area; auto p getPos(n - 1, rest); ll x p.first, y p.second; switch (block) { case 0: return {y, x}; // 左上 case 1: return {x, y len}; // 右上 case 2: return {x len, y len}; // 右下 default: return {2 * len - 1 - y, len - 1 - x}; // 左下 } } int main() { int T; scanf(%d, T); while (T--) { int n; ll a, b; scanf(%d%lld%lld, n, a, b); // 如果题目编号从 1 开始这里统一转成 0-based // a--; b--; ll dx getPos(n, a).first - getPos(n, b).first; ll dy getPos(n, a).second - getPos(n, b).second; long double dist sqrtl((long double)(dx * dx dy * dy)); long long ans llround(dist * 10.0L); printf(%lld\n, ans); } return 0; }代码很短但每一行都值得拆开看。getPos的基本条件是 N0也就是 1×1 的子城编号只能是 0坐标自然是 (0, 0)。这个基本条件保证了递归能够一级一级往上返。主函数里的dx * dx dy * dy在 N31 时仍然在 long long 范围内因为坐标最大是 2^31 量级平方后是 2^62 量级没有超过 9.22×10^18 的上限。如果题目给到 N32那就需要另想办法但竞赛版的分形之城一般不会设计到超过这个范围。3.3 用 Python 快速验证C 适合最终提交但调试阶段用 Python 会更舒服。尤其是生成小规模布局表的时候Python 的递归和元组拆包写起来非常直观。def get_pos(n, pid): if n 0: return (0, 0) L 1 (n - 1) area L * L q, r divmod(pid, area) x, y get_pos(n - 1, r) if q 0: return (y, x) if q 1: return (x, y L) if q 2: return (x L, y L) return (2 * L - 1 - y, L - 1 - x) # 打印 n2 的 4x4 编号布局 n 2 grid [[0] * (1 n) for _ in range(1 n)] for idx in range(1 (2 * n)): x, y get_pos(n, idx) grid[x][y] idx for row in grid: print( .join(f{v:2d} for v in row))这一段可以用来做最基础的 sanity check。正常情况下会输出0 3 4 5 1 2 7 6 14 13 8 9 15 12 11 10如果你改了旋转方向或者区块顺序这个表格就会变得不连续比如出现编号断层或坐标重叠。所以调试时不要只测一两组样例一定要先测这样的“全量布局表”。4. 距离计算与精度陷阱4.1 单位换算题目通常会给一个单位长度。很多版本里相邻两栋房屋之间距离是 10所以最终答案为答案 round(欧氏距离 × 10)例如一级城市中编号 0 和编号 2 的坐标分别为 (0, 0) 和 (1, 1)欧氏距离是 sqrt(2)最终结果就是 sqrt(2)×10 ≈ 14.14四舍五入到 14。这个例子常被当成样例来验证代码。4.2 四舍五入的写法C 里四舍五入可以用llround它会返回 long long。注意不要直接用printf(%.0Lf)因为浮点数打印格式可能因为精度问题出现 0.5 边界上的差异。我习惯这样写long long ans llround(dist * 10.0L);这里dist用sqrtl计算 long double 版本。虽然误差很小但竞赛题对边界往往比较敏感能用高精度就用高精度。4.3 出现负坐标怎么办正常变换公式不会产生负坐标。只要 N 和编号合法四个象限的变换都会把坐标限制在 [0, 2^N - 1] 范围内。如果在调试中发现负坐标或超出边界的坐标几乎可以肯定是递归中block或rest计算错误或者基本条件写错了。5. 常见错误和调试技巧5.1 容易踩的四个坑错误类型具体表现解决方案类型容量不足N 稍大时答案异常坐标、面积、编号全部用 long long子城面积算错使用了 2^n 而不是 4^(n-1)area len × len其中 len 2^(n-1)编号基数不统一输入从 1 开始但没减 1计算前统一转换编号左下变换写错坐标重叠或布局断裂用 n2 的全量布局表检查5.2 用 n2 的布局表快速定位调试递归题不要只盯着单个函数的返回值。最有效的做法是写一个循环把某级城市的全部编号映射成坐标然后按坐标填充到一个二维数组里再打印出来。用我之前给的 Python 脚本跑一次 n2 或 n3一眼就能看出来四个区块的变换对不对。比如常见的错误之一是把左下区块的公式写成return {2 * len - y, len - 1 - x};少了那个-1。结果就是左下区块整体往外偏移一格打印出来的二维表中左下区域会出现边界外的坐标或者出现坐标重叠。这种错误靠样例输入很难发现但靠布局表立刻就能看出来。5.3 递推改迭代如果担心递归深度或者环境对递归栈限制比较严也可以用迭代方式实现。核心思路是把每一层的(block, rest)记录到栈里逐层确定编号归属再反向结算坐标。不过对于 N ≤ 31 的规模递归栈深度完全在安全范围内所以这道题用递归反而是更清晰的选择。迭代版的思路很简单但写起来比递归容易乱。我的建议是先把递归版写对、调通再考虑改成迭代版不要一上来就在迭代的坐标变换里绕晕。6. 一点扩展分形问题的一般套路“分形之城”这道题并不是孤例。很多分形相关题目都遵循同样的模式把大图形拆成若干个小的相似图形然后定义编号与子图形之间的映射关系。解决这类问题的核心永远是两条第一找到“分块编号到子块编号”的递推关系第二找到“子块坐标到全局坐标”的几何变换。只要这两条路打通了剩下的就是代码实现和精度处理。平时遇到这种题不要急着背公式先拿小规模图形把布局表打出来理解一遍编号是怎么连续走的再回到公式里看那些常数到底在做什么。这样即使题目换一个方向旋转你也能根据布局表反推出新的变换公式。我在实际做这题的时候最受益的并不是代码本身而是把“递归”从一种函数调用方式升级成了一种空间划分思路。分形之城的 N 级城市本质上就是一张巨大的递归索引表每次通过编号除以子城面积都能把我们准确地丢进下一层更小的地图里。想清楚这一步剩下的所有旋转和平移就都只是细节了。 
长河君 · 2026/10/24 4:38:20 · 阅读 1.2k 分形之城递归解法：坐标变换、距离计算与C++实现
刷到《算法竞赛进阶指南》0x02 里“递推与递归”这一章的人多半会被“分形之城”这道题卡住一阵子。这题表面上是一个城市规划的图形题实际上考的却是一套非常典型的递归坐标映射给你一个 N 级城市里的两个房屋编号让你求这两座房子在现实平面上的直线距离。我第一次做这题的时候愣是盯着题面里的那张分形图看了半天还以为要模拟整座城的建造过程后来顺着“递归”“分块”“旋转”这些关键词才慢慢揭开它的底层逻辑。这篇分享就围绕“分形之城”的递归解法展开重点说清楚三个事情为什么它能用递推做、四个区块的坐标变换到底怎么来的、以及实际写代码的时候有哪些容易踩的坑。不管是刚学递归的新手还是在备战算法竞赛想快速过一遍思路的老手看完应该都能直接自己写出一份能过样例的实现。1. 题目到底在说什么一座由递归规则长出来的城市1.1 先建立 N 级城市的递归定义很多初学者一看到“分形”第一反应是图形复杂、函数复杂。其实这道题最妙的地方在于它把“城市”定义成了一个递归结构1 级城市是一个 2×2 的街区里面住着 4 户人家N 级城市是把 4 个 N-1 级城市按照特定的旋转和平移方式拼成一个 2×2 的大城区。所以 N 级城市的总边长是 2^N总房屋数是 2^(2N) 4^N。这里要特别注意“边长”和“房屋数”的区别边长是 2 的幂房屋数是 4 的幂。很多代码写错就是因为在计算子城面积的时候习惯性地用了与边长一样的幂次。这种定义方式决定了我们不需要真的把城市画出来。只要能从编号反推坐标递归结构会自动帮我们定位到每一级城市里的相对位置。而“从编号到坐标”的过程正是这题的核心。1.2 房屋编号的内部顺序题目中编号并不是随便排的它遵循着分形结构的连接顺序。以小的一级城市为例如果把 4 个房屋按照编号顺序连接起来会形成一条类似蛇形的连续曲线。我在这篇分享里统一采用如下坐标约定坐标 (x, y) 分别表示“行”和“列”都从 0 开始x 向下增长y 向右增长。那么一级城市中 4 个编号对应的坐标是编号坐标0(0, 0)1(0, 1)2(1, 1)3(1, 0)画成表格就是0 1 3 2你会发现编号 0 → 1 → 2 → 3 正好走了一条从左到右、再从上到下、最后回到左侧的“S”形路线。这条路线就是低一级城市的基本骨架也是理解整个分形递归的关键。注意有的题目版本会把编号改成 1-based也就是房屋编号从 1 到 4^N。此时只要在传参前统一把编号减 1 即可核心递归逻辑完全不用变。2. 从编号到坐标四个区块的落位逻辑2.1 为什么可以按四等份递归假设当前要求的是 N 级城市中编号为 id 的房屋坐标。先看 N-1 级城市的规模边长是 2^(N-1)房屋数是 len × len其中 len 2^(N-1)。N 级城市由 4 个 N-1 级子城拼成。我们可以直接通过一次整数除法确定编号 id 落在哪个子城子城编号 block id / (len × len)子城内部编号 rest id % (len × len)这就是“递推”的入口。只要递归求解 getPos(N-1, rest)得到它在子城内部的坐标 (x, y)再根据 block 对应的旋转和平移规则把内部坐标转换到 N 级城市的全局坐标即可。这个思路的本质是分治大问题拆成小问题小问题的结果再通过变换组合成大问题的结果。递归深度最多 N 层而 N 一般不超过 31所以时间复杂度是 O(N)空间复杂度是 O(N)完全足以应对大多数竞赛数据。2.2 四个区块的变换关系四个子城在全局中的位置分别是左上、右上、右下、左下。它们的变换方式如下区块全局位置坐标变换0左上(x, y) → (y, x)1右上(x, y) → (x, y len)2右下(x, y) → (x len, y len)3左下(x, y) → (2×len - 1 - y, len - 1 - x)这个表是整道题的核心。很多人选择直接背下来但我还是建议理解一下左上和左下两个区块的变换为什么这么写。左上区块要把子城的出口接到右上区块的入口。如果只是平移那么从编号顺序上看就会断层。通过观察一级城市的基本走向可以发现把子城的坐标做“行、列互换”也就是转置刚好能让编号连接处自然衔接。这也就是 case 0 为什么返回 (y, x) 的原因。左下区块更复杂一些。它既要保证编号从上方的右下区块接续下来又要让整个城市最终收尾在左下角。从几何上看它相当于把子城旋转了一下再平移到左下区域。公式里的2×len - 1 - y就是把原本较小的 y 反向映射到下方区域len - 1 - x则保证列方向也落在左半区。如果不理解公式最简单可靠的验证方式就是拿 N1 的子城手动套一遍得到一个 N2 的完整坐标表。下面就是我们这套公式推出来的 4×4 城市布局0 3 4 5 1 2 7 6 14 13 8 9 15 12 11 10你可以沿着编号 0 → 1 → 2 → 3 → … → 15 走一遍会发现它确实是一条连续不断的曲线。这也是我调试时最常用的小技巧用小规模数据生成整个布局表格肉眼看看编号顺序是否连通。3. 核心代码实现3.1 前置准备递归函数需要用到两个关键数值len 2^(N-1)子城的边长area len × len子城的房屋总数对应 4^(N-1)。N 最大到 31 左右时len × len 大约是 2^60已经超过 int 的范围所以这里所有相关变量都应该使用 long long。如果你还在用 int 存边长和面积N 稍微给大一点就会出问题而且这种问题往往不是编译报错而是答案莫名其妙地错。3.2 C 实现直接给出一个可供复制的核心递归函数#include bits/stdc.h using namespace std; typedef long long ll; pairll, ll getPos(int n, ll id) { if (n 0) return {0, 0}; ll len 1LL (n - 1); ll area len * len; int block id / area; ll rest id % area; auto p getPos(n - 1, rest); ll x p.first, y p.second; switch (block) { case 0: return {y, x}; // 左上 case 1: return {x, y len}; // 右上 case 2: return {x len, y len}; // 右下 default: return {2 * len - 1 - y, len - 1 - x}; // 左下 } } int main() { int T; scanf(%d, T); while (T--) { int n; ll a, b; scanf(%d%lld%lld, n, a, b); // 如果题目编号从 1 开始这里统一转成 0-based // a--; b--; ll dx getPos(n, a).first - getPos(n, b).first; ll dy getPos(n, a).second - getPos(n, b).second; long double dist sqrtl((long double)(dx * dx dy * dy)); long long ans llround(dist * 10.0L); printf(%lld\n, ans); } return 0; }代码很短但每一行都值得拆开看。getPos的基本条件是 N0也就是 1×1 的子城编号只能是 0坐标自然是 (0, 0)。这个基本条件保证了递归能够一级一级往上返。主函数里的dx * dx dy * dy在 N31 时仍然在 long long 范围内因为坐标最大是 2^31 量级平方后是 2^62 量级没有超过 9.22×10^18 的上限。如果题目给到 N32那就需要另想办法但竞赛版的分形之城一般不会设计到超过这个范围。3.3 用 Python 快速验证C 适合最终提交但调试阶段用 Python 会更舒服。尤其是生成小规模布局表的时候Python 的递归和元组拆包写起来非常直观。def get_pos(n, pid): if n 0: return (0, 0) L 1 (n - 1) area L * L q, r divmod(pid, area) x, y get_pos(n - 1, r) if q 0: return (y, x) if q 1: return (x, y L) if q 2: return (x L, y L) return (2 * L - 1 - y, L - 1 - x) # 打印 n2 的 4x4 编号布局 n 2 grid [[0] * (1 n) for _ in range(1 n)] for idx in range(1 (2 * n)): x, y get_pos(n, idx) grid[x][y] idx for row in grid: print( .join(f{v:2d} for v in row))这一段可以用来做最基础的 sanity check。正常情况下会输出0 3 4 5 1 2 7 6 14 13 8 9 15 12 11 10如果你改了旋转方向或者区块顺序这个表格就会变得不连续比如出现编号断层或坐标重叠。所以调试时不要只测一两组样例一定要先测这样的“全量布局表”。4. 距离计算与精度陷阱4.1 单位换算题目通常会给一个单位长度。很多版本里相邻两栋房屋之间距离是 10所以最终答案为答案 round(欧氏距离 × 10)例如一级城市中编号 0 和编号 2 的坐标分别为 (0, 0) 和 (1, 1)欧氏距离是 sqrt(2)最终结果就是 sqrt(2)×10 ≈ 14.14四舍五入到 14。这个例子常被当成样例来验证代码。4.2 四舍五入的写法C 里四舍五入可以用llround它会返回 long long。注意不要直接用printf(%.0Lf)因为浮点数打印格式可能因为精度问题出现 0.5 边界上的差异。我习惯这样写long long ans llround(dist * 10.0L);这里dist用sqrtl计算 long double 版本。虽然误差很小但竞赛题对边界往往比较敏感能用高精度就用高精度。4.3 出现负坐标怎么办正常变换公式不会产生负坐标。只要 N 和编号合法四个象限的变换都会把坐标限制在 [0, 2^N - 1] 范围内。如果在调试中发现负坐标或超出边界的坐标几乎可以肯定是递归中block或rest计算错误或者基本条件写错了。5. 常见错误和调试技巧5.1 容易踩的四个坑错误类型具体表现解决方案类型容量不足N 稍大时答案异常坐标、面积、编号全部用 long long子城面积算错使用了 2^n 而不是 4^(n-1)area len × len其中 len 2^(n-1)编号基数不统一输入从 1 开始但没减 1计算前统一转换编号左下变换写错坐标重叠或布局断裂用 n2 的全量布局表检查5.2 用 n2 的布局表快速定位调试递归题不要只盯着单个函数的返回值。最有效的做法是写一个循环把某级城市的全部编号映射成坐标然后按坐标填充到一个二维数组里再打印出来。用我之前给的 Python 脚本跑一次 n2 或 n3一眼就能看出来四个区块的变换对不对。比如常见的错误之一是把左下区块的公式写成return {2 * len - y, len - 1 - x};少了那个-1。结果就是左下区块整体往外偏移一格打印出来的二维表中左下区域会出现边界外的坐标或者出现坐标重叠。这种错误靠样例输入很难发现但靠布局表立刻就能看出来。5.3 递推改迭代如果担心递归深度或者环境对递归栈限制比较严也可以用迭代方式实现。核心思路是把每一层的(block, rest)记录到栈里逐层确定编号归属再反向结算坐标。不过对于 N ≤ 31 的规模递归栈深度完全在安全范围内所以这道题用递归反而是更清晰的选择。迭代版的思路很简单但写起来比递归容易乱。我的建议是先把递归版写对、调通再考虑改成迭代版不要一上来就在迭代的坐标变换里绕晕。6. 一点扩展分形问题的一般套路“分形之城”这道题并不是孤例。很多分形相关题目都遵循同样的模式把大图形拆成若干个小的相似图形然后定义编号与子图形之间的映射关系。解决这类问题的核心永远是两条第一找到“分块编号到子块编号”的递推关系第二找到“子块坐标到全局坐标”的几何变换。只要这两条路打通了剩下的就是代码实现和精度处理。平时遇到这种题不要急着背公式先拿小规模图形把布局表打出来理解一遍编号是怎么连续走的再回到公式里看那些常数到底在做什么。这样即使题目换一个方向旋转你也能根据布局表反推出新的变换公式。我在实际做这题的时候最受益的并不是代码本身而是把“递归”从一种函数调用方式升级成了一种空间划分思路。分形之城的 N 级城市本质上就是一张巨大的递归索引表每次通过编号除以子城面积都能把我们准确地丢进下一层更小的地图里。想清楚这一步剩下的所有旋转和平移就都只是细节了。