题目描述 自从到了南中之地（今四川南部、云南东北部和贵州西北部一带），孔明不仅把孟获收拾得服服帖帖，而且还发现了许多少数民族的智慧。 他发现少数民族的图腾往往有一种分形的效果，在得到了酋长的传授后，孔明掌握了许多绘图技术，但唯独不会画他们的图腾。 请你根据样例找出图腾的规律。 输入 每个数据一个数字，表示图腾的大小(此大小非彼大小)，n≤10.。 输出 这个大小的图腾。

题目描述

自从到了南中之地（今四川南部、云南东北部和贵州西北部一带），孔明不仅把孟获收拾得服服帖帖，而且还发现了许多少数民族的智慧。

他发现少数民族的图腾往往有一种分形的效果，在得到了酋长的传授后，孔明掌握了许多绘图技术，但唯独不会画他们的图腾。

请你根据样例找出图腾的规律。

输入

每个数据一个数字，表示图腾的大小(此大小非彼大小)，n≤10。

输出

这个大小的图腾。

样例输入

2

样例输出

　　*　　
　* *　
* * *
　* *
　　*

样例输入

3

样例输出

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

算法1

(递归) $O(n^2)$

先看样例2的输出，我们可以发现一个规律：$n$级图腾由$2n-1$个$n-1$级图腾组成，其中最中间的$n-1$级图腾被替换为星号。

那么我们可以先递归地画出$n-1$级图腾，然后根据上述规律画出整个$n$级图腾。

时间复杂度

每次递归需要画出$2n-1$个图腾，因此总时间复杂度为$O((2n-1)^2)$，即$O(n^2)$。

参考文献

无

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 500;

char g[N][N];

void dfs(int x, int y, int n)//画n级图腾的起点是g[x][y]
{
if (n == 1)
{
g[x][y] = '*';
return;
}

dfs(x + (1 << n - 2), y, n - 1);//中间的图腾
for (int i = 0; i < n - 1; i++)//上下两个三角形
{
g[x][y + i] = g[x + (1 << n - 2)][y + i] = '*';//上半部分
g[x + (1 << n - 1) - 1][y + i] = g[x + (1 << n - 2)][y + n - 2 + i] = '*';//下半部分
}

dfs(x, y + (1 << n - 2), n - 1);//左半部分
dfs(x + (1 << n - 1), y + (1 << n - 2), n - 1);//右半部分
}

int main()
{
int n;
while (cin >> n)
{
memset(g, ' ', sizeof g);//初始化为空格
dfs(0, 0, n);
for (int i = 0; i < 1 << n - 1; i++)//输出
{
for (int j = 0; j < 1 << n - 1; j++)
cout << g[i][j];
cout << endl;
}
}
return 0;
}