09 洛谷 P1010 幂次方(递归)

题目链接

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