Есть вот такая задача: Сгенерировать массив чисел, сумма которых составит 1. Кол-во чисел вводится с клавиатуры. Решение может быть любое главное получить итоговую сумму 1 (Не желательно большое кол-во нулей)
-
1Числа могут быть любые (положительные/отрицательные)? Или только из интервала [0;1]?– Андрей NOPCommented 27 апр. 2018 в 12:55
-
1Какое должно быть распределение у полученных чисел?– YaantCommented 27 апр. 2018 в 12:56
-
ТС, если вам требуется равномерное распределение, рекомендую рассмотреть ответ @AnT: ru.stackoverflow.com/a/820415/218063– Андрей NOPCommented 28 апр. 2018 в 5:44
5 ответов
Генерируем 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
-переменную во избежание переполнений.
-
Кстати а вот эта идея уже куда интереснее:) кстати на бумаге хорошо решаемая:)– JMNextCommented 27 апр. 2018 в 13:10
-
2@JMNext, этим же способом выполняется нормализация векторов до единичных– test123Commented 27 апр. 2018 в 13:12
-
:) Блиииин как все просто оказалось... А я выдумываю сложные алгоритмы елки палки))– JMNextCommented 27 апр. 2018 в 13:23
-
2Такой подход даст "кособокое" распределение результата. То есть он лучше, чем "много нулей", но на самом деле страдает от той же проблемы, только менее явно. Commented 27 апр. 2018 в 18:03
-
3Если бы вы делили полученные значения на предзаданную константу, то равномерность распределения бы сохранялась, но так как вы делите на сумму самих случайных значений, равномерность теряется. Сумма нескольких случайных величин распределена не равномерно, а нормально. Например, гистограмма суммы
N
бросаний игральной кости имеет хорошо нам знакомую форму колокола. Вот именно на такую неравномерно распределенную случайную величину вы и выполняете деление в вашем варианте . И именно из-за этого теряете равномерность распределения результата. Commented 27 апр. 2018 в 18:34
Вариант с делением на сумму заранее сгенерированных чисел не дает равномерного распределения результата из-за того, что сумма равномерно распределенных величин сама не является равномерно распределенной. А равномерность распределения результата в таких задачах обычно подразумевается.
Более подходящим с точки зрения распределения решением будет следующее: сгенерировать 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;
}
-
1Похоже что это и есть единственный верный ответ в плане равномерности распределения– ZergatulCommented 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.– ZergatulCommented 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
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();
-
Последнее число будет глубоко отрицательное и сильно отличаться от остальных. Не понятно только на сколько это критично для автора. Commented 27 апр. 2018 в 13:21
-
1@АндрейNOP почему будет отрицательное? Тут скорее другая проблема, числа с каждой итераций в среднем будут становиться меньше.– yolosoraCommented 27 апр. 2018 в 13:24
-
@АндрейNOP если первое будет 0.7, то второе не будет больше, чем 0.3– yolosoraCommented 27 апр. 2018 в 13:27
-
Ах, нет, всё правильно. Вы же на max каждый раз умножаете. Понял ваш алгоритм. Но да, хоть числа и не будут отрицательные, но будут все равно не равномерно распределены - дальние числа будут меньше Commented 27 апр. 2018 в 13:28
-
1@АндрейNOP ну в принципе после этого массив можно перемешать :D– yolosoraCommented 27 апр. 2018 в 13:29
Ну, раз ограничений никаких нет, то самое примитивное решение: массив в котором первый элемент равен 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));
-
2Если решение покажется недостаточно случайным, то можно модифицировать алгоритм и сделать 1 не первый элемент, а рандомный. :)– YaantCommented 27 апр. 2018 в 13:12
-
1много нулей как то не очень смотриться. И да ща исправлю. Надо рационально как то сгенерить:)– JMNextCommented 27 апр. 2018 в 13:16
-
@JMNext Да, пожалуй, надо уточнить условие. А то в заголовке про случайные дробные числа, а в тексте они не упоминаются. Commented 27 апр. 2018 в 13:17
-
-
1
Одна из идей - создавать большие целые числа, а затем делить их, к примеру, на 1000. Так у Вас сформируется массив дробных чисел =) Действия выполняемых, пока сумма всех элементов не станет равной 1. Каждое сформированное число нужно проверить: подходит ли оно условию (должно быть меньше разности 1 и сумма остальных элементов массива).
-
-
1великолепное решение, осталось ответить на поставленный вопрос, который заключается в другом– test123Commented 27 апр. 2018 в 12:58
-
4А что, идея хорошая - нагенерировать любых чисел и разделить каждое на сумму всех! Просто автор неудачно сформулировал ответ... Commented 27 апр. 2018 в 12:59
-
Нет, прочитайте что вам Андрей написал, то что вы предлагаете опять не подходит, по критерию "нам надо указать число таких чисел"– test123Commented 27 апр. 2018 в 13:01
-
О нет, автор изменил ответ и его уже понесло не туда... Прочитайте мой предыдущий комментарий. Commented 27 апр. 2018 в 13:01