MS 的 f2f 面试中的面试问题:
确定积分解的个数
x1 + x2 + x3 + x4 + x5 = N
哪里0 <= xi <= N
所以基本上我们需要在最多5个部分中找到N的分区数 应该用纸和笔来解决。虽然没有取得太大进展,有人对此有解决方案吗?
最佳答案
假设数字严格 > 0。
考虑一个整数段 [0, N]。问题是将其拆分为正长度的 4 段。想象一下,我们通过在相邻数字之间放置 4 个分隔点来做到这一点。有多少方法可以做到这一点? C(N-1, 4)。
现在,一些数字可以是 0-s。设 k 为非零数字的数量。我们可以用C(5,k) 种方式选择它们,每一种都有C(N-1, k) split 。将 [0,5] 范围内的所有 k 累加,我们得到
求和[ C(5,k) * C(n-1,k); k = 0 到 5]
关于algorithm - 积分解的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11846001/