[原创]蓝桥杯 2014 B组 C++ 第五题 分形问题
2016-03-15 20:42:54 Tabris_ 阅读数：1566
博客爬取于2020-06-14 22:44:46
以下为正文
版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50899795
蓝桥杯2014第五题
打印图形：
小明在X星球的城堡了发现了如下图形和文字：
Rank=3
Rank=4
Rank=5
题目是填空题 但是代码是自己写的 博客最下面有原代码
分形问题最主要的是找到图形的最基本的点
如POJ 2083 的那个X 基本构成 就是在九个方格里 左上，左下，中间，右上，右下，这5个位置 都有X 而数字每加一个 就把每一个X替换成这个基本的构成
POJ ：http://poj.org/problem?id=2083
这道题个基本构成就不是这么简单 不是每个三角形上的每个点 而是三角形上的一个顶点 其实了解过分形的 看到这句就能解决了 之后就一遍又一遍的递归就好了 但千万注意 你递归的只是三角形的一个顶点(选择这个图形选择上顶点会方便一些） 在打印图形的时候 要把基本三角形的8个点 都打印上
具体如下 数字表示递归操作的层级
画圈的就是所说的基本点 递归应从这里开始
然后找下一级图形的基本点
其实每个上级的基本点都是被递归多次的 毕竟分形就是大的图形中套用小的图形 一直套 直到分形处理结束 这时候就开始赋值了（也就是打印图形的过程）
详情请看代码注释 很详细的哦
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| # include<stdio.h>
# include<string.h>
# include<algorithm>
# include<math.h>
using namespace std;
char a[3000][3000];
void dayin(int car,int x,int y) //核心算法 递归打印
{
if(car==1) //因为递归的只是三角形的定点 所以得把剩下所有的点 都给附上图形
{
a[x][y]='*';
a[x+1][y+1]='*';
a[x+1][y-1]='*';
a[x+2][y+2]='*';
a[x+2][y-2]='*';
a[x+3][y+1]='*';
a[x+3][y-1]='*';
a[x+3][y+3]='*';
a[x+3][y-3]='*';
return ;
}
int s=pow(2,car-2); //这也是高
int e=pow(2,car-2); //这也是宽度
dayin(car-1,x,y);
// dayin(car-1,x+s,y+e); //因为图形是根据三个定点进行分形的 所以 只打印三个定点就好了 剩下的都不需要递归
// dayin(car-1,x+s,y-e);
// dayin(car-1,x+s*2,y+e*2);
// dayin(car-1,x+s*2,y-e*2);
dayin(car-1,x+s*4,y+e*4);
dayin(car-1,x+s*4,y-e*4);
// dayin(car-1,x+s*3,y+e);
// dayin(car-1,x+s*3,y-e);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(a,' ',sizeof(a));
int n;
scanf("%d",&n);
int s=pow(2,n-1); //这是高
int e=pow(2,n); //这是宽度
dayin(n,1,e/2); //打印
for(int i=1;i<=s;i++) //把图形之外的都去掉
a[i][e]='\0';
for(int i=1;i<=s;i++)
printf("%s\n",a[i]+1);
}
}
|
精简版代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| # include<stdio.h>
# include<string.h>
# include<algorithm>
# include<math.h>
using namespace std;
char a[3000][3000];
void dayin(int car,int x,int y)
{
if(car==1)
{
a[x][y]='*';
a[x+1][y+1]='*';
a[x+1][y-1]='*';
a[x+2][y+2]='*';
a[x+2][y-2]='*';
a[x+3][y+1]='*';
a[x+3][y-1]='*';
a[x+3][y+3]='*';
a[x+3][y-3]='*';
return ;
}
int s=pow(2,car-2);
int e=pow(2,car-2);
dayin(car-1,x,y);
dayin(car-1,x+s*4,y+e*4);
dayin(car-1,x+s*4,y-e*4);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(a,' ',sizeof(a));
int n;
scanf("%d",&n);
int s=pow(2,n-1);
int e=pow(2,n);
dayin(n,1,e/2);
for(int i=1;i<=s;i++)
a[i][e]='\0';
for(int i=1;i<=s;i++)
printf("%s\n",a[i]+1);
}
}
|
蓝桥杯的代码(为填空)
其答案为 f(a,rank-1,row,col+w/2)
他的想法和我稍有偏差 但是道理都一样的 这里就不在过多阐述了
但是他的这个代码还是值得读一读的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| # define N 70
void f(char a[][N], int rank, int row, int col)
{
if(rank==1)
{
a[row][col] = '*';
return;
}
int w = 1;
int i;
for(i=0; i<rank-1; i++)
w *= 2;
____________________________________________;
f(a, rank-1, row+w/2, col);
f(a, rank-1, row+w/2, col+w);
}
int main()
{
char a[N][N];
int i,j;
for(i=0; i<N; i++)
for(j=0; j<N; j++)
a[i][j] = ' ';
f(a,6,0,0);
for(i=0; i<N; i++)
{
for(j=0; j<N; j++)
printf("%c",a[i][j]);
printf("\n");
}
return 0;
}
|
