太cai了,只能做做氵题了🙄
南蛮图腾
题目背景
自从到了南蛮之地,孔明不仅把孟获收拾的服服帖帖,而且还发现了不少少数民族的智慧,他发现少数民族的图腾往往有着一种分形的效果,在得到了酋长的传授后,孔明掌握了不少绘图技术,但唯独不会画他们的图腾,于是他找上了你的爷爷的爷爷的爷爷的爷爷……帮忙,作为一个好孙子的孙子的孙子的孙子……你能做到吗?
题目描述
给定一个正整数 $n$,参考输出样例,输出图形。
输入格式
每个数据输入一个正整数 $n$,表示图腾的大小(此大小非彼大小)
输出格式
这个大小的图腾
样例 #1
样例输入 #1
2
样例输出 #1
/\
/__\
/\ /\
/__\/__\
样例 #2
样例输入 #2
3
样例输出 #2
/\
/__\
/\ /\
/__\/__\
/\ /\
/__\ /__\
/\ /\ /\ /\
/__\/__\/__\/__\
提示
数据保证,$1 \leq n \leq 10$。
方法一
数据很小($1 \leq n \leq 10$)
直接暴力递归。
一个大小为n的图形是由三个大小为n-1的图形组成的($n \ne 1$)
因此通过层层递归,直到 $n = 1$ ,存入二维数组中。
$code:$
#include<bits/stdc++.h>
using namespace std;
int n;
char mp[1030][2050]; //map关键词
void draw(int x, int y, int deep){ //deep表示所需图形的大小
if(deep == 1){ //画出n=1的基本图形
mp[x][y]='/';
mp[x][y + 1]='\\';
mp[x + 1][y - 1] = '/';
mp[x + 1][y] = '_';
mp[x + 1][y + 1] = '_';
mp[x + 1][y + 2] = '\\'; //向右的划线有特殊的含义
return;
}
draw(x, y, deep - 1);
draw(x + pow(2, deep - 1), y - pow(2, deep - 1), deep - 1);
draw(x + pow(2, deep - 1), y + pow(2, deep - 1), deep - 1);
}
int main(){
cin >> n;
for(int i = 1; i <= pow(2, n); i ++){ //初始化
for(int j = 1; j <= pow(2, n + 1); j ++) mp[i][j] = ' ';
}
draw(1, pow(2, n), n);
for(int i = 1; i <= pow(2, n); i ++){ //输出
for(int j = 1; j <= pow(2, n + 1); j ++){
cout << mp[i][j];
}
cout << endl;
}
return 0;
}
方法二
用分治也很简单, 每次向下复制一下,向右复制一下,再向上复制一下。
/\
/__\
/\ /\
/__\/__\
向下和向右:(顺便把原本的清掉)
/\ /\
/__\ /__\
/\ /\ /\ /\
/__\/__\/__\/__\
再向上:
/\
/__\
/\ /\
/__\/__\
/\ /\
/__\ /__\
/\ /\ /\ /\
/__\/__\/__\/__\
$code:$
#include<bits/stdc++.h>
using namespace std;
int n;
char mp[3000][3000];
int h = 2, w = 4; //h是高,w是宽
int main(){
cin >> n;
memset(mp, ' ', sizeof(mp)); //也可以用刚刚的for循环
mp[1][1] = mp[1][4] = ' ';
mp[1][2] = mp[2][1] = '/';
mp[1][3] = mp[2][4] = '\\';//向右的划线有特殊的含义
mp[2][2] = mp[2][3] = '_';
for(int i = 1; i < n; i ++){
for(int j = 1; j <= h; j ++){
for(int k = 1; k <= w; k++){
mp[j + h][k] = mp[j + h][k + w] = mp[j][k];
mp[j][k] = ' '; //把上面的清掉
}
}
//向上
for(int j = 1; j <= h; j ++){
for(int k = 1; k <= w; k ++){
mp[j][k + w / 2] = mp[j + h][k];
}
}
w *= 2, h *= 2;
//刷新完成一次
}
for(int i = 1; i <= h; i ++){
for(int j = 1; j <= w; j ++){
cout << mp[i][j];
}
cout << endl;
}
return 0;
}