解题思路

题目要求按照给定的整数 n，打印出一个“分形”的圣诞树图案。 观察给出的 C++ 代码可以发现，这并不是简单的等腰三角形堆叠，而是类似 Sierpinski 三角形 的分形结构： 树冠高度每加 1 级，整体高度、宽度都扩大 2 倍，并在“左下”“右下”分别复制上一层的图案。

具体做法：

1. 用一个二维字符数组作为画布，先全部填空格 ' '。

   • 行数 rows = 3 * 2^(n-1)
   • 列数 cols = 3 * 2^n
   • 树顶在最中间列 top = 3 * 2^(n-1) - 1

2. 先在画布中间位置画出最小的一棵树（高度为 3 的小三角）：

   • 第 0 行：(0, top) 一个 *
   • 第 1 行：(1, top-1) 和 (1, top+1)
   • 第 2 行：(2, top-2)、(2, top)、(2, top+2)

3. 通过“扩展步骤 step = 1..n-1”构造更大的分形：

   • 当前要扩展的边长 range = 3 * 2^(step-1)

   • 在画布上，找到前一层高度范围 [0, range-1] 内的所有 *： 对于每个 * 在 (i, j) 位置：

     • 在 (i + range, j - range) 画一个 *（左下复制）
     • 在 (i + range, j + range) 画一个 *（右下复制）

   • 这样每一层都把上一层“复制”到左下和右下，形成指数级扩展的分形结构。

4. 树干的绘制：

   • 树干高度为 n 行，列位置与树顶相同。
   • 每行输出 top 个空格，再输出一个 *。

最终输出二维数组中的所有字符即可得到图案。

本质上是一个在二维数组上进行的 分形构造 / 迭代复制算法，不需要递归，直接用循环实现即可。

复杂度分析

设 n 的上限不大（例如题目常见约束 1 ≤ n ≤ 8），画布大小为：

• 行数：rows = 3 * 2^(n-1)
• 列数：cols = 3 * 2^n

1. 填充画布：

   • 时间复杂度：O(rows * cols)

2. 每一层扩展：

   • 第 step 层时，range = 3 * 2^(step-1)
   • 遍历区域大小约 range * 2*range = O(range^2)
   • 累加各层得到时间复杂度为： O(3^2 * (2^(2*(n-1))) ) = O(4^n)，与画布大小同阶。

3. 总体复杂度：

   • 时间复杂度：O(4^n)
   • 空间复杂度：O(rows * cols) = O(4^n)

在题目给定的 n 范围下，该复杂度完全可接受。

代码实现

Python

import sys

# 计算 2 的幂
def pow2(x: int) -> int:
    return 1 << x

# 构建树冠，返回(画布、行数、列数、树顶列号)
def build_tree(n: int):
    rows = 3 * pow2(n - 1)
    cols = 3 * pow2(n)
    top = 3 * pow2(n - 1) - 1

    # 初始化画布，全是空格
    g = [[' ' for _ in range(cols)] for _ in range(rows)]

    # 画最小的高度为 3 的小树
    g[0][top] = '*'
    g[1][top - 1] = '*'
    g[1][top + 1] = '*'
    g[2][top - 2] = '*'
    g[2][top] = '*'
    g[2][top + 2] = '*'

    # 按层扩展分形结构
    for step in range(1, n):
        rang = 3 * pow2(step - 1)
        for i in range(rang):  # 只在上一层的高度范围内找 '*'
            for j in range(top - rang + 1, top + rang):
                if g[i][j] == '*':
                    # 左下复制
                    g[i + rang][j - rang] = '*'
                    # 右下复制
                    g[i + rang][j + rang] = '*'

    return g, rows, cols, top


def main():
    data = sys.stdin.read().strip()
    if not data:
        return
    n = int(data)

    g, rows, cols, top = build_tree(n)

    out_lines = []

    # 输出树冠
    for i in range(rows):
        # 去掉行尾多余空格，避免无意义宽输出
        out_lines.append(''.join(g[i]).rstrip())

    # 输出树干，高度为 n
    for _ in range(n):
        out_lines.append(' ' * top + '*')

    sys.stdout.write('\n'.join(out_lines) + '\n')


if __name__ == "__main__":
    main()

Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {

    // 计算 2 的幂
    static int pow2(int x) {
        return 1 << x;
    }

    // 构建树冠，返回字符画布
    static char[][] buildTree(int n, int[] info) {
        int rows = 3 * pow2(n - 1);
        int cols = 3 * pow2(n);
        int top = 3 * pow2(n - 1) - 1;

        info[0] = rows;
        info[1] = cols;
        info[2] = top;

        char[][] g = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            Arrays.fill(g[i], ' ');
        }

        // 画最小的小树
        g[0][top] = '*';
        g[1][top - 1] = '*';
        g[1][top + 1] = '*';
        g[2][top - 2] = '*';
        g[2][top] = '*';
        g[2][top + 2] = '*';

        // 分形扩展
        for (int step = 1; step < n; step++) {
            int range = 3 * pow2(step - 1);
            for (int i = 0; i < range; i++) {
                for (int j = top - range + 1; j < top + range; j++) {
                    if (g[i][j] == '*') {
                        g[i + range][j - range] = '*';
                        g[i + range][j + range] = '*';
                    }
                }
            }
        }

        return g;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (!sc.hasNextInt()) {
            return;
        }
        int n = sc.nextInt();

        int[] info = new int[3]; // rows, cols, top
        char[][] g = buildTree(n, info);
        int rows = info[0];
        int cols = info[1];
        int top = info[2];

        StringBuilder sb = new StringBuilder();

        // 输出树冠
        for (int i = 0; i < rows; i++) {
            int last = cols - 1;
            // 去掉行末多余空格
            while (last >= 0 && g[i][last] == ' ') last--;
            if (last < 0) {
                sb.append('\n');
                continue;
            }
            for (int j = 0; j <= last; j++) {
                sb.append(g[i][j]);
            }
            sb.append('\n');
        }

        // 输出树干，高度为 n
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < top; j++) {
                sb.append(' ');
            }
            sb.append('*').append('\n');
        }

        System.out.print(sb.toString());
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

// 计算 2 的幂
int pow2(int x) {
    return 1 << x;
}

// 构造树冠，返回 rows, cols, top，并把结果写入 g
void buildTree(int n, vector<string> &g, int &rows, int &cols, int &top) {
    rows = 3 * pow2(n - 1);
    cols = 3 * pow2(n);
    top = 3 * pow2(n - 1) - 1;

    // 初始化画布
    g.assign(rows, string(cols, ' '));

    // 画最小的小树
    g[0][top] = '*';
    g[1][top - 1] = '*';
    g[1][top + 1] = '*';
    g[2][top - 2] = '*';
    g[2][top] = '*';
    g[2][top + 2] = '*';

    // 分形扩展
    for (int step = 1; step < n; ++step) {
        int range = 3 * pow2(step - 1);
        for (int i = 0; i < range; ++i) {
            for (int j = top - range + 1; j < top + range; ++j) {
                if (g[i][j] == '*') {
                    g[i + range][j - range] = '*'; // 左下复制
                    g[i + range][j + range] = '*'; // 右下复制
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    vector<string> g;
    int rows, cols, top;
    buildTree(n, g, rows, cols, top);

    // 输出树冠
    for (int i = 0; i < rows; ++i) {
        int last = cols - 1;
        // 去掉行末多余空格
        while (last >= 0 && g[i][last] == ' ') --last;
        if (last < 0) {
            cout << '\n';
            continue;
        }
        for (int j = 0; j <= last; ++j) cout << g[i][j];
        cout << '\n';
    }

    // 输出树干，高度为 n
    for (int k = 0; k < n; ++k) {
        for (int j = 0; j < top; ++j) cout << ' ';
        cout << "*\n";
    }

    return 0;
}

题目内容

今天是圣诞节，牛牛要打印一个漂亮的圣诞树送给想象中的女朋友，请你帮助他实现梦想。

输入描述

输入圣诞树的大小 $n$

$1≤n≤8$

输出描述

输出对应的圣诞树

样例1

输入

1

输出

  *
 * *
* * *
  *

样例2

输入

2

输出

     *
    * *
  *     *
 * *   * *
* * * * * *
     *
     *