Как разделить целое число на массив примерно равных и равномерно распределенных частей, сумма которых равна исходному целому числу?

Для заданного целого числа 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 частей, каждая часть будет кратна 2

Stef 18.11.2022 15:07

В качестве альтернативы можно использовать вариант алгоритма рисования линий Брезенхэма для чередования ваших значений так, как вы хотите. Вам нужно решить, когда принимать n/d и когда принимать n/d + 1. Это похоже на алгоритм Брезенхема, который должен решать, когда двигаться только в направлении х, а когда двигаться и в направлении х, и в направлении у.

Stef 18.11.2022 15:10

@Stef нет, это другой вопрос; Меня не волнуют части, кратные 2 или кратные чему-либо, если уж на то пошло.

Tim Angus 18.11.2022 15:11

См., например, код more_itertools.interleave_evenly в python.

Stef 18.11.2022 15:12

Я ответил на свой вопрос ниже, для чего это стоит. Я задал (и ответил) вопрос, потому что я не видел адекватного ответа на свой вопрос в другом месте...

Tim Angus 18.11.2022 15:12

Было ли это «нет» какой-то конкретной вещи, которую я сказал, или всему, что я сказал?

Stef 18.11.2022 15:12

@Stef нет ответа, кратного 2.

Tim Angus 18.11.2022 15:13
Структурированный массив Numpy
Структурированный массив Numpy
Однако в реальных проектах я чаще всего имею дело со списками, состоящими из нескольких типов данных. Как мы можем использовать массивы numpy, чтобы...
T - 1Bits: Генерация последовательного массива
T - 1Bits: Генерация последовательного массива
По мере того, как мы пишем все больше кода, мы привыкаем к определенным способам действий. То тут, то там мы находим код, который заставляет нас...
Что такое деструктуризация массива в JavaScript?
Что такое деструктуризация массива в JavaScript?
Деструктуризация позволяет распаковывать значения из массивов и добавлять их в отдельные переменные.
1
7
104
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Один из способов - использовать динамическое соотношение (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

Другие вопросы по теме