求一个整数所有的求和获取方式

jafeney
  • 910

编写一个函数 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
回复
阅读 4.6k
3 个回答

代码

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个或两个参数:

  1. 第一个参数是要求和的数字

  2. 第二个参数是开始累加的数字(为了实现递归,将求和方式分解)

  3. 为了避免重复,累加数字在累加过程中只增加、不减少,即测试的累加数列中后一项一定会大于或等于前一项


简单地说、把 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 + 1

    • sum(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);
}

题主可自行对比尝试,对于较大的数字,真是快了一个数量级

int n;
//input n here
f[0][0]=1;
for(int i=1;i<=n;++i)
    for(int j=1;j<=i;++j)
    {
        f[i][j]=f[i-1][j-1];
        if(i-j>0) f[i][j]+=f[i-j][j];
    }
int ans=0;
for(int i=1;i<=n;++i) ans+=f[n][i];
//output ans here

由于好久没写js有点生疏了,就直接上C++代码了

这是一个简单的动态规划问题,我们用f[i][j]表示把数字i分割为j个部分的方案数。显然,最终结果为ANS=Σf[n][j] 1≤j≤n

接下来考虑DP方程的转移,即从已有的方案生成一个新的方案。为避免重复,我们采取如下操作:
1、在当前方案末尾加一个1上去,即由分割方案X=a1+a2+a3+...+ak得到X+1=a1+a2+a3+...+ak+1
2、将当前方案的每个部分都加一个1上去,即由分割方案X=a1+a2+a3+...+ak得到X+k=(a1+1)+(a2+1)+(a3+1)+...+(ak+1)

题主可以自己想一想,或者试着写几个出来,就会发现这样做的话,每个方案必定是从另一个唯一的方案生成而来的

把上面的两个操作写成代码,就是f[i][j]=f[i-1][j-1]+f[i-j][j]

当然,既然我们所有的方案都是从另一个方案生成而来的,那必定有一个初始方案啊,显然的,初始方案就是f[0][0]=1,把数字0分割为0个部分,这样算一种情况。

当然还有其他的解法,比如生成函数之类的,可以参考http://blog.csdn.net/qq429205...,但是如果用程序代码来实现的话,DP是最简单的。

cxgenjoy
  • 2
新手上路,请多包涵

我的思路一直卡在数列里出不来了。这个可以求出来一个数列公式把。比如斐波那契数列那种f(n)=f(n-1)+f(n-2).

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
你知道吗?

宣传栏