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

Question

[rd100]

Есть число 751
Есть 3 человека и нам нужно разделить его в зависимости от рабочих часов, но так, чтобы распределились все средства без остатка.
Например, один работал 12, другой 18, а третий 13 часов.

Answer 1

[Aetae]

function split(sum, ...results) {
  // делим число на общее количество часов
  const part = sum / results.reduce((a, b) => a + b);

  // каждые часы умножаем на результат деления и округляем
  const result = results.map(hours => Math.round(hours * part));

  // финальная сумма с учётом округлений
  const resultSum = result.reduce((a, b) => a + b);

  // разница между финальной суммой и изначальной
  const difference = sum - resultSum;

  // если есть разница
  if(difference) {
    // выбираем рандомно счасливчика\неудачника 
    // за счёт которого компенсируем разницу
    // поменяй если надо выбрать кого-то конкретного :)
    const luckyIndex = Math.floor(Math.random() * result.length);
    result[luckyIndex] += difference;
  }

  return result;
}

Comments

[rd100]

А как все-такие сделать так, чтобы остаток распределился пропорционально?
Т.е. или 2 одному или по 1 двум

[Aetae]

rd100, а пропорционально это как? "2 одному или по 1 двум " - ни о чём не говорит.
Мой алгоритм работает вполне пропорционально на мой вкус - кто больше наработал - тому больше и остатка достаётся.
difference при этом никогда не больше половины количества людей, т.е. равномерно нераспределим.

[Aetae]

rd100, Вот так вы можете сами написать алгоритм распределения остатка, который вам кажется верным):

// алгоритм распределения остатков
function spreadDifference(result, difference) {
  const keys = Object.keys(result);
  const length = keys.length;
  let i = 0;

  // если остаток положительный
  if (difference > 0) {
    // сортируем по убыванию, чтоб лучшие получали прибавку первыми 
    keys.sort((a, b) => result[b] - result[a]);

    // пока остаётся остаток проходимся по сортированным значениям
    while(difference) {
      // difference всегда меньше количества людей
      // потому тут i++ не может убежать за пределы keys
      const index = keys[i++];
      // уменьшаем остаток на единицу
      difference--;
      // увеличиваем результат на единицу
      result[index]++;
    }
  } else {
    // сортируем по возрастанию, чтоб худшие получали минус первыми 
    keys.sort((a, b) => result[a] - result[b]);

    // пока остаётся остаток проходимся по сортированным значениям
    while(difference) {
      // difference всегда меньше количества людей, однако
      // из-за нулей возможно прохождения по keys несколько раз
      const index = keys[i++ % length];

      // результат - ноль, не отнимаем от нуля
      if(result[index] === 0)
        continue;

      // увеличиваем остаток на единицу
      difference++;
      // уменьшаем результат на единицу
      result[index]--;
    }
  }
  return result;
}


function split(sum, ...results) {
  // делим число на общее количество часов
  const part = sum / results.reduce((a, b) => a + b);

  // каждые часы умножаем на результат деления и округляем
  const result = results.map(hours => Math.round(hours * part));

  // финальная сумма с учётом округлений
  const resultSum = result.reduce((a, b) => a + b);

  // разница между финальной суммой и изначальной
  let difference = sum - resultSum;

  // если есть разница
  if(difference)
    spreadDifference(result, difference);

  return result;
}

split(751, 12, 18, 13); // [ 210, 314, 227 ]

[Aetae]

rd100, или как вариант можно работать сразу с первичным остатком:

// алгоритм распределения положительного остатка
function spreadRemainder(result, remainder) {
  // сортируем по убыванию, чтоб лучшие получали прибавку первыми 
  const sortedKeys = Object
    .keys(result)
    .sort((a, b) => result[b] - result[a]);
  const length = sortedKeys.length;
  let i = 0;

  // пока остаётся остаток проходимся по сортированным значениям
  while(remainder) {
    const index = sortedKeys[i++ % length];
    // уменьшаем остаток на единицу
    remainder--;
    // увеличиваем результат на единицу
    result[index]++;
  }

  return result;
}

function split(sum, ...results) {
  // общее количество часов
  const sumResults = results.reduce((a, b) => a + b);
  // целочисленно делим число на общее количество часов
  const part = Math.floor(sum / sumResults);
  // остаток от целочисленного деления
  const remainder = sum % sumResults;

  // каждые часы умножаем на результат деления
  const result = results.map(hours => hours * part);

  // если есть остаток
  if(remainder)
    spreadRemainder(result, remainder);

  return result;
}

split(751, 12, 18, 13); // [ 210, 313, 228 ]

Результаты тут иные, потому что пропорциональность учитывается иначе: тут остаток по всем размазывается равномерно, с небольшим преимуществом лучших, а в предыдущем варианте - больше наработал - больше остатка, и только совсем неделимый(< количества человек) остаток раскидывается равномерно.

Как правильно - никто кроме вас не скажет. Напишите свой алгоритм.)

Answer 2

[Rsa97]

751 / (12 + 18 + 13) = 17.4651
12 * 17.4651 = 209.58
18 * 17.4651 = 314.37
13 * 17.4651 = 227.05

Comments

[rd100]

Там остаток получается 1, а нужно без.
Что бы эти остатки распределились по соотношениям к большему, ведь может остаться не только 1.

[Rsa97]

rd100, 209.58 + 314.37 + 227.05 = 751. Какой остаток?
Или вам нужно, чтобы результат тоже получился целочисленным? Тогда используйте банковское округление, получите 210, 314, 227. В большинстве случаев этого хватает.

[rd100]

Rsa97, тогда на 1-2 больше может получиться