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

希望能帮助到你！

Answer 2

序列的递归定义（来自 Peter 到 A018819 的链接）：

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

Answer 3

您想找到可以将数字表示为 2 的幂的总和的方式的数量。首先，您需要找到该特定数字中设置的位数，因为设置的位数将为我们提供最小数量需要将其表示为 2 的幂的总和。将其表示为 2 的幂的总和所需的最大数字将是数字本身，因为您可以将其表示为 1 的总和（因为 2 的 0 幂是 1 ）。例子：5可以表示为（1+1+1+1+1）

因此，将数字表示为 2 的幂的方法总数由公式简单地给出 --> 令 no 为 x ( x - no of set bits in x ) + 1 ；例如，设数字为 17，则 17 中的设置位数为 2，因此路数为 (17 - 2) + 1 = 16；