蓝桥杯算法训练VIP-幂方分解(python17行，好理解)

解题思路:每次求出幂次的组成由大到小排列，存储到列表里(也可以直接由高幂次到低幂次遍历)，再利用递归求解。

注意事项:

参考代码:

解法一：列表存储幂次组合

def fun2(x):  # 求出幂次的组成由大到小排列
   a = []
   cnt = 0
   while x:
       if x & 1:
           a.append(cnt)
       cnt += 1
       x >>= 1
   a = a[::-1]
   return a

def fun1(x):
   if x == 0 or x == 2:
       print('%d' % x, end='')
       return
   a = fun2(x)
   for i in range(len(a)):
       if a[i] == 1:
           print('2', end='')
       else:
           print('2(', end='')
           fun1(a[i])
           print(')', end='')
       if i != len(a) - 1:
           print('+', end='')

n = int(input())
fun1(n)

解法二：直接由高到低遍历幂次并递归

def fun1(x):
   if x == 0 or x == 2:
       print('%d' % x, end='')
       return
   lens = len(bin(x)) - 2  # 转为二进制长度
   for i in range(lens - 1, -1, -1):  # 从高到低遍历幂次
       if (x >> i) & 1:  # 有2**i的组成
           if i == 1:
               print('2', end='')
           else:
               print('2(', end='')
               fun1(i)
               print(')', end='')
           if 2 ** i != x & -x:  # i次幂不是最低次幂时(其中x&-x可以求出最低位幂如6&-6=2)
               print('+', end='')
n = int(input())
fun1(n)