Description:

圈圈圆圆圈圈，lulu小朋友最近看喜羊羊看多了，老是受刺激就画圆圈，听到小于8的数字时，还会画出十分有规律的圆圈，现在你需要根据样例观察出规律，编写程序，根据输入的数字n（n<8）,输出对应的圆圈。

Input:

第一行是样例数T（T<9）

第2到2+T-1行每行有一个整数n（n<8），代表lulu听到的数字

Output:

听到对应数字时，输出对应样子的圆圈。

Sample Input:

4
0
1
2
3

Sample Output:

 O
O O
 O
    O
   O O
    O
 O     O
O O   O O
 O     O
    O
   O O
    O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O
    O                 O
   O O               O O
    O                 O
 O     O           O     O
O O   O O         O O   O O
 O     O           O     O
    O                 O
   O O               O O
    O                 O
             O
            O O
             O
          O     O
         O O   O O
          O     O
             O
            O O
             O

题目链接

这是一道基础的分形题，分形的核心是递归，假设输入1时输出

O

输入2时输出

 O
O O
 O

那么1就是递归出口，输入n时的图形就是利用4个n-1时图形再次拼凑成一个菱形，绘制图形时先计算n-1图形在n图形中的位置坐标，然后在相应的位置中利用递归绘制分形图形。
这道题输入n=0是输出

O

和我理解的分形代码相差1，在输入n后执行n++或者调用分形函数时执行（n+1,0,0）就可以了。题目还要求一行中最后一个"O"后面没有空格，这个在输出时判断一下就行，我写的代码比较复杂。

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;

char map[3000][3000];           // 分形字符数组

void Fractal(int n, int x, int y) {
    if (n == 1) {                           // 递归出口
        map[x][y] = 'O';
    }
    else {
        int k = pow(3, n - 2);                          // 计算每个(n - 1)分形的大小
        Fractal(n - 1, x        , y + k    );           // 上面的(n - 1)分形
        Fractal(n - 1, x + k    , y + 2 * k);           // 右边的(n - 1)分形
        Fractal(n - 1, x + k    , y        );           // 左边的(n - 1)分形
        Fractal(n - 1, x + 2 * k, y + k    );           // 下面的(n - 1)分形
    }
}

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;       // 输入样例数
    while (t--) {
        int n;
        cin >> n;
        n++;                                // 题目是从0开始
        int size = pow(3, n - 1);           // 计算分形大小
 		mem(map, ' ');                      // 初始化分形字符数组为空格
        Fractal(n, 0, 0);                   // 画分形
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < size; ++j) {
                cout << map[i][j];
                // 每一行最后一个O后面不带空格,如果输出“O”判断此“O”是否是最后一个“O”
                bool flag = 0;
                if (map[i][j] == 'O' && map[i][j + 1] == ' ') {
                    for (int k = j + 1; k < size;++k) {
                        if (map[i][k] == 'O') {
                            flag = 1;
                            break;
                        }
                    }
                    if (!flag) {
                        break;                  // 如果是此行最后一个“O”跳出此行
                    }
                }
            }
            cout << endl;       // 换行
        }
    }
    return 0;
}