南蛮图腾【分治递归】
题目链接:https://www.luogu.org/problem/P1498
题目描述
自从到了南蛮之地,孔明不仅把孟获收拾的服服帖帖,而且还发现了不少少数民族的智慧,他发现少数民族的图腾往往有着一种分形的效果,在得到了酋长的传授后,孔明掌握了不少绘图技术,但唯独不会画他们的图腾,于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙,作为一个好孙子的孙子的孙子的孙子……你能做到吗?
输入格式
每个数据一个数字,表示图腾的大小(此大小非彼大小) n<=10
输出格式
这个大小的图腾
样例输入
2
样例输出
/\ /__\ /\ /\ /__\/__\
样例输入
3
样例输出
/\ /__\ /\ /\ /__\/__\ /\ /\ /__\ /__\ /\ /\ /\ /\ /__\/__\/__\/__\
思路
类型杨辉三角的图形。。。打印图形的大小指的是 2^n ,即n=2时,打印4行;N=3时,打印8行。字符数组要初始化为空格,不然交上去会WA,其余的就是复制打印输出,具体细节看代码
完整代码
#include<bits/stdc++.h> using namespace std; #define LL long long int n; char a[2000][3000]; int main() { cin>>n; int sum=(int)pow(2,n),tot=sum-1;//pow()函数返回值是double类型 for(int i=1;i<=1024;i++)//初始化数组 for(int j=1;j<=2048;j++) a[i][j]=' '; //先储存一个类似循环节的图形,下面复制即可 a[1][1]='/';a[1][2]='\\'; a[2][1]='/';a[2][2]='_'; a[2][3]='_';a[2][4]='\\'; for(int i=2;i<=n;i++) { int kk=(int)pow(2,i-1); for(int j=1;j<=kk;j++) { int kkk=kk*2;//行是列长的两倍 for(int k=1;k<=kkk;k++) { a[j+kk][k]=a[j][k]; a[j+kk][k+kkk]=a[j][k]; } } } int cnt=2;//cnt是每行打印的字符数,每次递增2 for(int i=1;i<=sum;i++) { //先打印前缀空格 for(int j=1;j<=tot;j++) { printf(" "); } tot--;//空格每次减1 //打印字符 for(int j=1;j<=cnt;j++) printf("%c",a[i][j]); cnt+=2; printf("\n"); } return 0; }