超级圣诞树

[题目链接](https://www.nowcoder.com/practice/470d26c9a73e4e17be8cc45cac843423)

思路

这道题要求根据输入的等级 ,输出一棵"超级圣诞树"。关键在于发现它是一个分形递归结构。

先观察样例,找出规律:

等级 1(基础三角形):

  *
 * *
* * *
  *

树冠是 3 行、宽度为 5 的三角形,加上 1 行树干。

等级 2:把等级 1 的树冠居中放在上半部分,下半部分是两个等级 1 的树冠左右并排(中间隔 1 个空格),最后是 2 行树干。

等级 3:把等级 2 的树冠居中放在上半部分,下半部分是两个等级 2 的树冠左右并排,最后是 3 行树干。

归纳出递推关系:

  • 树冠行数:
  • 树冠宽度:(即
  • 树干: 行,每行在正中间放一个 *

构造方法:用一个字符串数组表示当前等级的树冠。从等级 1 开始,逐步递推到等级

  1. 上半部分:把上一级的每一行左右各补 个空格,使其居中。
  2. 下半部分:把上一级的每一行复制两份,中间用 1 个空格连接。

最后输出树冠(每行去掉行尾空格)和树干即可。

代码

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

int main(){
    int n;
    cin >> n;

    vector<string> crown = {"  *  ", " * * ", "* * *"};

    for(int lv = 2; lv <= n; lv++){
        int prev_w = crown[0].size();
        int pad = (prev_w + 1) / 2;
        string sp(pad, ' ');

        vector<string> next;
        for(auto &row : crown)
            next.push_back(sp + row + sp);
        for(auto &row : crown)
            next.push_back(row + " " + row);
        crown = move(next);
    }

    int width = crown[0].size();
    for(auto &row : crown){
        int last = row.size() - 1;
        while(last >= 0 && row[last] == ' ') last--;
        cout << row.substr(0, last + 1) << "\n";
    }
    string trunk(width / 2, ' ');
    trunk += '*';
    for(int i = 0; i < n; i++)
        cout << trunk << "\n";

    return 0;
}
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        List<String> crown = new ArrayList<>(Arrays.asList("  *  ", " * * ", "* * *"));

        for (int lv = 2; lv <= n; lv++) {
            int prevW = crown.get(0).length();
            int pad = (prevW + 1) / 2;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < pad; i++) sb.append(' ');
            String sp = sb.toString();

            List<String> next = new ArrayList<>();
            for (String row : crown)
                next.add(sp + row + sp);
            for (String row : crown)
                next.add(row + " " + row);
            crown = next;
        }

        int width = crown.get(0).length();
        StringBuilder out = new StringBuilder();
        for (String row : crown) {
            int last = row.length() - 1;
            while (last >= 0 && row.charAt(last) == ' ') last--;
            out.append(row, 0, last + 1).append('\n');
        }

        int mid = width / 2;
        StringBuilder t = new StringBuilder();
        for (int i = 0; i < mid; i++) t.append(' ');
        t.append('*');
        String trunk = t.toString();
        for (int i = 0; i < n; i++)
            out.append(trunk).append('\n');

        System.out.print(out);
    }
}
import sys

def solve():
    n = int(input())
    crown = ["  *  ", " * * ", "* * *"]

    for lv in range(2, n + 1):
        prev_w = len(crown[0])
        pad = " " * ((prev_w + 1) // 2)
        top = [pad + row + pad for row in crown]
        bottom = [row + " " + row for row in crown]
        crown = top + bottom

    width = len(crown[0])
    output = []
    for row in crown:
        output.append(row.rstrip())
    trunk = " " * (width // 2) + "*"
    for _ in range(n):
        output.append(trunk)
    sys.stdout.write("\n".join(output) + "\n")

solve()
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

rl.on('line', (line) => {
    const n = parseInt(line.trim());
    let crown = ["  *  ", " * * ", "* * *"];

    for (let lv = 2; lv <= n; lv++) {
        const prevW = crown[0].length;
        const pad = ' '.repeat((prevW + 1) / 2);
        const next = [];
        for (const row of crown)
            next.push(pad + row + pad);
        for (const row of crown)
            next.push(row + " " + row);
        crown = next;
    }

    const width = crown[0].length;
    const lines = crown.map(row => row.trimEnd());
    const trunk = ' '.repeat(Math.floor(width / 2)) + '*';
    for (let i = 0; i < n; i++)
        lines.push(trunk);
    console.log(lines.join('\n'));
    rl.close();
});

复杂度分析

  • 时间复杂度,其中 是最终树冠宽度。每一级递推需要遍历所有行并拼接字符串,总行数为 ,每行长度为
  • 空间复杂度,存储整棵树冠的字符串数组。