题解 | #2的幂次方#

KY103 这个题有点意思

大体思路：首先设置一个辅助数组，按下标保存2^0, 2^1, 2^2.... 2^14。

递归时从后往前依次将数字减去2的k次幂，如果能减去，则递归分解k

递归的终止条件为：当前要分解的数字为0或者1。如果当前数字为0，则直接输出即可，如果为1，则说明减去一个2^1 刚刚好

对于输出，第一次考虑时利用队列，后来一想大可不必，直接在递归代码的上下文中进行输出即可。如果当前下标为1，则不需要输出括号，否则输出括号

#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;
// bool first = true;
int pows[15];


void split(int n, bool first){
    if(n == 0 ){
        printf("%d", n);
        return ;
    }
        
    if(n == 1){
        // printf("0");
        return;
    }
    for(int i=14; i>=0 && n > 0; i--){
        if(n - pows[i] >= 0){
            if(!first){
                printf("+");
            }
            printf("2");
            if(i != 1){
                printf("(");
                split(i, 1);
                printf(")");
            }
            
            
            first = 0;
            n = n - pows[i];
        }
    }
}


int main(void){
    
    
    int n;
    for(int i=0; i<15; i++){
        pows[i] = pow(2, i);
    }
    
    while(scanf("%d", &n) != EOF){
        split(n,1);
        printf("\n");
    }
    
    
    return 0;
}