TIitle

P1010 [NOIP1998 普及组] 幂次方

题目描述

任何一个正整数都可以用 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)。

输入格式

一行一个正整数 n。

输出格式

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

样例

样例输入

样例输出

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

Link

[P1010 NOIP1998 普及组] 幂次方 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Ideals

步骤

这道题属于比较明显的递归，大致上步骤分两步：

把大整数分解成2的幂乘相加的形式，如11 = 2(3)+2(1)+2(0)
把大整数下的小整数继续划分，结果是11 = 2(2+2(0))+2+2(0)

思路

把大整数分解成2的幂乘相加的形式，这个可以用二进制来实现，二进制字符串中1对应的下标可以算出幂乘的数字
例如：11的二进制为1011，1对应的幂乘数字为3、1、0，不难得出 len - 1 - i的计算方法。
也就是说这里我们可以输出11 = 2(3)+2(1)+2(0)的格式了，但是有一个比较烦的是加号的输出，这里用了一个标记sign，sign初始为0，也就是第一次不输出加号，第一次进入for就把sign置为1，后面每次都输出+2()的格式。
接下来把小整数丢进递归，也就是执行devide( len - 1 - i)。
细节1是递归出口是0、1、2，细节2是输出1的时候不要加括号，即不要输出2(1)，只输出2。所以加了这句if len(b) - 1 - i != 1，是1就不打括号。

Code

def devide(num):
    sign = 0
    if num == 1:
        return
    elif num <= 2:
        print(num,end='')
    else:
        b = bin(num)[2:]
        for i,c in enumerate(b):
            if c == '1':
                if sign == 0:
                    sign = 1
                else:
                    print("+",end='')
                print("2",end='')
                if len(b) - 1 - i != 1:
                    print("(",end='')
                devide(len(b) - 1 - i)
                if len(b) - 1 - i != 1:
                    print(")",end='')

if __name__ == '__main__':

    devide(int(input()))

Analyse

这道题属于递归，递归的复杂度算起来比较麻烦，这里可以猜测复杂度是O(logn)

（洛谷普及组）2的幂次方

幂次方