题解：P10458 Fractal

sillation · 2024-05-18 20:56:55 · 题解

题目传送门

思路：

根据输出样例我们可以知道 n 度的盒分形图为一个长宽为 3^{n-1} 的正方形。

设置递归函数 {f(n,x,y)} 生成以坐标 x,y 为左上角的 n 度盒分形。

1. 递归边界： 若 n=1，则在 x,y 输出 X。

2. 若 n > 1,则计算 n - 1 度的盒子的规模 m = 3^{n-2},分别在左上方，右上方，中间，左下方和右下方 5 个 n-1 度的盒子。

• 对于左上方的 n-1 度的盒子，左上角的坐标为 x,y。递归函数为 {f(n - 1,x + 2m , y)}。

• 对于右上方的 n-1 度的盒子， 右上方的坐标为 x + 2m,y。递归函数为 {f( n - 1,x + 2m,y)}。

• 对于中间的 n-1 度的盒子，中间的坐标为 x + m,y + m。递归函数为 {f(n-1,x+m,y+m)}。

• 对于左下方的 n-1 度的盒子，左下方的坐标为 x,y+2m。递归函数为 {f (n-1,x,y+2m)} 。

• 对于右上方的 n-1 度的盒子，右下方的坐标为 x+2m,y+2m。递归函数为 {f(n-1,x+2m,y+2m)}。

代码：

#include<bits/stdc++.h>
using namespace std;
char mp[730][730];
void f(int n, int x, int y) {
    //递归边界
    if (n == 1) {
        mp[x][y]='X';
    } else {
        int m = pow(3, n - 2);
        //递归5个位置 
        f(n - 1, x, y);
        f(n-1, x+2*m, y);
        f(n - 1, x , y + 2 * m);
        f(n - 1, x + m, y + m);
        f(n-1,x+2*m,y+2*m);
    }
}
int main() {
    int n ;
    while (1) {
        cin >> n;
        if(n==-1) return 0;
        int c=pow(3, n - 1);
         //初始化
        memset(mp,' ',sizeof(mp));
        f(n, 0, 0);
        for (int i = 0; i < c; i++) {
            for(int j=0; j< c; j++) printf("%c",mp[i][j]);
            cout<<endl;
        }
        cout <<'-'<<endl;
    }
    return 0;
}

笔者文风不好，请见谅。