dollar
@dollar
Делай добро и бросай его в воду.

Как распределить значение по ячейкам примерно равномерно?

Есть массив чисел, его размер N.
Числа произвольные от 0 до 1.
Нужно разбить число X на N мелких чисел, и прибавить к каждому элементу массива так, чтобы каждый не превышал 1.

Сложность составляет именно последнее условие. Так-то можно было бы просто посчитать мелкое число как:
x = X / N
И дальше к каждому элементу массива прибавить по x.
Но что если хотя бы какой-то элемент будет 1 или близкий к 1? Тогда этот x (или ту часть, что высовывается за единицу) придётся снова бить между оставшимися. И получается как-то не понятно и не эффективно.
  • Вопрос задан
  • 93 просмотра
Решения вопроса 1
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Для каждой ячейки известна её оставшаяся до потолка 1 «ёмкость».

Сложить ёмкости = capacity вместимость всего массива.
Если X > capacity — «невпихуемо!» — задача не имеет решения.

Коэффициент k = X / capacity меньше или равен 1.
Идти по ячейкам, откусывать от X в очередную кусочек, пропорционально ёмкости этой ячейки с коэфф. k.

Так в каждую доложат пропорционально её ёмкости, сглаживая неравномерность заполнения.
шесть строк на JS
const spread = (value, arr) => {
  const CELL_MAX = 1;
  const sum = arr.reduce((acc, c) => acc + c);
  const capacity = arr.length * CELL_MAX - sum;
  if (value > capacity) throw new Error("Value won't fit");
  const k = value / capacity;
  return arr.map(el => el + (CELL_MAX - el) * k);
}

spread(0.2, [ 0.1, 0.1 ]) // [ 0.2, 0.2 ]
spread(0.2, [ 0.1, 0.99 ]) // [ 0.29780219780219785, 0.9921978021978022 ]
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
function distribute(arr, val) {
  let n = arr.length;
  let dVal = val;
  while (dVal > 0) {
    let d = dVal / n;
    dVal = 0;
    for (let i = 0; i < arr.length; i += 1) {
      if (arr[i] === 1) {
        continue;
      }
      arr[i] += d;
      if (arr[i] < 1) {
        continue;
      }
      dVal += arr[i] - 1;
      arr[i] = 1;
      n -= 1;
      if (n === 0) {
        return undefined;
      }
    }
  }
  return arr;
}
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы