|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
把一个数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: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[num];
- bits[num]=val;
-
- for (i = 0; i <= max; i++)
- {
- printf("%d*%d+ ",bits[i],1<<i);
- sum+=bits[i]*(1<<i);
- }
- printf("=%d\n",sum);
-
- return 1;
- }
- sum=0;
- for (i=0;i<=val/bit;i++)
- {
- bits[num]=i;
- tmp=val-bit*i;
- ret=fen1jie4(tmp,num-1,max,bits);
- sum+=ret;
- }
- return sum;
- }
- int main()
- {
- int bits[8]={0};
- int val=29,n=0,tmp=val;
- while(tmp>>=1)n++;
- int ret =fen1jie4(val,n,n,bits);
- printf("%d",ret);
- return 0;
- }
复制代码
|
|