chenwhccc 发表于 2021-12-9 23:21:42

如题 求c++详解

题目描述：
把一个数N拆分成2的i次幂之和
比如N等于5时：
N=
1+1+1+1+1
1+1+1+2
1+2+2
1+4
共4种情况
对于NN (1 <= N <= 1,000,000)，请你计算有多少种拆分方式。 .
输入：
一行，一个数字,N
输出：
一行，一个数字，代表N的拆分方案数(由于结果可能很大，当结果足够大时输出它的最后9位)

jhq999 发表于 2021-12-12 15:49:58

本帖最后由 jhq999 于 2021-12-12 15:57 编辑

int fen1jie4(int val,int num,int max,int* bits)//英语渣懒的找英语单词，直接用汉语拼音代替。
{
        int ret=0,tmp=0,i=0,sum=0,bit=1<<num;
        if (num==0)
        {
                //tmp=bits;
                bits=val;
               
                for (i = 0; i <= max; i++)
                {
                        printf("%d*%d+ ",bits,1<<i);
                        sum+=bits*(1<<i);
                }
                printf("=%d\n",sum);
               
                return 1;
        }
        sum=0;
        for (i=0;i<=val/bit;i++)
        {

                bits=i;
                tmp=val-bit*i;
                ret=fen1jie4(tmp,num-1,max,bits);
                sum+=ret;
        }
        return sum;
}
int main()
{   
        int bits={0};
        int val=29,n=0,tmp=val;
        while(tmp>>=1)n++;
        int ret =fen1jie4(val,n,n,bits);
        printf("%d",ret);
    return 0;

}

29*1+ 0*2+ 0*4+ 0*8+ 0*16+ =29
27*1+ 1*2+ 0*4+ 0*8+ 0*16+ =29
25*1+ 2*2+ 0*4+ 0*8+ 0*16+ =29
23*1+ 3*2+ 0*4+ 0*8+ 0*16+ =29
21*1+ 4*2+ 0*4+ 0*8+ 0*16+ =29
19*1+ 5*2+ 0*4+ 0*8+ 0*16+ =29
17*1+ 6*2+ 0*4+ 0*8+ 0*16+ =29
15*1+ 7*2+ 0*4+ 0*8+ 0*16+ =29
13*1+ 8*2+ 0*4+ 0*8+ 0*16+ =29
11*1+ 9*2+ 0*4+ 0*8+ 0*16+ =29
9*1+ 10*2+ 0*4+ 0*8+ 0*16+ =29
7*1+ 11*2+ 0*4+ 0*8+ 0*16+ =29
5*1+ 12*2+ 0*4+ 0*8+ 0*16+ =29
3*1+ 13*2+ 0*4+ 0*8+ 0*16+ =29
1*1+ 14*2+ 0*4+ 0*8+ 0*16+ =29
25*1+ 0*2+ 1*4+ 0*8+ 0*16+ =29
23*1+ 1*2+ 1*4+ 0*8+ 0*16+ =29
21*1+ 2*2+ 1*4+ 0*8+ 0*16+ =29
19*1+ 3*2+ 1*4+ 0*8+ 0*16+ =29
17*1+ 4*2+ 1*4+ 0*8+ 0*16+ =29
15*1+ 5*2+ 1*4+ 0*8+ 0*16+ =29
13*1+ 6*2+ 1*4+ 0*8+ 0*16+ =29
11*1+ 7*2+ 1*4+ 0*8+ 0*16+ =29
9*1+ 8*2+ 1*4+ 0*8+ 0*16+ =29
7*1+ 9*2+ 1*4+ 0*8+ 0*16+ =29
5*1+ 10*2+ 1*4+ 0*8+ 0*16+ =29
3*1+ 11*2+ 1*4+ 0*8+ 0*16+ =29
1*1+ 12*2+ 1*4+ 0*8+ 0*16+ =29
21*1+ 0*2+ 2*4+ 0*8+ 0*16+ =29
19*1+ 1*2+ 2*4+ 0*8+ 0*16+ =29
17*1+ 2*2+ 2*4+ 0*8+ 0*16+ =29
15*1+ 3*2+ 2*4+ 0*8+ 0*16+ =29
13*1+ 4*2+ 2*4+ 0*8+ 0*16+ =29
11*1+ 5*2+ 2*4+ 0*8+ 0*16+ =29
9*1+ 6*2+ 2*4+ 0*8+ 0*16+ =29
7*1+ 7*2+ 2*4+ 0*8+ 0*16+ =29
5*1+ 8*2+ 2*4+ 0*8+ 0*16+ =29
3*1+ 9*2+ 2*4+ 0*8+ 0*16+ =29
1*1+ 10*2+ 2*4+ 0*8+ 0*16+ =29
17*1+ 0*2+ 3*4+ 0*8+ 0*16+ =29
15*1+ 1*2+ 3*4+ 0*8+ 0*16+ =29
13*1+ 2*2+ 3*4+ 0*8+ 0*16+ =29
11*1+ 3*2+ 3*4+ 0*8+ 0*16+ =29
9*1+ 4*2+ 3*4+ 0*8+ 0*16+ =29
7*1+ 5*2+ 3*4+ 0*8+ 0*16+ =29
5*1+ 6*2+ 3*4+ 0*8+ 0*16+ =29
3*1+ 7*2+ 3*4+ 0*8+ 0*16+ =29
1*1+ 8*2+ 3*4+ 0*8+ 0*16+ =29
13*1+ 0*2+ 4*4+ 0*8+ 0*16+ =29
11*1+ 1*2+ 4*4+ 0*8+ 0*16+ =29
9*1+ 2*2+ 4*4+ 0*8+ 0*16+ =29
7*1+ 3*2+ 4*4+ 0*8+ 0*16+ =29
5*1+ 4*2+ 4*4+ 0*8+ 0*16+ =29
3*1+ 5*2+ 4*4+ 0*8+ 0*16+ =29
1*1+ 6*2+ 4*4+ 0*8+ 0*16+ =29
9*1+ 0*2+ 5*4+ 0*8+ 0*16+ =29
7*1+ 1*2+ 5*4+ 0*8+ 0*16+ =29
5*1+ 2*2+ 5*4+ 0*8+ 0*16+ =29
3*1+ 3*2+ 5*4+ 0*8+ 0*16+ =29
1*1+ 4*2+ 5*4+ 0*8+ 0*16+ =29
5*1+ 0*2+ 6*4+ 0*8+ 0*16+ =29
3*1+ 1*2+ 6*4+ 0*8+ 0*16+ =29
1*1+ 2*2+ 6*4+ 0*8+ 0*16+ =29
1*1+ 0*2+ 7*4+ 0*8+ 0*16+ =29
21*1+ 0*2+ 0*4+ 1*8+ 0*16+ =29
19*1+ 1*2+ 0*4+ 1*8+ 0*16+ =29
17*1+ 2*2+ 0*4+ 1*8+ 0*16+ =29
15*1+ 3*2+ 0*4+ 1*8+ 0*16+ =29
13*1+ 4*2+ 0*4+ 1*8+ 0*16+ =29
11*1+ 5*2+ 0*4+ 1*8+ 0*16+ =29
9*1+ 6*2+ 0*4+ 1*8+ 0*16+ =29
7*1+ 7*2+ 0*4+ 1*8+ 0*16+ =29
5*1+ 8*2+ 0*4+ 1*8+ 0*16+ =29
3*1+ 9*2+ 0*4+ 1*8+ 0*16+ =29
1*1+ 10*2+ 0*4+ 1*8+ 0*16+ =29
17*1+ 0*2+ 1*4+ 1*8+ 0*16+ =29
15*1+ 1*2+ 1*4+ 1*8+ 0*16+ =29
13*1+ 2*2+ 1*4+ 1*8+ 0*16+ =29
11*1+ 3*2+ 1*4+ 1*8+ 0*16+ =29
9*1+ 4*2+ 1*4+ 1*8+ 0*16+ =29
7*1+ 5*2+ 1*4+ 1*8+ 0*16+ =29
5*1+ 6*2+ 1*4+ 1*8+ 0*16+ =29
3*1+ 7*2+ 1*4+ 1*8+ 0*16+ =29
1*1+ 8*2+ 1*4+ 1*8+ 0*16+ =29
13*1+ 0*2+ 2*4+ 1*8+ 0*16+ =29
11*1+ 1*2+ 2*4+ 1*8+ 0*16+ =29
9*1+ 2*2+ 2*4+ 1*8+ 0*16+ =29
7*1+ 3*2+ 2*4+ 1*8+ 0*16+ =29
5*1+ 4*2+ 2*4+ 1*8+ 0*16+ =29
3*1+ 5*2+ 2*4+ 1*8+ 0*16+ =29
1*1+ 6*2+ 2*4+ 1*8+ 0*16+ =29
9*1+ 0*2+ 3*4+ 1*8+ 0*16+ =29
7*1+ 1*2+ 3*4+ 1*8+ 0*16+ =29
5*1+ 2*2+ 3*4+ 1*8+ 0*16+ =29
3*1+ 3*2+ 3*4+ 1*8+ 0*16+ =29
1*1+ 4*2+ 3*4+ 1*8+ 0*16+ =29
5*1+ 0*2+ 4*4+ 1*8+ 0*16+ =29
3*1+ 1*2+ 4*4+ 1*8+ 0*16+ =29
1*1+ 2*2+ 4*4+ 1*8+ 0*16+ =29
1*1+ 0*2+ 5*4+ 1*8+ 0*16+ =29
13*1+ 0*2+ 0*4+ 2*8+ 0*16+ =29
11*1+ 1*2+ 0*4+ 2*8+ 0*16+ =29
9*1+ 2*2+ 0*4+ 2*8+ 0*16+ =29
7*1+ 3*2+ 0*4+ 2*8+ 0*16+ =29
5*1+ 4*2+ 0*4+ 2*8+ 0*16+ =29
3*1+ 5*2+ 0*4+ 2*8+ 0*16+ =29
1*1+ 6*2+ 0*4+ 2*8+ 0*16+ =29
9*1+ 0*2+ 1*4+ 2*8+ 0*16+ =29
7*1+ 1*2+ 1*4+ 2*8+ 0*16+ =29
5*1+ 2*2+ 1*4+ 2*8+ 0*16+ =29
3*1+ 3*2+ 1*4+ 2*8+ 0*16+ =29
1*1+ 4*2+ 1*4+ 2*8+ 0*16+ =29
5*1+ 0*2+ 2*4+ 2*8+ 0*16+ =29
3*1+ 1*2+ 2*4+ 2*8+ 0*16+ =29
1*1+ 2*2+ 2*4+ 2*8+ 0*16+ =29
1*1+ 0*2+ 3*4+ 2*8+ 0*16+ =29
5*1+ 0*2+ 0*4+ 3*8+ 0*16+ =29
3*1+ 1*2+ 0*4+ 3*8+ 0*16+ =29
1*1+ 2*2+ 0*4+ 3*8+ 0*16+ =29
1*1+ 0*2+ 1*4+ 3*8+ 0*16+ =29
13*1+ 0*2+ 0*4+ 0*8+ 1*16+ =29
11*1+ 1*2+ 0*4+ 0*8+ 1*16+ =29
9*1+ 2*2+ 0*4+ 0*8+ 1*16+ =29
7*1+ 3*2+ 0*4+ 0*8+ 1*16+ =29
5*1+ 4*2+ 0*4+ 0*8+ 1*16+ =29
3*1+ 5*2+ 0*4+ 0*8+ 1*16+ =29
1*1+ 6*2+ 0*4+ 0*8+ 1*16+ =29
9*1+ 0*2+ 1*4+ 0*8+ 1*16+ =29
7*1+ 1*2+ 1*4+ 0*8+ 1*16+ =29
5*1+ 2*2+ 1*4+ 0*8+ 1*16+ =29
3*1+ 3*2+ 1*4+ 0*8+ 1*16+ =29
1*1+ 4*2+ 1*4+ 0*8+ 1*16+ =29
5*1+ 0*2+ 2*4+ 0*8+ 1*16+ =29
3*1+ 1*2+ 2*4+ 0*8+ 1*16+ =29
1*1+ 2*2+ 2*4+ 0*8+ 1*16+ =29
1*1+ 0*2+ 3*4+ 0*8+ 1*16+ =29
5*1+ 0*2+ 0*4+ 1*8+ 1*16+ =29
3*1+ 1*2+ 0*4+ 1*8+ 1*16+ =29
1*1+ 2*2+ 0*4+ 1*8+ 1*16+ =29
1*1+ 0*2+ 1*4+ 1*8+ 1*16+ =29
140
页: [1]
查看完整版本: 如题 求c++详解