求一个程序:输入整数n,可分成m(0<m<n)个数相加,每种组合算一种情况,输出有多少种?例如n=3.输出有两种1.1+2 2.1+1+1。n=4时,输出有4种:1.1+1+1+1 2.2+2 3.1+3 4.1+1+2 。给出0<n<13,求一个程序实现它!
function f(n)
{
return f1(n,1)-1; //最顶层只有一个n不分不算
}
//递归:按从小到底分割,用p限制
function f1(n, p)
{
var r = 0;
if (n>=p) r = 1; //直接用掉n算1种
var i;
for (i=p; i<n; i++) {
r += f1(n-i, i);
}
return r;
}
结果
n f(n)
-- ----
1 0
2 1
3 2
4 4
5 6
6 10
7 14
8 21
9 29
10 41
11 55
12 76