关于算法:分形之城递归超典型例题还没明白手把手画给你看

援用自 Acwing，原题链接：

98. 分形之城

题目
题解
代码

<p> 城市的布局在城市建设中是个大问题。</p>
<p> 可怜的是，很多城市在开始建设的时候并没有很好的布局，城市规模扩充之后布局不合理的问题就开始浮现。</p>
<p> 而这座名为 Fractal 的城市构想了这样的一个布局计划，如下图所示：</p>

<p> 当城区规模扩充之后，Fractal 的解决方案是把和原来城区构造一样的区域依照图中的形式建设在城市四周，晋升城市的等级。</p>
<p> 对于任意等级的城市，咱们把正方形街区从左上角开始依照路线标号。</p>

尽管这个计划很烂，Fractal 布局部门的人员还是想晓得，如果城市倒退到了等级 $N$，编号为 $A$ 和 $B$ 的两个街区的直线间隔是多少。

街区的间隔指的是街区的中心点之间的间隔，每个街区都是边长为 $10$ 米的正方形。

<h4> 输出格局 </h4>
第一行输出正整数 $n$，示意测试数据的数目。

以下 $n$ 行，输出 $n$ 组测试数据，每组一行。

每组数据包含三个整数 $N, A, B$，示意城市等级以及两个街区的编号，整数之间用空格隔开。

一共输入 $n$ 行数据，每行对应一组测试数据的输入后果，后果四舍五入到整数。

$1 \le N \le 31$
$1 \le A,B \le 2^{2N}$
$1 \le n \le 1000$

10 
30 
50

这有啥不明确的，手把手画进去！

首先明确，为啥能用递归：

咱们想计算 n 等级的坐标，晓得 n-1 等级的坐标就行

而后思考怎么递归？

咱们首先规定，每个等级的坐标系原点是独特的，如下图。

而后咱们从非凡到个别，演绎推法则：

等级 1 这个块块，如果放到等级 2 里，有四种状况要探讨
等级 1 放到等级 2 的左上象限，则相当于顺时针旋转了 90°，并且还要沿 y 轴翻转（为什么要沿 y 轴翻转呢？因为你留神每个编号的地位，不翻转，形态尽管对上了，然而编号程序没对上）
等级 1 放到等级 2 的右上象限，则不必转
等级 1 放到等级 2 的右下象限，则不必转
等级 1 放到等级 2 的左下象限，则相当于逆时针旋转了 90°，并且还要沿 y 轴翻转

转完了，因为咱们当初从等级 1 到等级 2 了，因而坐标系原点也挪动了，所以要在等级 1 的原有坐标根底上进行平移。

好了，我给你画个图，你就懂了。

而后你再去看代码。

这里补充一点数学知识：

对于点 (x, y)，沿原点顺时针旋转 90°，将变为 (y, -x)
对于点 (x, y)，沿原点逆时针旋转 90°，将变为 (-y, x)
对于点 (x, y)，以 y 轴为对称轴翻转将变为 (-x, y)

#include <iostream>
#include <cstring>
#include <cmath>  // sqrt
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

PLL calc(LL n, LL m)
{
    /*
    * n: 等级
    * m: 坐标，从 0 开始计数
    */
    if (n == 0) return {0, 0};
    LL len = 1ll << (n - 1);  // 2^{n-1} 本等级内象限的边长 /2
    LL cnt = 1ll << (2 * n - 2);  // 4^{n-1} 本等级内象限容量
    PLL pos = calc(n - 1, m % cnt);  // 上一等级的坐标信息
    LL x = pos.first, y = pos.second;
    int z = m / cnt;  // 处于哪个象限
    // 左上象限顺转 90°（y,-x）沿 y 对称（-y,-x）更换原点（-y-len,-x+len）if (z == 0)
        return {- y - len, - x + len};
    // 右上象限更换原点（x+len,y+len）else if (z == 1)
        return {x + len, y + len};
    // 右下象限更换原点（x+len,y-len）else if (z == 2)
        return {x + len, y - len};
    // 左下象限逆转 90°（-y,x）沿 y 对称（y,x）更换原点（y-len,x-len）return {y - len, x - len};
}

int main()
{
    int N;
    cin >> N;
    while (N --)
    {
        LL n, m1, m2;
        cin >> n >> m1 >> m2;
        PLL pos1 = calc(n, m1 - 1);
        PLL pos2 = calc(n, m2 - 1);

        double delta_x = (double) (pos1.first - pos2.first);
        double delta_y = (double) (pos1.second - pos2.second);
        // 等级 1 中 len 是单位长度，且示意象限的一半长即为 10 / 2 = 5
        printf("%.0lf\n", sqrt(delta_x * delta_x + delta_y * delta_y) * 5);
    }
}

题目

题解

代码