蓝桥杯_算法训练_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表示（在表示中不能有空格）

样例输入

样例输出

样例输入

样例输出

提示

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

解题思路

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

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

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

AC代码