string - "Consolidation"算法名称/实现

Question

不太确定如何描述这个，但我有一个我喜欢玩的文字游戏，我想将其实现为计算机程序。

基本要点是您查看字母的值 (A=1..Z=26)，并将字母合并为尽可能少的字母，并且尽可能彼此接近。

举个例子:

s t a c k

对值求和

19 + 20 + 1 + 3 + 11 = 54

找到最少数量的字母:

ceil(54/26) = 3

选择彼此最接近的字母

54/3 = 18

要显示的字母应该是rrr。

这恰好是一个简单的例子。当您需要 rrs 时(如果您的初始字符串是“堆栈”)，它会是什么样子？

这是否已经有一个我可以查找和实现的名称？

Answer 1

我认为您的问题可以归结为:给定 n 和 k，找到数字 r1、r2 , ..., rk 使得 sum(r1 + r2 + ... + rk) = n 和 max(r1, r2, ..., rk) - min(r1, r2, ..., rk) 越小越好。

解决方案是选择r = floor(n/k)，并将数字的n mod k设置为r + 1 , 以及其余的 r。

例如，如果 n = 55 和 k = 3(您的示例)，我们有 floor(55/3) = 18而 55 mod 3 是 1，所以解是 19, 18, 18。

剩下的就是数字和字母之间的转换。