有没有一种有效的算法可以将数字分成N
分段,以便数字之和等于原始数字,并具有最小基数?例如,如果我想将 50 分成 7 个小节,并且最小基数为 2,我可以这样做10,5,8,2,3,5,17
(以及任何其他数量的组合)。我想将数字保留为整数,并且相对随机,但我不确定如何有效地生成总和等于原始值且不包含低于给定最小值的数字。有什么建议么?
编辑-只是为了复制/粘贴我的评论,整数不必是唯一的,但我想避免每次都使用相同的大小(例如 50 分成 10 个相同大小)。
这是一个算法:
- Divide
N
by m
where N
是你的号码并且m
是小节的数量。
- 将结果向下舍入到最接近的值,并将该值分配给所有小节。
- 向每个小节添加 1,直到值总计为
N
。此时如果N
是 50 岁并且m
是 7,你会有 8, 7, 7, 7, 7, 7, 7
- 从 0 迭代到
m-1
,步进2,并在之间添加一个随机数-(currentValue-base)
and currentValue-base
。将该数字的倒数添加到其相邻的存储桶中。如果您有奇数个存储桶,则在最后一个存储桶上,不要将该数字的倒数添加到其相邻的存储桶中,而是以类似于上面的步骤 2 和 3 的分布式方式将其添加到所有其他存储桶中。
表现:
步骤 1 是O(1)
,步骤 2、3 和 4 是O(m)
,所以总体来说是O(m)
.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)