TonyStark1337
@TonyStark1337

Случайные числа с заданной сумой, какой алгоритм?

Привет, какой алгоритм уже есть или как сделать свой если надо найти 4 рандомных числа сума которых ровна N, допустим x+y+z+m = 100, где каждая больше другой, то есть x > y > z > m. У кого какие мысли ?
  • Вопрос задан
  • 280 просмотров
Решения вопроса 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
x = rand(1, 97);
y = rand(1, 98-x);
z = rand(1, 99-x-y);
result = sort([x, y, z, 100-x-y-z]);
Ответ написан
Seasle
@Seasle Куратор тега JavaScript
Помог - отметь решением \( ゚ヮ゚)/
Вариант 4 - Окончательный.
Возвращает массив уникальных чисел больше нуля отсортированных по убыванию. Имеется проверка на возможность разделения числа на более мелкие.
const sum = array => array.reduce((accumulator, value) => (accumulator += value), 0);

const breakUp = (number, count) => {
  const minimal = (count * (count + 1)) / 2;
  if (minimal > number) {
    throw new Error(`Число ${number} слишком маленькое. Минимальное допустимое число ${minimal}.`);
  }
  const numbers = Array.from({ length: count }, (_, index) => (count - index));

  numbers.forEach((value, index, array) => {
    const total = sum(array);
    const remainder = number - total;
    if (total < number) {
      const random = (index === count - 1)
        ? remainder + value
        : Math.floor(Math.random() * remainder);

      array[index] = random;
    }
  });

  const isUnique = new Set(numbers).size === numbers.length;

  if (!isUnique) {
    return breakUp(number, count);
  } else {
    return numbers.sort((a, b) => (b - a));
  }
};


Другие варианты

Вариант 1.
const breakUp = (number, count) => {
  const numbers = [];

  for (let index = 0; index < count; index++) {
    const random = index === count - 1
      ? number
      : Math.round(Math.random() * number);
    
    numbers.push(random);
    number -= random;
  }

  numbers.sort((a, b) => b - a);

  return numbers;
};

const numbers = breakUp(100, 4);
console.log(numbers); // [76, 15, 6, 3]


Вариант 2.
const breakUp = (number, count) => Array.from({ length: count }, (_, index) => {
  const random = index === count - 1
    ? number
    : Math.round(Math.random() * number);

  number -= random;

  return random;
}).sort((a, b) => b - a);


Вариант 3.
const breakUp = (number, count) => {
  const numbers = new Set();

  while (numbers.size < count) {
    const previousSize = numbers.size;
    const random = numbers.size === count - 1
      ? number
      : Math.floor(Math.random() * number);
    
    numbers.add(random);

    if (previousSize < numbers.size) {
      number -= random;
    }
  }

  return [...numbers.values()].sort((a, b) => b - a);
};

Ответ написан
Пригласить эксперта
Ответы на вопрос 4
@mayton2019
Ent. Software engineer. Oracle. SQL. BigData.
Сортировка не нужна вобщем-то.

Геометрически, задача сводится к генерации 3х случайных точек на отрезке длиной в 100.
Ответ написан
@Karpion
Проблема в том, что сделать у всех трёх чисел равномерное распределение - не получится. Вы бы написали, зачем это нужно.

Мне кажется, надо кинуть на отрезок длины 100 три точки, чтобы разделить его на четыре части. Полученные три числа - отсортировать.

Проблема: числа могут получиться одинаковыми.
Решение: Кидаем три точки на отрезок длиной 94=100-1-2-3. Сортируем отрезки. Потом к первому прибавляем 3, ко второму прибавляем 2, к третьему прибавляем 1 - это если нужны целые числа.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Добавлю экзотическое заполнение.
Можно генерить любые числа рандомно (r) от 0 до 1 и поочерёдно заполнять переменные.
По шагам (на каждой строке r - генерируется только один раз):
1. (x+y+z+m+r<100)?(x+=r):break
2. (y+r<x&&x+y+z+m+r<=100)?y+=r:goto 1
3. (z+r<y&&x+y+z+m+r<=100)?z+=r:goto 1
4. (m+r<z&&x+y+z+m+r<=100)?m+=r:goto 1
5. goto 1

PS: Если избавиться от однотипных переменных в пользу массива, то получим сразу два бонуса:
1. Можно использовать простую рекурсию.
2. Набор количества значений в сумме - полностью произвольно-задаваемый.
Ответ написан
sergiks
@sergiks Куратор тега JavaScript
♬♬
Чтобы соблюсти условие строго-больше, можно записать все слагаемые через их ненулевые разницы.
x > y, значит, x = y + ненулевое_число. Можно так перезаписать слагаемые:
m          = k0 
z = m + k1 = k0 + k1
y = z + k2 = k0 + k1 + k2
x = y + k3 = k0 + k1 + k2 + k3
-----------------------------
m+z+y+x    = 4k0 + 3k1 + 2k2 + k3 = SUM
ki — это натуральные числа от 1.
Получили все k — вычислили x, y, z, m.

Сначала получим k0
Т.к. на k1..k3 уходит минимум 6, когда все по 1,
для k0 остаётся диапазон [1, (SUM - 6) / 4]
при этом k0 должен быть целым.

Выбрав случайный k0 в этом диапазоне,
получаем новую целевую сумму SUM1 = SUM - 4 * k0,
которую нужно заполнить 3k1 + 2k2 + k3 = SUM1

Рекурсия. Но на последнем шаге k3 это весь остаток.

const addUpTo = (top, n) => {
  const getDiffs = (sum, n, acc = []) => {
    if (n === 1) {
      x = sum;
    } else {
      const headroom = (n - 1) * n / 2;
      const cap = Math.floor((sum - headroom) / n);
      if (cap < 1) throw("Impossible. " + JSON.stringify(acc));
      x = 1 + Math.floor(Math.random() * cap);
    }

    acc.push(x);

    if (n <= 1) {
      return acc;
    } else {
      return getDiffs(sum - x * n, n - 1, acc);
    }
  }

  return getDiffs(top, n).map((_, i, a) => a.reduce((acc, c, j) => j <= i ? acc + c : acc)).reverse();
}

addUpTo(100, 4)  /*
[ 34, 30, 21, 15 ]
[ 31, 24, 23, 22 ]
[ 66, 17, 13, 4 ]
[ 47, 22, 21, 10 ]
...
*/

addUpTo(10, 4)  // [ 4, 3, 2, 1 ]
addUpTo(9, 4)   // ошибка, невозможно разложить
Ответ написан
Ваш ответ на вопрос

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

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