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
    16 ноя 2016 в 14:47
  • @h86C1p я указал как 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
    16 ноя 2016 в 14:44
  • @h86C1p не обязательно
    – pavel
    16 ноя 2016 в 15:17

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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