algorithm - n を 2 の累乗の和として書く方法の数

Question

n などの数値を 2 のべき乗の合計で書き込む方法がいくつあるかを調べるアルゴリズムはありますか?

例: 4 の場合、次の 4 つの方法があります。

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

ありがとう。

Answer 1

g(m) が、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

シーケンスの再帰的定義 (Peter の A018819 へのリンクから):

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