algorithm - 将 n 写成 2 的幂之和的方法数

Question

是否有任何算法可以找出有多少种方法可以写出一个数字，例如 n ，其总和为 2 ？

例如:对于 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;
}

希望对您有所帮助!