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

Для заданного целого числа 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
Как настроить Tailwind CSS с React.js и Next.js?
Как настроить Tailwind CSS с React.js и Next.js?
Tailwind CSS - единственный фреймворк, который, как я убедился, масштабируется в больших командах. Он легко настраивается, адаптируется к любому...
LeetCode запись решения 2536. Увеличение подматриц на единицу
LeetCode запись решения 2536. Увеличение подматриц на единицу
Увеличение подматриц на единицу - LeetCode
Переключение светлых/темных тем
Переключение светлых/темных тем
В Microsoft Training - Guided Project - Build a simple website with web pages, CSS files and JavaScript files, мы объясняем, как CSS можно...
Отношения "многие ко многим" в Laravel с методами присоединения и отсоединения
Отношения "многие ко многим" в Laravel с методами присоединения и отсоединения
Отношения "многие ко многим" в Laravel могут быть немного сложными, но с помощью Eloquent ORM и его моделей мы можем сделать это с легкостью. В этой...
В PHP
В PHP
В большой кодовой базе с множеством различных компонентов классы, функции и константы могут иметь одинаковые имена. Это может привести к путанице и...
Карта дорог Беладжар PHP Laravel
Карта дорог Беладжар PHP Laravel
Laravel - это PHP-фреймворк, разработанный для облегчения разработки веб-приложений. Laravel предоставляет различные функции, упрощающие разработку...
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

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