AOJ 716.谢尔宾斯基三角形

谢尔宾斯基三角形

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

Original

Transformed

1
2
3
25

Sample Output

Original

Transformed

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

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>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

#define REP(n) for(int o=0;o<n;o++)

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("
");
        }
    return 0;
}