performance - 将数字拆分为总和组件

Question

是否有一种有效的算法可以将一个数字分成 N 个小节，以便数字的总和与原始数字之和相加，并具有最小基数？例如，如果我想将 50 分成 7 个小节，并且最小基数为 2，我可以执行 10,5,8,2,3,5,17(以及任何其他组合数)。我想将数字保留为整数，并且相对随机，但我不确定如何有效地生成总和为原始数字且不包含低于给定最小值的数字。有什么建议吗？

编辑 - 只是为了复制/粘贴我的评论，整数不必是唯一的，但我想每次都避免它们的大小相等(例如 50 分成 10 个相等的大小)。

Answer 1

这是一个算法:

1. 划分N通过 m其中 N是你的号码和m是小节的数量。
2. 将结果四舍五入到最接近的值，并将该值分配给所有子部分。
3. 在每个小节中加一，直到值加起来为 N .此时如果N是 50 和 m是 7，你会得到 8, 7, 7, 7, 7, 7, 7
4. 从 0 迭代到 m-1 ，步进2，在-(currentValue-base)之间添加一个随机数和 currentValue-base .将该数字的倒数添加到其相邻的桶中。如果您有奇数个桶，则在最后一个桶上，不要将该数字的倒数添加到其相邻桶中，而是以类似于上述步骤 2 和 3 的分布式方式将其添加到所有其他桶中。

性能:第 1 步是 O(1) ，步骤 2、3 和 4 是 O(m) ，总的来说是 O(m) .