题目

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;
}