探索一個數的不同方式的數量可以表示爲2的冪的和

Question

將f（0）= 1和f（n）定義爲不同方式的數量n可以表示爲整數冪的和使用每個功率不超過twice.For例子更中，f（10）= 5，因爲有五種不同的方式來表達10 2：

1. 1 + 1 + 8
2. 1 + 1 + 4 + 4
3. 1 + 1 + 2 + 2 + 4
4. 2 + 4 + 4
5. 2 + 8

---

什麼是F（N）爲給定的n.you可以使用任何計算機語言，

import math 
def powOfTwo(n): 
    i=0 
    while(pow(2,i)<=n): 
     if (pow(2,i)==n): 
      return True 
     else: 
      i=i+1 
    return False 

def noWays(n): 
    if n==1: 
     return 1 
    elif n==0: 
     return 0 
    else: 
     if (n%2==0): 
      if (powOfTwo(n-2) and n-2!=2):     
       return (1+noWays((n-2)/2)+noWays(n/2)) 
      else: 
       return (noWays((n-2)/2)+noWays(n/2)) 
     else: 
      if (powOfTwo(n-1)and n-1!=2): 
       return (1+noWays((n-1)/2)) 
      else: 
       return (noWays((n-1)/2)) 
n=int(input()) 
v=noWays(n) 
print(v) 

Answer 1

通常情況下，這些類型的謎題，你就必須要問的問題一個不同的方式。

給定一個起始數字，有多少種方法可以通過減去兩個冪來將它轉換爲零？你可以減去每個數字零次，一次或兩次。

讓函數簽名採取以下參數：

• N：你想轉換到零
• 數P：你被允許的最小數量減去

算法如下所示。 （in Typescript）

function pathsToZero(n: number, p:number) : number { 
    if(n === 0) { 
     // We've hit the target! 
     return 1; 
    } 
    if(n < p) { 
     // This will only be negative. No point in continuing 
     return 0; 
    } 
    return pathsToZero(n, p*2) + pathsToZero(n-p, p*2) + pathsToZero(n-p*2, p*2); 
} 


let resultForTen = pathsToZero(10, 1);