Rand с различной вероятностью?

Question

[Klef]

Здравствуй мой любимый хаб «ненормальное программирование»

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

Условие: есть последовательность, от 1 до 100, необходимо выбрать случайным образом число из этой последовательности, но так, что бы у 1 был наименьший приоритет выбора а у 100 максимальный.



Решение у меня есть (даже два, одно программистское (нашел сам), второй математическое (это уже подсказали товарищи)

Вот картинка демонстрирующая:



по X последовательность от 1 до 100

по Y шанс выпадения

белая — чистый рандом

красная — прог решение

зеленая — математическая

серая — ноль, для чистоты эталона



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

Все предложения могу добавить на график. для проверки.

Завтра к вечеру покажу что у меня есть за варианты.



upd: добавил время затраченное на просчет.

Comments

[nonbody]

for($i=0; $i<1000; $i++){
$chance = 30;
if (rand(1,100)<=$chance){
echo "yeah\r\n";
}else{
echo "no chance\r\n";
}
}

Вот простейший способ оказывается

Answer 1

[agmt]

Если плотность вероятности равномерно возрастает, значит функция распределения возрастает по параболе. Значит в итоге нужное число можно получить по формуле «1+sqrt(rnd(10000))».

Comments

[agmt]

А, именно это и было предложено чуть выше, только без прибавления «1».

[Klef]

добавил на график.
и данный ответ совпадает с математическим.

[pxx]

Это первое, что пришло в голову, но потом я начал мудрить с вероятностями и окончательно себя запутал.

Answer 2

[MiXei4]

Генерируем число от 1 до суммы арифметической прогрессии от 1 до 100 = 5050.
Получаем x. Далее считаем при каком минимальном числе y число x окажется меньше суммы арифметической прогрессии от 1 до y.

Смысл такой — выпадает 1 — ответ 1, выпадает 2 или 3 — ответ 2, выпадает 4, 5, 6 — ответ 3 и тд

Comments

[Klef]

собираем массив, так пошел я.
а потом ранд из массива.

[agmt]

Именно так, для дискретного случая этот метод более точно подходит, чем предложенный мной.

Answer 3

[Klef]

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

Comments

[waragarf]

Привет, у меня возник возможно глупый вопрос возможно ли сделать приоритетом не наибольшее число а наибольшее и наименьшее например в чтобы вашей же последовательности приоретет отдавался сначала или 1 или 100 потом или 2 или 99 и тд?

Answer 4

[NiGHt_LEshiY]

Первое что пришло в голову — ideone.com/HO6sF0
Моих знаний математики и алгоритмов явно не хватает, но… это хотя бы примерно правильное направление мысли?

Comments

[Klef]

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

[NiGHt_LEshiY]

Чуть упрощённый вариант на С — ideone.com/YWaxut
На PHP — ideone.com/vbv0qa

[Klef]

2 NiGHt_LEshiY дайте все таки Коментарии, каюсь я не могу понять, зачем вам цикл до милиона, если результат нужен от 1 до 100

[agmt]

Цикл до миллиона — проверка.

[Klef]

цикл меня сбил с толку :(

Answer 5

[nonbody]

for($i=0; $i<1000; $i++){
$chance = 30;
if (rand(1,100)<=$chance){
echo "yeah\r\n";
}else{
echo "no chance\r\n";
}
}

Вот простейший способ оказывается

Answer 6

[livestd]

var getr=function (len){
sqr=Math.pow(len,2);
rnd=Math.random() * (sqr);
sqrt=Math.sqrt(rnd);
frnd=Math.floor(sqrt);
return frnd;
}
var arr=[0,0,0,0,0,0,0,0,0,0,0,0];
for (var i=0;i<=10000;i++){
arr[getr(12)]+=1;
if (i>=10000)
console.log(arr);
}