Для заданного целого числа n
какой алгоритм может разделить его на массив из d
частей, обладающих свойствами, при которых его элементы суммируются с исходным целым числом n
, примерно равными по размеру и достаточно равномерно распределенными по всему массиву? например деление 13 на 10 частей выглядит примерно так:
[1, 1, 2, 1, 1, 2, 1, 1, 2, 1]
В частности, это не должно выглядеть так:
[1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
(неравномерное распределение)
[1, 1, 1, 1, 1, 1, 1, 1, 1, 4]
(примерно не равны по размеру)
Четность членов массива не важна.
В качестве альтернативы можно использовать вариант алгоритма рисования линий Брезенхэма для чередования ваших значений так, как вы хотите. Вам нужно решить, когда принимать n/d
и когда принимать n/d + 1
. Это похоже на алгоритм Брезенхема, который должен решать, когда двигаться только в направлении х, а когда двигаться и в направлении х, и в направлении у.
@Stef нет, это другой вопрос; Меня не волнуют части, кратные 2 или кратные чему-либо, если уж на то пошло.
См., например, код more_itertools.interleave_evenly в python.
Я ответил на свой вопрос ниже, для чего это стоит. Я задал (и ответил) вопрос, потому что я не видел адекватного ответа на свой вопрос в другом месте...
Было ли это «нет» какой-то конкретной вещи, которую я сказал, или всему, что я сказал?
@Stef нет ответа, кратного 2.
Один из способов - использовать динамическое соотношение (a/b
) по отношению к отношению больших значений к малым значениям (c/r
), чтобы определить распределение остатка после деления:
function split(n, d)
{
if (d === 0)
return [];
// Integer division spelled in JavaScript
const q = Math.floor(n / d);
const r = n % d;
const c = d - r;
let out = Array(d);
let a = 1;
let b = 1;
for(let i = 0; i < d; i++)
{
// Make the ratio a/b tend towards c/r
if ((a * r) < (b * c))
{
a++;
out[i] = q;
}
else
{
b++;
out[i] = q + 1;
}
}
// Check the array sums to n
console.info(out, n === out.reduce((a, b) => a + b, 0));
return out;
}
split(11, 10);
split(173, 9);
split(13, 10);
split(1773, 19);
Это производит вывод:
[1, 1, 1, 1, 1, 1, 1, 1, 2, 1], true
[19, 19, 19, 20, 19, 19, 19, 20, 19], true
[1, 1, 2, 1, 1, 2, 1, 1, 2, 1], true
[93, 93, 94, 93, 93, 94, 93, 93, 94, 93, 93, 94, 93, 93, 94, 93, 93, 94, 93], true
Отвечает ли это на ваш вопрос? Разделив четное число на N частей, каждая часть будет кратна 2