PAT 天梯赛 L1-002 【递归】

题目链接

https://www.patest.cn/contests/gplt/L1-002

题意

给出一个数字 和一个字符 画出 可用数字下的最大沙漏，并且输出剩余没用掉的符号数

思路

可以先打一个表 判断 多少个数字 能够组成 沙漏 然后 遍历一遍，给的符号数 最多能够打 多少个符号数 组成的沙漏 然后 递归打出来

AC代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <cstdlib>

#include <ctype.h>

#include <numeric>

#include <sstream>

using namespace std;

typedef long long LL;

const double PI = 3.14159265358979323846264338327;

const double E = 2.718281828459;

const double eps = 1e-6;

const int MAXN = 0x3f3f3f3f;

const int MINN = 0xc0c0c0c0;

const int maxn = 1e2 * 5 + 5;

const int MOD = 1e9 + 7;

int a[23] = {1};

char c;

void print(int n, int cur)

{

    if (n == 1)

    {

        while (cur --)

            printf(" ");

        printf("%c\n", c);

    }

    else

    {

        for (int i = 0; i < cur; i++)

            printf(" ");

        for (int i = 0; i < n; i++)

            printf("%c", c);

        printf("\n");

        print(n - 2, cur + 1);

        for (int i = 0; i < cur; i++)

            printf(" ");

        for (int i = 0; i < n; i++)

            printf("%c", c);

        printf("\n");

    }

}

int main()

{

    int i, j;

    for (i = 1, j = 3; i < 23; i++, j += 2)

        a[i] += j * 2 + a[i - 1];

    int n;

    scanf("%d %c", &n, &c);

    int vis;

    for (i = 0 ; i < 23; i++)

    {

        if (a[i] > n)

        {

            vis = i - 1;

            break;

        }

        else if (a[i] == n)

        {

            vis = i;

            break;

        }

    }

    print((vis + 1) * 2 - 1, 0);

    cout << n - a[vis] << endl;

}