2018年全国多校算法寒假训练营练习比赛(第一场)G - 圆圈(分形)
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;
}