求n的2的幂的和的组合数及其和的形式

yyy_fcz

求n的2的幂的和的组合数及其和的形式 任意给一个自然数n，求其可以表达为2的幂的和的组合个数。 如： 2=1+1，=2，所以2的组合数是2. 4=1+1+1+1=2+1+1=2+2=4，所以4的组合数是4. 注意1+1+2与1+2+1与2+1+1看成是一种组合。 若只计算组合个数，我做了个程序，很简单快捷，但当n=1000000时，计算机要溢出。 我也做出了一个可以求出n的个数和所有排列的程序，但效率太低，算1000都要好长时间。 哪位能给出一个好的算法来给出任意n（至少大于1000）的排列个数和所有排列来。

wayne

在编程擂台版块，与你的主题紧挨着的，楼主竟然不知 http://bbs.emath.ac.cn/thread-2276-1-1.html

yyy_fcz

递推公式是 d=[n/2]+1, s(d)=s(d-1)+s([d+1]/2), s(1)=1;

gxqcn

2# 已指出，相同话题已有，且正在进行中， 为避免讨论的不集中，故对本主题进行关闭处理。