蓝桥杯_算法训练_2的次幂表示（递归）

//这个递归挺难得，凑合看懂

任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0。现在约定幂次用括号来表示，即a^b表示为a(b)此时，137可表示为：2(7)+2(3)+2(0) 进一步：7=2^2+2+2^0 （2^1用2表示）3=2+2^0。所以最后137可表示为：2(2(2)+2+2(0))+2(2+2(0))+2(0) 又如：1315=2^10+2^8+2^5+2+1 所以1315最后可表示为：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)。

输入格式

正整数（1<=n<=20000）

 

输出格式

符合约定的n的0，2表示（在表示中不能有空格）

 

样例输入

137

样例输出

2(2(2)+2+2(0))+2(2+2(0))+2(0)

样例输入

1315

样例输出

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

用递归实现会比较简单，可以一边递归一边输出。

 

解题思路

基本算法是数转二进制，使用求余+除法循环计算。题目提示了递归，但是一下递归不容易写对而且不好调试，可以一步步来，先写成某个数的次方和，调试正确后再对次方递归解析。

递归时，上一次计算的次方成为新的数，应该注意这个数为0和为2时的特殊情况。

一个数被分解后，成为剩余的数+2的次方，这两个数其中之一都可能为0，应该注意只有这两个数都非零时才输出'+'号

 

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
void put(int num,int n){//num为当前数，n为几次方 
    //printf("num = %d, n = %d\n",num,n);
    if(num==0)return;//结束条件，分解结束 
    int r=num%2;//最后一位取出来 
    num=num>>1;//右移一位 
    put(num,n+1);//下一位次方 +1 
    if(num&&r)printf("+");//前面和当前位非0的时候输出'+'号 
    if(r){//当前最后一位 非0 那么输出对应的表示 
        if(n==1)
            printf("2");
        else{
            printf("2(");
            if (n==0)printf("0");
            else put(n,0);//次方大于等于2 时，继续分解 
            printf(")");
        }
    }
}
int main(){
    int num;
    scanf("%d",&num);
    put(num,0);//刚开始 最后一位 是0次方 
    return 0;
}