случайный ряд

← →
мс_анатолий (2009-05-08 10:04) [0]

Уважаемый мастера.
Скажите как быстрее получить случайный ряд,
если известны Min,Max, число значений в ряду, среднее арифметическое, хотя бы с 2 знаками после запятой.
Заранее спасибо.
double sum = 0;
double MeanA = 0; //получаемое среднее
double Mean - известное среднее
Array[j] - массив с известным числом записей
Count - число записей

while (Mean != MeanA)
{
sum = 0;
for (unsigned int j = 0; j < Count; j++)
{
Array[j] = GetRandomValue(Min,Max);
sum+=Array[j];
}
MeanA = sum / Count;
}

← →
KSergey © (2009-05-08 10:45) [1]

наверное такой подход даст результат, только вот это условие надо переработать.

while (Mean != MeanA)

При переработке думать вот о чем:
1) Два double числа очень вероятно не равны друг другу, даже если на экране и выглядят одинаково
2) фраза "хотя бы с 2 знаками после запятой" - она не просто так написана в задании. И она ка краз не учтена в реализации, что приводит к неработоспособности. Надо ее реализовать - и счастье будет.

← →
KSergey © (2009-05-08 10:46) [2]

по п.1) читать тут
http://www.delphikingdom.com/asp/viewitem.asp?catalogid=374

← →
Jeer © (2009-05-08 11:23) [3]

> если известны Min,Max, число значений в ряду, среднее арифметическое,
> хотя бы с 2 знаками после запятой.

Если заданы Min и Max, то среднее арифметическое ( мат.ожидание ) уже автоматом получается. При условии, конечно, что распределение симметрично.

← →
Franzy (2009-05-08 11:57) [4]

Создаем массив из случайных чисел в интервале от min до max из нужного кол-ва чисел, а затем вычитаем/прибавляем (так, чтобы не выходить за пределы отрезка) к элементам массива поправки, чтобы получить нужное матожидание. Случайное число + константа - это ведь тоже случайное число ;)

← →
KSergey © (2009-05-08 12:00) [5]

> Jeer © (08.05.09 11:23) [3]
> При условии, конечно, что распределение симметрично.

Такого условия в задаче нет. Зачем выдумывать?

← →
Franzy (2009-05-08 12:01) [6]

З.Ы. Ваш алгоритм не подходит, потому что длина ряда задана, а мой это учитывает.

← →
Дуб © (2009-05-08 12:03) [7]

Array[j] = Mean

И пусть докажут, что это не случайная последовательность.

← →
Franzy (2009-05-08 12:09) [8]

2Дуб
Не сработает, если членов ряда мало.

← →
Дуб © (2009-05-08 12:13) [9]

> Franzy (08.05.09 12:09) [8]

? а что именно не сработает? Среднее будет меньше или как?

← →
Franzy (2009-05-08 12:31) [10]

Вру. Сработает при любом кол-ве, но ряд получится странный. Случайным в ем будет только первое число. Второе должно быть равно 2M-A(1). А третье и все последующие будут равны M. Формально такой ответ, мб, и подходит, а вот по сути - нет.

← →
Дуб © (2009-05-08 12:34) [11]

> Franzy (08.05.09 12:31) [10]

А по сути там и не получится. Ибо элементы ненезависимы. Их сумма задана:)

← →
Jeer © (2009-05-08 12:39) [12]

> KSergey © (08.05.09 12:00) [5]
>
> > Jeer © (08.05.09 11:23) [3]
> > При условии, конечно, что распределение симметрично.
>
> Такого условия в задаче нет. Зачем выдумывать?

Стандартные функции генерации дают симметричное распределение.
Не в курсе ?

← →
TUser © (2009-05-08 13:33) [13]

Кнут, т.3

← →
Дуб © (2009-05-08 13:38) [14]

> TUser © (08.05.09 13:33) [13]

случайные - они во втором.

← →
Franzy (2009-05-08 14:09) [15]

По сути там N-1 случайных чисел, +1, которое получается из суммы остальных. Чувствуете разницу между 1 случайным и N-1, которые получаются из него?

← →
Чайник © (2009-05-08 14:10) [16]

Задача не так проста, как кажется.
Обратите внимание - "известны Min,Max, число значений в ряду, среднее арифметическое".
Если принять равномерное распределение случ.чисел в ряду, то
среднее арифметическое ~ (Min+Max)/2

Если же задано среднее арифметическое "хотя бы с 2 знаками после запятой", значит явно предполагается неравномерное распределение. Мне кажется, вся педагогическая соль этого задания в том и состоит, чтобы найти соответствующую функцию для закона распределения сл.чисел в ряду.

← →
Чайник © (2009-05-08 14:14) [17]

АЛГОРИТМ ГЕНЕРАЦИИ СЛУЧАЙНОЙ ВЕЛИЧИНЫ, ПОДЧИНЯЮЩЕЙСЯ ЗАДАННОМУ ЗАКОНУ РАСПРЕДЕЛЕНИЯ -
http://ps300.narod.ru/fr3d/prob.htm

← →
Сергей М. © (2009-05-08 14:21) [18]

> Задача не так проста, как кажется

У автора кривой язык.

Он, похоже, не в состоянии построить правильно предложение с изложением ИД, которое должно было прозвучать так:

Получить ряд из заданного количества случайных чиcел, принадлежащих заданному диапазону значений, и расчитать среднее арифметическое членов полученного ряда с точностью до 2-х знаков после запятой.

В такой формулировке задача предельно понятна и тривиальна в решении.

← →
Чайник © (2009-05-08 14:25) [19]

> У автора кривой язык.

Ну тады ой - велик могучим русских языков!

← →
Franzy (2009-05-08 14:28) [20]

2Сергей М.
Вам бы в политику, уважаемый :) "Вы задали неправильный вопрос, правильно было спросить вот так". В вашей постановке задача тривиальна, но это ДРУГАЯ задача.

Соль в том, что заданы мин, макс, кол-во и среднее ряда. И нужно составить массив, удовлетворящий данным условиям с заданной точностью.

← →
palva © (2009-05-08 14:30) [21]

> Дуб © (08.05.09 12:03) [7]

дал исчерпывающий и единственный ответ для такой постановки задачи. Обратите внимание, что задано не мат. ожидание членов ряда, а среднее арифметическое ряда. То есть, если считать члены ряда одинаково распределенными случайными величинами, то единственным распределением, которое удовлетворяет условию задачи будет дискретное распределение с одним состоянием равным Meen.

← →
palva © (2009-05-08 14:32) [22]

Любое другое распределение даст случайность среднего арифметического, что противоречит условию задачи.

← →
Franzy (2009-05-08 14:33) [23]

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

← →
Franzy (2009-05-08 14:37) [24]

2palva

Вот вам случайный массив, который удовлетворяет всем условиям задачи, но распределtние у него не mean:

1 3 6 2
(N=4, min =0, max =10, Mean = 3)

> Franzy (08.05.09 14:28) [20]

> заданы мин, макс, кол-во и среднее ряда. И нужно составить
> массив, удовлетворящий данным условиям с заданной точностью

Какой массив-то ? Их же будет множество , каждый из которых удовлетворяет таким условиям..

Сдается мне, мы друг друга не понимаем. Вы задали числовой ряд, то есть реализацию случайного ряда, а не распределение его членов.
Вы можете указать распределение, которому подчиняются его члены?
Ну типа: 1 с вероятностью 0.2, 2 с вероятностью 0.3, 3 с вероятностью 0.2, 6 с вероятностью 0.3. Что бы вы ни задали, среднее арифметическое не будет равно 3 с вероятностью единица.

← →
Franzy (2009-05-08 14:55) [27]

Короче, алгоритм:
Пусть заданы MIN, MAX, N, MEAN, EPS (требуемая точность)

1) Составляем массив A из N случайных чисел из интервала [MIN,MAX]
2) Вычисляем ср. арифм массива = X
3) Пускаем цикл, выполняющийся, пока не будет выполнено условие abs(X-MEAN)<=EPS. Внутри цикла:
3.1 Вычисляем невязку Y=(MEAN-X)*N;
3.2 Выбираем случайный элемент массива (i). Делаем A(i) =A(i)+Y
3.3 Проверяем выход за пределы интервала: если A(i)>MAX, то A(i)=MAX; если A(i)<MIN, то A(i)=MIN
3.4 Вычисляем новое среднее X.

По-моему, предельно просто, быстро и эффективно. Быстрее будет только если запоминать уже измененные элементы массива и больше их не использовать (они и так уже будут максимизированы/минимизированы). Экстремалы вообще могут не случайный выбор использовать, а по порядку перебирать :)

З.Ы. Если MEAN не принадлежит интервалу [MIN,MAX], алгоритм уйдет в бесконечный цикл, иначе подходящий массив будет составлен не более чем за N итераций (в самом худшем случае).

← →
Franzy (2009-05-08 14:58) [28]

> Сдается мне, мы друг друга не понимаем. Вы задали числовой
> ряд, то есть реализацию случайного ряда, а не распределение
> его членов.

Раз это программерская задача, то явно требуется написать процедуру, которая выдает такие случайные ряды, а не придумывает распределения...

> требуется написать процедуру, которая выдает такие случайные ряды

Дуб вам уже дал такую процедуру, которая гораздо проще и к тому же дает равенство Mean и среднего арифметического абсолютно точно. Если допускается погрешность для Mean и требовалась бы ненулевая дисперсия, то тоже существует гораздо более простая процедура порождения ряда, - это брать члены согласно равномерному распределению на отрезке [Mean-Eps, Mean+Eps]. Но ненулевой дисперсии в задаче не требуется.

Вот такая забавная фигня получается пока.

procedure FillRandomSum(var A: array of Double; AMin, AMax, AMean: Double); procedure FillR(L, R: Integer; ASum: Double); var SL, SR: Double; M, NL, NR: Integer; MinL, MaxL: Double; begin if L = R then A[L] := ASum else begin M := (L + R) div 2; NL := M - L + 1; NR := R - M; MinL := Max(NL * AMin, ASum - NR * AMax); MaxL := Min(NL * AMax, ASum - NR * AMin); //пляски с бубном и ненаучным тыком для получения более-менее равномерного распределения repeat SL := RandG((MaxL + MinL)/2, (MaxL - MinL)/(NL*Sqrt(NL))); until (SL >= MinL) and (SL <= MaxL); SR := ASum - SL; FillR(L, M, SL); FillR(M + 1, R, SR); end; end; var i, j: Integer; Temp: Double; begin FillR(0, High(A), AMean * Length(A)); //перемешаем for i := High(A) downto 1 do begin Temp := A[i]; j := Random(i + 1); A[i] := A[j]; A[j] := Temp; end; end;

Franzy
Давайте, кстати, разберем ваш алгоритм. Дает он одинаково распределенные величины? Конечно дает. Каким будет распределение вероятности? Попробуем вычислять плотность эмпирически, частотно. Разобьем [Min, Max] на небольшие отрезки и будем подсчитывать частоту попаданий в каждый отрезок. В пределе при стремлении к бесконечности мы получим плотность распределения. Так вот, ненулевая плотность получится только на отрезках покрываемых отрезком [Mean-Eps, Mean+Eps] в противном случае была бы ненулевая вероятность выхода среднего арифметического за пределы этого отрезка.

В то же время любая плотность вероятности, носитель которой покрывается отрезком [Mean-Eps, Mean+Eps] удовлетворяет условию задачи. Конечно, здесь остается следующий парадокс: случайная величина у нас может принимать какое-то значение на отрезке, на который она должна попадать с нулевой вероятностью. Но таких парадоксов в теории вероятностей пруд пруди.

← →
Franzy (2009-05-08 16:07) [32]

> Дуб вам уже дал такую процедуру, которая гораздо проще и
> к тому же дает равенство Mean

Да, но она выдает нужный результат лишь формально, а не по сути. Случайным будет лишь первое число ряда. А последние и вовсе все одинаковые будут. Практический смысл такого ряда?

> Практический смысл такого ряда?

Я согласен, что у вас гораздо больше здравого смыла, чем у меня. Но с другой стороны, разве автор объяснил нам практический смысл? Зачем он скрестил случайные величины и фиксированное среднее арифметическое? Почему он не взял мат.ожидание? Вы же пресекли попытки объяснить автору, чего он на самом деле хочет. А идиотски поставленная задача имеет идиотское решение.

← →
Franzy (2009-05-08 17:06) [34]

Будучи преподом, принимающим у студентов лабы по информатике, я научился воспринимать объяснения в любых, самых идиотских вариантах :)

> Franzy (08.05.09 16:07) [32]
> Да, но она выдает нужный результат лишь формально, а не
> по сути. Случайным будет лишь первое число ряда. А последние
> и вовсе все одинаковые будут. Практический смысл такого
> ряда?

Очень простой - он верен. В любом другом случае будет совершенно элементарно показать, что получаемый вами массив вовсе не совсем случаен - за подробностями к Кнуту, например. О чем вам и толкует и пробует объяснить palva.

Есть простые иилюстрации к подобному.

> Franzy (08.05.09 17:06) [34]
> Будучи преподом, принимающим у студентов лабы по информатике,
> я научился воспринимать объяснения в любых, самых идиотских
> вариантах :)

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

Тогда да, тогда мой вариант отпадает, безусловно. :)

> Да, но она выдает нужный результат лишь формально, а не
> по сути.

Вот как? 2*2=4 это формально, а по сути понятно 5.

> Случайным будет лишь первое число ряда. А последние и вовсе
> все одинаковые будут.

Ну и? Вы хотите к случайным последовательностям применить критерии обсуждаемые во втором томе Кнута? Так уверяю вас - ваши построения их и вовсе не пройдут. Ибо сумма задана, а соответвенно поведение ваших членов не может быть полностью случайным.

А насчет случайного. Есть вот, например задача - случайным образом распределить числа от 1 до 1000000 в массиве с миллионом элементов.

Нормальный способ - он у того же Кнута описан. Но иногда, новички используют другие методы. Например, заполняют массив сначала его индексами, а потом бегут от начала до середины и меняют местами числа из первой части со случайными элементами из второй. Очевидно, что все идет насмарку. Кстати, также пойдет и на смарку, если бежать по четным и производить случайно замену с нечетными. И т.д и т.п. Случайность - это не так просто.

Хотя ради зачета, истиной можно и покривить. Зачет же. Именно по этому я не стал приводить правдоподобные примеры решения. Борис же такой грех на душу взял - сделал кому-то к зачету задачку. Теперь авор должен будет часть корочки от диплома принести МВо.

случайный ряд Найти похожие ветки