超级圣诞树
[题目链接](https://www.nowcoder.com/practice/470d26c9a73e4e17be8cc45cac843423)
思路
这道题要求根据输入的等级 ,输出一棵"超级圣诞树"。关键在于发现它是一个分形递归结构。
先观察样例,找出规律:
等级 1(基础三角形):
*
* *
* * *
*
树冠是 3 行、宽度为 5 的三角形,加上 1 行树干。
等级 2:把等级 1 的树冠居中放在上半部分,下半部分是两个等级 1 的树冠左右并排(中间隔 1 个空格),最后是 2 行树干。
等级 3:把等级 2 的树冠居中放在上半部分,下半部分是两个等级 2 的树冠左右并排,最后是 3 行树干。
归纳出递推关系:
- 树冠行数:
- 树冠宽度:
(即
)
- 树干:
行,每行在正中间放一个
*
构造方法:用一个字符串数组表示当前等级的树冠。从等级 1 开始,逐步递推到等级 :
- 上半部分:把上一级的每一行左右各补
个空格,使其居中。
- 下半部分:把上一级的每一行复制两份,中间用 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();
});
复杂度分析
- 时间复杂度:
,其中
是最终树冠宽度。每一级递推需要遍历所有行并拼接字符串,总行数为
,每行长度为
。
- 空间复杂度:
,存储整棵树冠的字符串数组。

京公网安备 11010502036488号