「Fractal」分形

题目描述

$n$ 阶分形：1 阶为 X， $n$ 阶由 5 个 $n-1$ 阶分形按十字排列（左上/右上/左下/右下 4 个 + 中上空格），输入多组 $n$ （ $-1$ 终止），每组输出 $3^{n-1}$ 行图案，组间 - 分隔。

思路

递归构造： $n$ 阶图案尺寸为 $3^{n-1}$ ，由 $n-1$ 阶图案复制到四个角落、其余留空，递归到 1 阶填 X，直接按行输出即可。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 10:40
# update_at: 2026-10-01 10:40

import sys
from functools import cache


@cache
def fractal(n: int) -> tuple[str, ...]:
    """回答：n 级盒子分形的图案长什么样（每一行是一个定宽字符串）。

    B(n) 的五个位置各放一份 B(n-1)：左上、右上、正中、左下、右下。
    每行始终补齐到整图宽度 size，拼接下一级时副本才不会错位；
    行尾空格留到输出前再去掉。`@cache` 让 7 级图案只算一次，各级复用。
    """
    if n == 1:
        return ("X",)
    size = 3 ** (n - 1)  # B(n) 的边长：每升一级扩大 3 倍
    half = size // 3     # B(n-1) 的边长；也是上/中/下三带的高度与各副本的平移量
    unit = fractal(n - 1)
    gap = " " * half     # 上/下带里左右两份之间的空白，恰好也是 half 宽

    rows = []
    for row in unit:  # 上带：左右两份 B(n-1)
        rows.append(row + gap + row)
    for row in unit:  # 中带：只有一份 B(n-1)，水平居中
        rows.append(gap + row + gap)
    for row in unit:  # 下带：左右两份 B(n-1)
        rows.append(row + gap + row)
    return tuple(rows)


def solve() -> None:
    for token in sys.stdin.read().split():
        n = int(token)
        if n == -1:  # 终止标记
            break
        print("\n".join(row.rstrip() for row in fractal(n)))
        print("-")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:21
 * update_at: 2026-10-06 11:21
 */

// 盒子分形：B(n) 由五份 B(n-1) 放在左上、右上、正中、左下、右下构成，
// 边长为 3^(n-1)，n <= 7 时边长最大 729，直接用二维数组画出所有级别即可。

#include <cstdio>

typedef long long ll;

const int MAXN = 7;              // 最大级别
const int MAXS = 729;            // 3^6 = 729，最大边长

char f[MAXN + 1][MAXS][MAXS];    // f[n][r][c] = 第 n 级分形第 r 行第 c 列的字符（'X' 或 ' '）
ll len[MAXN + 1];                // len[n] = 第 n 级分形的边长 3^(n-1)

int main() {
    // 初始化第 1 级：只有一个 X
    len[1] = 1;
    f[1][0][0] = 'X';

    // 由第 n-1 级逐级构造第 n 级：每个 X 复制到五个位置
    for (int n = 2; n <= MAXN; n++) {
        ll half = len[n - 1];    // 上一级的边长，也是各副本的平移量
        len[n] = half * 3;
        for (ll r = 0; r < half; r++) {
            for (ll c = 0; c < half; c++) {
                if (f[n - 1][r][c] != 'X') continue;
                f[n][r][c] = 'X';                       // 左上
                f[n][r][c + 2 * half] = 'X';            // 右上
                f[n][r + half][c + half] = 'X';         // 正中
                f[n][r + 2 * half][c] = 'X';            // 左下
                f[n][r + 2 * half][c + 2 * half] = 'X'; // 右下
            }
        }
    }

    int n;
    while (scanf("%d", &n) == 1) {
        if (n == -1) break;      // 终止标记
        ll size = len[n];
        for (ll r = 0; r < size; r++) {
            // 找本行最后一个 X，行尾空格不输出
            ll last = -1;
            for (ll c = size - 1; c >= 0; c--) {
                if (f[n][r][c] == 'X') { last = c; break; }
            }
            for (ll c = 0; c <= last; c++) {
                char ch = f[n][r][c];
                if (ch != 'X') ch = ' ';   // 数组未写过的位置按空格输出
                putchar(ch);
            }
            putchar('\n');
        }
        printf("-\n");           // 每组输出后一个短划线
    }
    return 0;
}

「Fractal」 分形

目录

题目描述

思路

参考代码