算法實踐：2的幂次方表示（遞歸）

2的幂次方表示

描述

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-HjnOLAKd-1583034303750)(C:\Users\HUAWEI\AppData\Roaming\Typora\typora-user-images\image-20200301114236455.png)]

輸入

一個正整數n（n≤20000）。

輸出

一行，符合約定的n的0，2表示（在表示中不能有空格）。

樣例

137
           

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

難度

中等，遞歸求解

解法

研究事例可知，先将輸入資料137按指數從大到小分為2(7)+2(3)+2(0)，然後又将指數按上面同樣的方法分為2(2)+2+2(0)、2+2(0)、0，就可分出137的最終結果2(2(2)+2+2(0))+2(2+2(0))+2(0)。非常明顯，這道題應該運用遞歸思想。

代碼

def Dfs(n):
    #尋找2的幂次方中最大的
    maxn = 15
    while(pow(2,maxn)>n):
        maxn = maxn-1
    y = maxn
    
    if(y==0):
        print('2(0)',end='')
    if(y==1):
        print('2',end='')
    if(y>1):
        print("2(",end='')
        Dfs(y)
        print(")",end='')
    if(n!=pow(2,y)):
        print("+",end='')
        Dfs(n-pow(2,y))
n = (int)(input())
Dfs(n)