天天看點

算法實踐: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)
           

繼續閱讀