Наименование / реализация алгоритма «Консолидация»

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.

Все, что остается, - это конвертировать числа и буквы.