算法基础算法

分形与分治

字数统计: 3.1k字   |   阅读时长: 12分
, ,

摘要: 分形问题与分治算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

什么是分形

分形，具有以非整数维形式充填空间的形态特征。(关于非整数维的含义和理论，可以看后面介绍的资料)。通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。

分形是一个数学术语，也是一套以分形特征为研究主题的数学理论。分形理论既是非线性科学的前沿和重要分支，是研究一类现象特征的新的数学分科，相对于其几何形态，它与微分方程与动力系统理论的联系更为显著。分形的自相似特征可以是统计自相似，构成分形也不限于几何形式，时间过程也可以，故而与鞅论关系密切。

分形几何是一门以不规则几何形态为研究对象的几何学。由于不规则现象在自然界普遍存在，因此分形几何学又被称为描述大自然的几何学。分形几何学建立以后，很快就引起了各个学科领域的关注。不仅在理论上，而且在实用上分形几何都具有重要价值。

如果想要系统学习分形的理论，可以看 Kenneth J. Falconer 在 1989 年写的《分形几何-数学基础及应用》，其中包含分形及分形几何的一般理论、分形的应用这两部分。理论部分包括维数的各种不同的概念及计算维数的方法、分形的几何性质；应用部分包括自相似集、自仿射集、函数的图、动力系统、Julia集、随机分型以及一些物理应用。

此外分形在金融中也是一个流派，这方面《市场的错误行为-风险-破产与收益的分形观点》这本书是最经典的。

分治与分形

分治法的思想是要解决一个整体问题，首先将整体问题分成若干个部分，每个部分构成一个子问题，其中每个子问题的描述与原问题一模一样，仅仅是问题规模缩小。当问题规模缩小到某个值的时候，就可以直接解决。

基于上面的思想，分治法的处理流程就是在每一轮中，如果问题可以直接解决，就解决，如果不能直接解决，就按特定方式分成若干个规模更小的子问题，先解决子问题，然后再整合子问题的结果，形成当前问题的结果。

分治法的这种处理流程与分形的构造流程非常像，只是理论上分形可以无限地进行下去，而分治进行到问题规模小到可以直接解决的时候就停止了。

因此如果限制分形的轮数，一些比较简单的分形问题可以用分治法解决。

用分治法解决一些分形的问题

(1) 分形

现在，定义“盒子分形”如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
一级盒子分形：
  X

二级盒子分形：

   X X
    X
   X X
如果用 B(n−1) 代表第 n−1 级盒子分形，那么第 n 级盒子分形即为：

  B(n - 1)        B(n - 1)

          B(n - 1)

  B(n - 1)        B(n - 1)

你的任务是绘制一个 n 级的盒子分形。

1
2
3
4
5
6
7
8
9
10
11
12
13
输入格式
输入包含几个测试用例。

输入的每一行包含一个不大于 7 的正整数 n，代表要输出的盒子分形的等级。

输入的最后一行为 −1，代表输入结束。

输出格式
对于每个测试用例，使用 X 符号输出对应等级的盒子分形。

请注意 X 是一个大写字母。

每个测试用例后输出一个独立一行的短划线。

算法: 分治

当分形轮数 n 为 1 的时候，可以直接解决，直接打印一个 X 就好。

当分形轮数 n 大于 1 的时候，就通过题目中对分形定义的方式，分解为 5 个子问题，每个子问题的分形轮数都变为 n - 1。然后分别解决各个 n - 1 的子问题即可。

在解决分形轮数 n - 1 的子问题时，还涉及到一个位置的信息，也就是打印的内容具体打印在什么位置，这个信息需要在进入子问题时带着。

下面我推导一下这个传入子问题的位置信息需要怎样得出。

对于分形轮数为 n 的问题，它的打印范围的总宽度和总高度为 $3^{n-1}$。分解后的 5 个分形轮数 n - 1 的子问题，打印范围的总宽度和总高度变均为 $3^{n-2}$，区别仅在于起始位置，因此我们需要传给子问题的信息就是起始位置 (x, y)。

这五个子问题的起始位置分别为：

我们记 solve(N, x, y) 表示要解决的是分形轮数为 N，左上角位置为 (x, y) 的问题。那么五个子问题分别为

1
2
3
4
5
solve(N - 1, x, y)
solve(N - 1, x, y + 2 * pow(3, N-2))
solve(N - 1, x + pow(3, N-2), y + pow(3, N-2))
solve(N - 1, x + 2 * pow(3, N-2), y)
solve(N - 1, x + 2 * pow(3, N-2), y + 2 * pow(3, N-2))

因此我们就可以写出以下分治算法，其中 board 为二维数组 vector<string>，board[i][j] 可以取空格或 X，表示最终打印的信息。

1
2
3
4
5
分解: 对于 (N, x, y)，分别解决上述的 5 个子问题

解决: 如果 N = 1，则在 board[x][y] 位置赋值为 X

合并: 合并阶段没有操作

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cmath>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve(const int N, const int x, const int y, vector<string>& board)
{
    if(N == 1)
    {
        board[x][y] = 'X';
        return;
    }
    solve(N - 1, x, y, board);
    solve(N - 1, x, y + 2 * pow(3, N - 2), board);
    solve(N - 1, x + pow(3, N - 2), y + pow(3, N - 2), board);
    solve(N - 1, x + 2 * pow(3, N - 2), y, board);
    solve(N - 1, x + 2 * pow(3, N - 2), y + 2 * pow(3, N - 2), board);
}

int main()
{
    int N;
    vector<string> board;
    while((cin >> N) && N != -1)
    {
        int len = (int)pow(3, N - 1);
        board.assign(len, string(len, ' '));
        solve(N, 0, 0, board);
        for(int i = 0; i < len; ++i)
            cout << board[i] << endl;
        cout << "-" << endl;
    }
}

(2) 98. 分形之城

如图，对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入格式
第一行输入正整数 n，表示测试数据的数目。

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

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

输出格式
一共输出 n 行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围
1<=N<=31,
1<=A,B<=22N,
1<=n<=1000

输入样例：
3
1 1 2
2 16 1
3 4 33
输出样例：
10
30
50

算法: 分治

当分形轮数 N 为 1 时，城市范围的长和宽为 2 * 2，当分形轮数 N 大于 1 时，城市范围的长和宽为 pow(2, N) * pow(2, N)。

本题核心要解决的是给定分形轮数 N，和某个点的编号 M，求该点在长和宽为 pow(2, N) * pow(2, N) 的图中的坐标 (x, y)。

当分形轮数 N 为 1 时，可以直接解决，对应关系如下

1
2
3
4
M = 1 -> (0, 0)
M = 2 -> (0, 1)
M = 3 -> (1, 1)
M = 4 -> (1, 0)

当分型轮数 N 大于 1 时，就通过题目中对分形定义的方式，分解为 4 个子问题，每个子问题的分形轮数都变为 N - 1。

如果不考虑分形定义中的旋转的问题，这四个子问题其实就是一个子问题，因此我们只需要解决一个分形轮数 N - 1 的子问题即可。只是根据 M 的值，进入的子问题可能是左上，左下，右上，右下中的一个，具体进入了哪个，对旋转的处理有影响。

因此在解决分形轮数 N - 1 的子问题时，还涉及到一个旋转的信息。按照题目中对分形的定义，当从轮数为 N 的问题进入轮数为 N - 1 的问题时:

  • 如果进入的是右上或右下，则解决分形轮数 N - 1 的问题后直接返回坐标 (x, y) 即可。
  • 如果进入的是左上，则解决分形轮数 N - 1 的问题，得到坐标 (x, y) 后，还需要顺时针旋转再水平翻转，然后再将坐标输出，最终为 (y, x)。
  • 如果进入的是左下，则解决分形轮数 N - 1 的问题，得到坐标 (x, y) 后，还需要逆时针旋转再水平翻转，然后再将坐标输出，最终为 (len - 1 - y, len - 1 - x)，其中 len = pow(2, N - 1)。

旋转问题解决了，还需要解决的是当从分形轮数 N 的问题进入分形轮数 N - 1 的问题时，M 如何变化。按照分型定义，分形轮数 N 的问题，一共有 pow(2, N) * pow(2, N) = pow(2, 2 * N) 个点，进入子问题后，有 pow(2, 2 * N - 2) 个点。因此不论进入四个角的哪一个，M 都会变为 M % pow(2, 2 * N - 2)

我们记 solve(N, M) 表示要解决的是分形轮数为 N，编号为 M 点的坐标。要解决的子问题为

1
solve(N - 1, M % pow(2, 2N - 2))

因此我们就可以写出以下分治算法

1
2
3
4
5
分解: 对于 (N, M), 解决 (N - 1, M % pow(2, 2 * N - 2)) 这个子问题

解决: 如果 N = 1，根据规则直接返回 (x, y)

合并: 根据 M 得到旋转信息，执行相应的旋转，然后再输出 (x, y)

当通过编号得到坐标这个问题解决后，给定两个点的编号 A, B，我们就可以求出距离了，过程如下。

1
2
3
x1, y1 = solve(N, A)
x2, y2 = solve(N, B)
ans = 10 * (abs(x1 - x2) + abs(y1 - y2))

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cmath>

using namespace std;

using ll = long long;

struct Point
{
    ll x, y;
    Point(){}
    Point(ll x, ll y):x(x),y(y){}
};

double dist(const Point& p1, const Point& p2)
{
    double ans  = (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    return sqrt(ans);
}

Point solve(const ll N, const ll M)
{
    if(N == 1)
    {
        if(M == 0)
            return Point(0, 0);
        else if(M == 1)
            return Point(0, 1);
        else if(M == 2)
            return Point(1, 1);
        else
            return Point(1, 0);
    }
    ll len = pow(2, N - 1); // 一个角的边长
    ll sub_cnt = len * len; // 一个角的点个数
    Point p = solve(N - 1, M % sub_cnt);
    Point ans;
    if(M < sub_cnt)
    {
        ans.x = p.y;
        ans.y = p.x;
    }
    else if(M < sub_cnt * 2)
    {
        ans.x = p.x;
        ans.y = p.y;
        ans.y += len;
    }
    else if(M < sub_cnt * 3)
    {
        ans.x = p.x;
        ans.y = p.y;
        ans.x += len;
        ans.y += len;
    }
    else
    {
        ans.x = (len - 1 - p.y);
        ans.y = (len - 1 - p.x);
        ans.x += len;
    }
    return ans;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        ll N, A, B;
        cin >> N >> A >> B;
        Point p1 = solve(N, A - 1);
        Point p2 = solve(N, B - 1);
        ll ans = round(10 * dist(p1, p2));
        cout << ans << endl;
    }
}
Share