算法設計技術

Question

通過公式2^n = 2 ^（n-1）+ 2 ^（n-1）設計用於計算任意非負整數n的遞歸算法。 先決條件：必須有一個加法運算執行

int computepowerOfTwo(int power) { 
    if(power == 1) 
     return 1; 
    else 
     return (2*computepowerOfTwo(power-1)) + (2*computepowerOfTwo(power-1)) 
} 

當我供電爲3最初它返回代碼中的16個

Answer 1

錯誤： -

1. if(power == 1)你應該返回2^1這是2。在else部分你正在返回
2. 相當於2*2^(power-1) + 2*2^(power-1)這將導致2 ^（N + 1），這是不對的，所以你應該只返回2*2^(power-1)

根據你的問題你的函數應儘可能遵循： -

int computepowerOfTwo(int power) { 
    if(power == 0) 
     return 1; 
    else 
     return computepowerOfTwo(power-1) + computepowerOfTwo(power-1); 
} 

Answer 2

至於對方的回答指出2^1是2，不1。

...但你的代碼實際上是停在0代替：

if(power == 0) 
    return 1; 

這是學習單元測試的價值的好機會。下面的一個簡單的測試用例...

for i in range(0, 11):              
    assert computepowerOfTwo(i) == 2 ** i 

...會告訴你：（1）你沒有處理的0和（2）你的答案2^1是錯的情況。