javascript - 求一个整数所有的求和获取方式
问题描述
编写一个函数 sum(n)
,求n
有多少种求和获取方式。
如:n = 4 :
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1
所以 sum(4)=5
下面是几个特例:
sum(-1) = 0
sum(1) = 1
测试用例如下:
sum(2) // 2 -> 1+1 , 2
sum(3) // 3 -> 1+1+1, 1+2, 3
sum(4) // 5 -> 1+1+1+1, 1+1+2, 1+3, 2+2, 4
sum(5) // 7 -> 1+1+1+1+1, 1+1+1+2, 1+1+3, 1+2+2, 1+4, 5, 2+3
...
sum(50) // 204226
sum(80) // 15796476
sum(100) // 190569292
代码
function sum(a, b) {
b = b | 1;
return a >= 2 * b ? sum(a - b, b) + sum(a, b + 1) : a >= b ? 1 : 0;
}
展开版本:
function sum(a, b) {
b = b || 1; //当 b 未赋值,默认为 1
if (a >= 2 * b) {
return sum(a - b, b) + sum(a, b + 1);
}else if (a >= b) {
return 1;
} else {
return 0;
}
}
解释
sum
接收1个或两个参数:
第一个参数是要求和的数字
第二个参数是开始累加的数字(为了实现递归,将求和方式分解)
为了避免重复,累加数字在累加过程中只增加、不减少,即测试的累加数列中后一项一定会大于或等于前一项
简单地说、把
sum(a, b)
的序列分成两部分:
第一个部分即由
b
开头,后接sum(a-b, b)
的所有可能序列第二个部分即由所有大于
b
的数字开头的和为a
的序列,即sum(a, b+1)
函数中第二个参数可能不好理解,这里举个例子:
sum(3); //求整数 3 的所有求和方式,等价于 sum(3,1);
sum(3,1)
计算后返回 sum(2,1) + sum(3,2)
-
sum(2,1)
是 2 的所有求和方式,返回sum(a-b, b)
的形式表示假定第一个累加的数字为b
的值,所以从需要累加到的总和中减去b
, 即sum(a-b, b)
,计算后返回sum(1,1) + sum(2,2)
sum(1,1)
属于a>=b && a<*2b
的情况(见下),返回 1,对应的累加序列为 1 + 1 + 1sum(2,2)
同样属于a>=b && a<2*b
的情况(见下),返回 1,对应的累加序列为 1 + 2
-
sum(3,2)
即sum(a, b + 1)
是 3 从大于等于 2 开始的所有求和方式(对应a>=b && a<2*b
的情况)假设第一个累加数字是 2 ,由于累加数字不减少,累加数列至少是 2 + 2 (即
2*b
,必定大于a
),不符合要求在所有大于 2 的累加数中,仅有第一个累加数字为
a
、即 3 时,累加数列为 3 时符合要求,计一次有效的求和方式,返回 1
这就找到了 3 的所有求和方式:
1 + 1 + 1
1 + 2
3
目前这个函数效率不太高。计算 sum(100) 时需要等待较长时间,期待更好的解法
补充
递归固然写起来简单,理解容易,但是对电脑的负担是很重的
看 Dappur 的答案感觉所谓学习算法是很重要的,那些总结出的分析方法都是前人的智慧。
这里我将 Dappur 的答案翻译为 js,供题主参考:
function sum(n){
var f =[[1],[]];
for(var i=1; i<=n; f[++i]=[];){
for(var j=1; j<=i; ++j)
{
f[i][j] = f[i-1][j-1] || 0;
if(i-j>0) f[i][j] += f[i-j][j] || 0;
}
}
return f[n].reduce((a,b)=>a+b);
}
题主可自行对比尝试,对于较大的数字,真是快了一个数量级
这篇关于javascript - 求一个整数所有的求和获取方式的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!