递归图形输出问题通用解法

青旅半醒 2022-06-01 05:55 179阅读 0赞

ACM学了有一段时间了，有一类题目遇到过了很多次，但很少做出来，这类题目就是递归图形输出。找了一些大神博客学习了一下，在这里做个总结。

那什么是递归图形输出问题呢？顾名思义，按照某种递归的规律输出某种类型图形的n次递归后的图形。

比如：

n=0：

![SouthEast][]

n=1：

![SouthEast 1][]

n=2：

![SouthEast 2][]

n=3：

![SouthEast 3][]

现在问你当n=7的时候这个图形是什么样子的。这种要求输出按某种规律递归增长的图形的问题就是递归图形输出问题。

再比如说POJ-1941也是一道典型的递归图形输出，链接->https://vjudge.net/problem/POJ-1941

这一类问题全部有一套通用的解法：

1，找n次递归增长后的图形的中点。

2，根据图形增长的规律找到所有子图形的中点。

3，对子图形递归找子图形的中点。

4，直到n=0后，对当前点的位置做标记，用二维数组存。

5，遍历二维数组输出图形。

就比如说我举的那个例子解题代码如下：

#include <iostream>  
    #include <cstdio>  
    #include <cstring>  
    #include <string>  
    #include <cstdlib>  
    #include <cmath>  
    #include <vector>  
    #include <queue>  
    #include <iterator>  
    #include <map>  
    #include <algorithm>  
    #include <set>  
    #include <functional>  
    #include <time.h>  
    #define lson rt<<1  
    #define rson rt<<1|1  
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 100005;
    const LL MOD = 1000000007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    LL gcd(LL a, LL b) { return b == 0 ? a : gcd(b, a%b); }
    LL ppow(LL a, LL b) { LL res = 1; for (int i = 1; i <= b; i++)   res *= a; return res; }
    LL quick_mod(LL a, LL b, LL c) { LL ans = 1; while (b) { if (b % 2 == 1)ans = (ans*a) % c; b /= 2; a = (a*a) % c; }return ans; }
    
    bool MAP[3000][3000];//二维数组存每个点是输出0还是空格
    
    void draw(int x, int y, int n)//画图函数
    {
    	int res;
    	if (n == 0)
    		MAP[x][y] = true;//n=0的时候就是一个点，标记为要输出0
    	else
    	{
    		res = ppow(3, n - 1);
    		draw(x, y, n - 1);//每一个图由五个子图构成，对五个子图递归调用draw函数
    		draw(x - res, y + res, n - 1);
    		draw(x - res, y - res, n - 1);
    		draw(x + res, y + res, n - 1);
    		draw(x + res, y - res, n - 1);
    	}
    }
    
    int main()
    {
    	int n, x;
    	while (scanf("%d",&n)!=EOF)
    	{
    		memset(MAP, 0, sizeof MAP);
    		x = (ppow(3, n) + 1) / 2;
    		draw(x, x, n);
    		for (int i = 1; i <= x*2-1; i++)//遍历二维数组输出
    		{
    			for (int j = 1; j <= x*2-1; j++)
    			{
    				if (MAP[i][j])
    					printf("0");
    				else
    					printf(" ");
    			}
    			printf("\n");
    		}
    	}
    }

[SouthEast]: /images/20220601/db603d8987c746f894482a2f2dd34276.png
[SouthEast 1]: /images/20220601/f9f1b5ebcb824796b09623f37cf8ab33.png
[SouthEast 2]: /images/20220601/e745bac1cabc490e821656bc19187b05.png
[SouthEast 3]: /images/20220601/d8d433e812b94abba3b09fb5f858cf56.png