AOJ 716.谢尔宾斯基三角形

194

题目



Time Limit: 3000 ms
Case Time Limit: 3000 ms
Memory Limit: 128 MB
Total Submission: 116
Submission Accepted: 35

Description  


谢尔宾斯基三角形(Sierpinski triangle)是一种分形,由波兰数学家谢尔宾斯基在1915年提出。下面的图片就是谢尔宾斯基三角形的一个简单例子。

现在,Roll想在自己的电脑中画出这个图形,他要求不高,只要实现一个控制台版本就好,也不需要行首的空格缩进,下面是一个25行的控制台版本的谢尔宾斯基三角形例子。(具体的字符可以参考样例输出)


你能帮他实现么



Input  


包含多组输入,EOF结束,每组输入包含一行,每行有一个数字N,表示要输出的是N行的谢尔宾斯基三角形。
1 <= N <= 512



Output  


对于每组输入,输出一个N行的谢尔宾斯基三角形。



Sample Input  


1
2
3
25



Sample Output  


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



Source  


谢尔宾斯基三角形



题解



可以找到规律:
n~2n-2行的内容是1~n-1行的内容水平放置两份


递推出关系即可

代码



/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
using namespace std;


const int maxn = 512 + 5;
bool d[maxn][maxn];

//将1~n-1行的内容拷贝两份在n~2n-2行(超过maxn时返回)
void copy(int n) {
for(int i = 1;i < n;i++) {
if(i + n - 1 < maxn)
for(int j = 1;j <= i;j++)
d[i + n - 1][j] = d[i + n - 1][j + n - 1] = d[i][j];
else
break;
}
}

int main() {
memset(d,false,sizeof(d));
d[1][1] = 1;

for(int i = 2;i < maxn;i = 2 * i - 1)
copy(i);

int n;
while(scanf("%d",&n) != EOF)
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= i;j++) {
printf("%c",d[i][j] ? '*' : ' ');
}
printf("\n");
}
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论