分割成数之和组件 [英] Split number into sum components

问题描述

是否有一个有效的算法来一批分成 N 小节，这样的数字的总和加起来原来，用最小基？例如，如果我想要分割成50 7小节，并有2个基地最小，我可以做 10,5,8,2,3,5,17 （组合以及任何其它数目）。我想保持数作为整数，而相对随机的，但我不知道如何有效地生成总结到原来的，不包括数字比给定的最低较低的数字。有什么建议？

Is there an efficient algorithm to split up a number into N subsections so that the sum of the numbers adds up to the original, with a base minimum? For example, if I want to split 50 into 7 subsections, and have a base minimum of 2, I could do 10,5,8,2,3,5,17 (as well as any other number of combinations). I'd like to keep the numbers as integers, and relatively random but I'm not sure how to efficiently generate numbers that sum up to the original and don't include numbers lower than the given minimum. Any suggestions?

编辑 - 只是为了复制/粘贴我的意见，该整数不必是唯一的，但我想，以避免大小相等，为所有这些（如50分成10个同等大小），每次

EDIT - Just to copy/paste my comment, the integers don't have to be unique, but I want to avoid equal sizes for all of them (e.g. 50 split into 10 equal sizes) everytime.

推荐答案

下面是一个算法：

1. 分割 N 按 M ，其中 N 是号和 M 是分段的数量。
2. 回合的结果下到最接近的值并分配该值的所有小节的。
3. 添加一个每个小节，直到值加起来 N 。此时如果 N 50和 M 为7，你有8个，7个，7个，7个， 7，7,7
4. 从1迭代到N，2步，并增加之间的的随机数 - （N-基地）和的N-基。该数的反添加到其相邻的桶。如果有补充说数的反到其相邻桶，它添加到所有其他水桶以类似于步骤2和3以上分布方式的奇数桶，然后在最后一个桶代替

1. Divide N by m where N is your number and m is the number of subsections.
2. Round the result down to its nearest value and assign that value to all of the subsections.
3. Add one to each subsection until the values add up to N. At this point if N was 50 and m was 7, you'd have 8, 7, 7, 7, 7, 7, 7
4. Iterate from 1 to N, stepping by 2, and add a random number between -(N-base) and N-base. Add the inverse of that number to its neighboring bucket. If you have an odd number of buckets, then on the last bucket instead of adding the inverse of that number to its neighboring bucket, add it to all of the other buckets in a distributed manner similar to steps 2 and 3 above.

性能： 第1步是 O（1），步骤2，3和4 O（M），所以总的来说这是 O（M）。

Performance: Step 1 is O(1), Steps 2, 3, and 4 are O(m), so overall it's O(m).

这篇关于分割成数之和组件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！