09 洛谷 P1010 幂次方(递归)

2020-07-24  本文已影响0人  _Mirage

题目链接

image.png

分析题意,发现其实就是先把输入的n减去能减去的2的最大的幂级,然后剩下的数也需要求出剩下的2的幂级。
其实就是一个递归的思路。

分析:

  1. 边界条件:
    n = 0,就可以停止寻找2的幂级数了(因为最小的是2^0=1,小于1了已经不能拆分了)

  2. 状态转移方程:
    2 ^ i <= n && 2 ^ (i + 1) > n,则
    f(n) = 2 ^ i + f(n - 2 ^ i)

分析,如果i是大于2的,那么我们需要再对其递归下,以得出值全为2的幂。

image.png

最后剩一个难点就是+号的输出,因为有的状态需要输出+号,有的状态不需要输出,这种情况我们就得通过递归的函数形参来进行判断,如果当前形参已经是0,那么表示已经到了表达式结尾,则不需要输出+号,反之需要。

源码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;

void f(int n) {
    int x, y;
    if (n == 0) {
        return;
    }
    for (int i = 1; ; i++) {
        if (1 << i > n) {
            x = i - 1;
            if (x > 2) {
                printf("2(");
                f(x);
                printf(")");
            }
            else {
                if (x == 1) printf("2");
                else printf("2(%d)", x);
            }
            y = n - (1 << x);
            if (y != 0)
                printf("+");
            f(y);
            return;
        }
    }
}

void solve(int n) {
    f(n);
}

int main(int argc, char const *argv[])
{
    int n;
    scanf("%d", &n);
    solve(n);

    return 0;
}
运行结果: image.png
image.png
上一篇 下一篇

猜你喜欢

热点阅读