將n寫爲2的冪的和的方法的數量

Question

是否有任何算法可以找出有多少種寫法的方法，例如n，功率和爲2？

例如：4，有四種方式：

4 = 4 
4 = 2 + 2 
4 = 1 + 1 + 1 + 1 
4 = 2 + 1 + 1 

感謝。

Answer 1

假設G（M）是書寫方式米爲2的冪我們使用的總和數量f（m，k）表示寫入m的方式的數量作爲2的冪的和，並且所有數字的冪小於或等於k。然後我們就可以減少對等式：

if m==0 f(m,k)=1;  
if k<0 f(m,k)=0;  
if k==0 f(m,k)=1;  
if m>=power(2,k) f(m,k)=f(m-power(2,k),k)+f(m,k-1);//we can use power(2,k) as one of the numbers or not.  
else f(m,k)=f(m,k-1); 

以6爲例：

g(6)=f(6,2) 
=f(2,2)+f(6,1) 
=f(2,1)+f(4,1)+f(6,0) 
=f(0,1)+f(2,0)+f(2,1)+f(4,0)+1 
=1+1+f(0,1)+f(2,0)+1+1 
=1+1+1+1+1+1 
=6 

這裏是下面的代碼：

#include<iostream> 
using namespace std; 

int log2(int n) 
{ 
    int ret = 0; 
    while (n>>=1) 
    { 
     ++ret;  
    } 
    return ret; 
} 

int power(int x,int y) 
{ 
    int ret=1,i=0; 
    while(i<y) 
    { 
     ret*=x; 
     i++; 
    } 
    return ret; 
} 

int getcount(int m,int k) 
{ 
    if(m==0)return 1; 
    if(k<0)return 0; 
    if(k==0)return 1; 
    if(m>=power(2,k))return getcount(m-power(2,k),k)+getcount(m,k-1); 
    else return getcount(m,k-1); 

} 

int main() 
{ 
    int m=0; 
    while(cin>>m) 
    { 
     int k=log2(m); 
     cout<<getcount(m,k)<<endl; 
    } 
    return 0; 
} 

希望它能幫助！

Answer 2

序列的遞歸定義（從彼得的鏈接A018819）：

f(n) = 1 if n = 0, Sum(j = 0..[n/2], f(j)) if n > 0 http://mathurl.com/nuaarfm.png