Изучая количество различных способов, число может быть выражено как сумма степеней 2

Question

Определить f (0) = 1 и f (n) как число различных способов n можно выразить как сумму целых степеней 2, используя каждую мощность не больше, чем, например twice.For, F (10) = 5, так как существует пять различных способов выразить 10:

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

---

что е (п) для данного 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

Часто с этими видами головоломок, вы просто должны задать вопрос а другой путь.

Учитывая начальный номер, сколько способов вы можете преобразовать его в ноль путем вычитания степеней двух? Вы можете вычесть каждое число ноль, одно или два раза.

Сделать сигнатура функции принимают следующие параметры:

• п: число вы пытаетесь преобразовать к нулю
• р: минимальное количество вы позволили вычесть

Алгоритм будет выглядеть следующим образом. (в машинописном машиностроении)

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);