n作为2的幂的总和的写法数量 [英] Number of ways to write n as a sum of powers of 2

问题描述

是否有一种算法可以找出用多少种方式写一个数字(例如n)，且总和为2?

示例:对于4种方法，有四种方法:

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

谢谢.

解决方案

假设g(m)是将m乘以2的幂的总和.所有数字的幂小于或等于k的m写为2的幂的和的方式.然后我们可以简化为等式:

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

希望有帮助！

Is there any algorithm to find out that how many ways are there for write a number for example n , with sum of power of 2 ?

example : for 4 there are four ways :

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

thanks.

解决方案

Suppose g(m) is the number of ways to write m as a sum of powers of 2. We use f(m,k) to represent the number of ways to write m as a sum of powers of 2 with all the numbers' power is less than or equal to k. Then we can reduce to the equation:

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

Take 6 as an example:

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

Here is the code below:

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

Hope it helps!

这篇关于n作为2的幂的总和的写法数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！