0

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

2 ответа 2

3

Пусть есть числа v1, v2, .. vn с вероятностями появления p1, p2, .. pn, Причем p1 + p2 + .. + pn = 1. Тогда достаточно сгенерировать случайное число на полуинтервале [0..1) и посмотреть в какой полуинтервал [p(k-1)..p(k)) оно попадет. Тогда будем считать, что выпало число vk

double rnd(double * v, double * p, int len) {
  double x = rand();
  double sum = 0;
  for (int i = 0; i < len; i++) {
    sum += p[i];
    if (x < sum)
      return v[i];
  }
  return v[len - 1];
}

Исходя из условия

для конкретного числа вероятность того, что функция вернет его, должна быть тем выше, чем меньше это число.

массив p формируется так

void fillProb(double * v, double * p, int len) {
  sort(v);
  double prev = 0;
  for (int i = 0; i < len; i++) {
    double cur = (v[i] - v[0])/(v[len - 1] - v[0]);
    p[i] = 1 - (cur - prev);
    prev = cur;
  }
}
2
  • Спасибо, но конкретно в этой задаче вероятности не рассчитаны, а как их рассчитать я не знаю.
    – h86C1p
    Commented 16 нояб. 2016 в 14:47
  • @h86C1p я указал как Commented 16 нояб. 2016 в 14:48
1

Ну как вариант (для целых чисел, можно для дробных, разница небольшая):

int rand(int[] list)
    int max = max(list) + 1
    int sum = 1
    for (int x: list)
        sum+= max - x
    int rand = rand()%sum
    for (int x: list)
        rand -= max - x 
        if (rand <= 0) return x
2
  • Я правильно понял, что массив должен быть отсортирован?
    – h86C1p
    Commented 16 нояб. 2016 в 14:44
  • @h86C1p не обязательно
    – pavel
    Commented 16 нояб. 2016 в 15:17

Ваш ответ

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

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