| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Случайный елемент массива |
| Автор: ST_Falcon 28.4.2006, 00:18 |
| Есть массив значений [0] - 1203 [1] - 34233 ................. [n] - 23432 нужно выбрать из него случайный елемент. НО вероятность выбора елементов с большими значениями должна быть выше!! и чем больше значение елемента от значений остальных елементов тем больше вероятность выбора елемента с большим значением... |
| Автор: MBo 28.4.2006, 05:34 |
| квадратичная зависимость подойдет? RandIndex := Max(Random(n+1), Random(n+1)); |
| Автор: ST_Falcon 28.4.2006, 17:52 |
| MBo не совсем... тут получается я выбираю максимальный индекс из рендомного диапазона... есть правда вариант прогнать все значения елементов диапазона в цикле и выбрать один из самых больших... сейчас попробую. зы. что больше никто такого не делал? |
| Автор: esperant0 28.4.2006, 19:20 |
| очень просто делаешь так чтобы элемент с значением х выбирался с вероятностью х\ сумма всех значений элементов массива |
| Автор: SoWa 28.4.2006, 19:40 |
| Я вот подумал- дать всем элементам массива равную вероятность, а потом распределять между маленьким и большим элементом массива как нибудь. Например x[1]=5 x[79]=123556 p[1]=0.2 p[79]=0.2 -> p[79]:=p[79]+p[1]/2; p[1]:=p[1]/2; Где p- это вероятность |
| Автор: MBo 29.4.2006, 15:26 |
| ST_Falcon, тебе понятны слова "квадратичная зависимость" ? |
| Автор: esperant0 29.4.2006, 16:47 | ||
Максимум между двумя случайными величинами и квадратичная зависимость суть разные вещи. |
| Автор: popolzen 30.4.2006, 08:21 |
| Предположим, что есть такой массив значений (n = 4): a[1] = 12 a[2] = 4 a[3] = 7 a[4] = 1 Сумма этих элементов равна Sum = a[1] + ... + a[n] Соотнесем с каждым элементом массива еще 2 значения: (b[1] = 0; b[i] = c[i - 1] + 1; c[i] = b[i] + a[i] - 1) b[1] = 0; c[1] = 11 b[2] = 12; c[2] = 15 b[3] = 16; c[3] = 22 b[4] = 23; c[4] = 23 Таким образом, элемент c[n] = sum(a[i]) - 1 Далее делаем Random(Sum), находим это значение в i-м диапазоне [b[i], c[i]] и получаем a[i] с вероятностью, пропорциональной его значению. Для поиска лучше всего использовать специализированные алгоритмы (например, бинарный), имеющие сложность меньше линейной. Надеюсь, я правильно понял твой вопрос. |
| Автор: ST_Falcon 3.5.2006, 19:48 | ||
popolzen
все понял кроме этого момента. делаю рандом по массиву sum и дальше поиск этого значения в массиве а? |
| Автор: Breed 4.5.2006, 07:26 | ||
Random от 0 до Sum/ Попадение этого числа в интервал от b[i] до c[i] получается с вероятностью а[i]. То есть находишь интервал в который попало временное случайное число, и соответствующее a[i] и будет - искомое число. |
