11

Есть вот такая задача: Сгенерировать массив чисел, сумма которых составит 1. Кол-во чисел вводится с клавиатуры. Решение может быть любое главное получить итоговую сумму 1 (Не желательно большое кол-во нулей)

3
  • 1
    Числа могут быть любые (положительные/отрицательные)? Или только из интервала [0;1]? Commented 27 апр. 2018 в 12:55
  • 1
    Какое должно быть распределение у полученных чисел?
    – Yaant
    Commented 27 апр. 2018 в 12:56
  • ТС, если вам требуется равномерное распределение, рекомендую рассмотреть ответ @AnT: ru.stackoverflow.com/a/820415/218063 Commented 28 апр. 2018 в 5:44

5 ответов 5

23

Генерируем N любых неотрицательных чисел.
Вычисляем их сумму.
Делим каждое на эту сумму.

Пример реализации:

int count = 10;
Random random = new Random();
int[] integers = new int[count];
long sum = 0;
for (int i = 0; i < count; ++i)
{
    integers[i] = random.Next();
    sum += integers[i];
}
double[] doubles = new double[count];
for (int i = 0; i < count; ++i)
    doubles[i] = (double)integers[i] / sum;
Console.WriteLine(string.Join("\n", doubles));
Console.WriteLine(doubles.Sum());

random.Next() возвращает неотрицательное случайное целое число.
Для накопления суммы берем long-переменную во избежание переполнений.

9
  • Кстати а вот эта идея уже куда интереснее:) кстати на бумаге хорошо решаемая:)
    – JMNext
    Commented 27 апр. 2018 в 13:10
  • 2
    @JMNext, этим же способом выполняется нормализация векторов до единичных
    – test123
    Commented 27 апр. 2018 в 13:12
  • :) Блиииин как все просто оказалось... А я выдумываю сложные алгоритмы елки палки))
    – JMNext
    Commented 27 апр. 2018 в 13:23
  • 2
    Такой подход даст "кособокое" распределение результата. То есть он лучше, чем "много нулей", но на самом деле страдает от той же проблемы, только менее явно. Commented 27 апр. 2018 в 18:03
  • 3
    Если бы вы делили полученные значения на предзаданную константу, то равномерность распределения бы сохранялась, но так как вы делите на сумму самих случайных значений, равномерность теряется. Сумма нескольких случайных величин распределена не равномерно, а нормально. Например, гистограмма суммы N бросаний игральной кости имеет хорошо нам знакомую форму колокола. Вот именно на такую неравномерно распределенную случайную величину вы и выполняете деление в вашем варианте . И именно из-за этого теряете равномерность распределения результата. Commented 27 апр. 2018 в 18:34
14

Вариант с делением на сумму заранее сгенерированных чисел не дает равномерного распределения результата из-за того, что сумма равномерно распределенных величин сама не является равномерно распределенной. А равномерность распределения результата в таких задачах обычно подразумевается.

Более подходящим с точки зрения распределения решением будет следующее: сгенерировать N-1 неубывающих равномерно распределенных случайных чисел в диапазоне [0, 1]

r1 ≤ r2 ≤ r3 ≤ ... ≤ rN-1

затем положить r0 = 0 и rN = 1 и в качестве искомых чисел взять попарные разности в соседях

r1 - r0, r2 - r1, r3 - r2, ..., rN - rN-1

На C++

#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>

int main()
{
  unsigned N = 10;
  std::vector<unsigned> r(N + 1);

  r.front() = 0;
  std::generate(r.begin() + 1, r.end() - 1, std::rand);
  std::sort(r.begin() + 1, r.end() - 1);
  r.back() = RAND_MAX;

  for (unsigned i = 1; i <= N; ++i)
    std::cout << double(r[i] - r[i - 1]) / RAND_MAX << " ";

  std::cout << std::endl;
}
9
  • 1
    Похоже что это и есть единственный верный ответ в плане равномерности распределения
    – Zergatul
    Commented 29 апр. 2018 в 2:02
  • @Zergatul, а что вы имеете ввиду под равномерностью? Я вот сгенерировал тремя способами миллион раз пакет из 10 чисел и получил такую картинку: 1, 2. А вот здесь пакеты по 100 чисел: 3. Как видно, мой алгоритм дает примерно равное количество чисел на начальном интервале (от 0 до 0,15). Алгоритм yolosora дает очень много мелких чисел. Алгоритм AnT дает тем меньше чисел, чем они больше, но не так много мелких как предыдущий. Commented 22 мая 2018 в 13:50
  • @АндрейNOP Смотрите, возьмем самый простой вариант задачи, сгенерить 2 числа, чья сумма = 1. Какой самый интуитивно верный ответ? Взять и разрезать интервал [0, 1) в случайном месте. Что и делает AnT. Ваш алгоритм будет генерировать числа ближе к 0.5 чаще. А теперь что не так с yolosora. Его алгоритм не зависит от количества чисел. Возьмем 10 чисел. По его алгоритму получается, что вероятность появления числа 0.9 на первой итерации равна 0.1. Возьмем 1000 чисел. Снова та же самая вероятность появления 0.9.
    – Zergatul
    Commented 22 мая 2018 в 14:27
  • В общем это зависит от потребности ТС, если он генерирует 10 чисел и хочет чтобы они были близки к 0.1, то мой алгоритм ему больше пойдет. Правда, в идеале тогда ему нужен алгоритм default locale :D Commented 22 мая 2018 в 14:40
  • 1
    @VTT: Я уже давал ссылку: en.wikipedia.org/wiki/Irwin%E2%80%93Hall_distribution. Сумма равномерно распределенных - это распределение Ирвина-Холла, очень похожее на нормальное. На равномерное вообще не похоже. Commented 5 июн. 2018 в 14:59
10

rnd - Random

 static double[] Generate(int count)
 { 
    var result = new double[count];
    var max = 1.0;
    for (int i = 0; i < count - 1; i++)
    {
       result[i] = rnd.NextDouble() * max;
       max -= result[i];
    }
    result[count-1] = max;
    return result;
 }

Дополнительно массив можно перемешать если критично то, что при такой генерации в среднем следующее значение становится меньше предыдущего. Пример простого перемешивания:

result.OrderBy(x => rnd.Next()).ToArray();

9
  • Последнее число будет глубоко отрицательное и сильно отличаться от остальных. Не понятно только на сколько это критично для автора. Commented 27 апр. 2018 в 13:21
  • 1
    @АндрейNOP почему будет отрицательное? Тут скорее другая проблема, числа с каждой итераций в среднем будут становиться меньше.
    – yolosora
    Commented 27 апр. 2018 в 13:24
  • @АндрейNOP если первое будет 0.7, то второе не будет больше, чем 0.3
    – yolosora
    Commented 27 апр. 2018 в 13:27
  • Ах, нет, всё правильно. Вы же на max каждый раз умножаете. Понял ваш алгоритм. Но да, хоть числа и не будут отрицательные, но будут все равно не равномерно распределены - дальние числа будут меньше Commented 27 апр. 2018 в 13:28
  • 1
    @АндрейNOP ну в принципе после этого массив можно перемешать :D
    – yolosora
    Commented 27 апр. 2018 в 13:29
6

Ну, раз ограничений никаких нет, то самое примитивное решение: массив в котором первый элемент равен 1, а остальные — 0.

int n = 5;
var arr = new decimal[n];
arr[0] = 1;

ОБНОВЛЕНИЕ: Добавлено уточнение, что много нулей нежелательно. Из-за этого решение не подходит.

Вариант №2: Заполняем массив значениями 1/n:

int n = 6;
var value = 1.0m/n;
var arr = Enumerable.Repeat(value, n).ToArray();

Тут возникает проблема: из-за ошибок округления при делении, сумма может не сойтись. Для того, чтобы сумма сошлась компенсируем первый элемент:

arr[0] = 1-(value*(n-1));
5
  • 2
    Если решение покажется недостаточно случайным, то можно модифицировать алгоритм и сделать 1 не первый элемент, а рандомный. :)
    – Yaant
    Commented 27 апр. 2018 в 13:12
  • 1
    много нулей как то не очень смотриться. И да ща исправлю. Надо рационально как то сгенерить:)
    – JMNext
    Commented 27 апр. 2018 в 13:16
  • @JMNext Да, пожалуй, надо уточнить условие. А то в заголовке про случайные дробные числа, а в тексте они не упоминаются. Commented 27 апр. 2018 в 13:17
  • @Yaant Ну это уже будет полный хаос и неразбериха. Commented 27 апр. 2018 в 13:18
  • 1
    Эх, не хотел бы я быть вашим заказчиком ;) Commented 27 апр. 2018 в 13:36
3

Одна из идей - создавать большие целые числа, а затем делить их, к примеру, на 1000. Так у Вас сформируется массив дробных чисел =) Действия выполняемых, пока сумма всех элементов не станет равной 1. Каждое сформированное число нужно проверить: подходит ли оно условию (должно быть меньше разности 1 и сумма остальных элементов массива).

6
  • и он будет равен 1? Commented 27 апр. 2018 в 12:58
  • 1
    великолепное решение, осталось ответить на поставленный вопрос, который заключается в другом
    – test123
    Commented 27 апр. 2018 в 12:58
  • 4
    А что, идея хорошая - нагенерировать любых чисел и разделить каждое на сумму всех! Просто автор неудачно сформулировал ответ... Commented 27 апр. 2018 в 12:59
  • Нет, прочитайте что вам Андрей написал, то что вы предлагаете опять не подходит, по критерию "нам надо указать число таких чисел"
    – test123
    Commented 27 апр. 2018 в 13:01
  • О нет, автор изменил ответ и его уже понесло не туда... Прочитайте мой предыдущий комментарий. Commented 27 апр. 2018 в 13:01

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.