[Разминка для мозгов]: взвешенный рандом

Итак, задача написать функцию взвешенного рандома. То есть такого рандома, где частота выпадения элемента зависит от значения его веса.

Например, возьмем двумерный массив размером 4 x 2. Каждый подмассив описывает вес и значение в соответствующем порядке.

int arr[5][2] = {
    {100, 1},
    {200, 2},
    {300, 3},
    {400, 4}
};

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

На большом количестве вызовов функции распределение случайных значений (количество выпадений каждого из них) должно быть приближено к соотношению их весов.

Например, на 20000 вызовах функции с вышеприведенным массивом, число 1 выпадет примерно 2000 раз, число 2 — ~4000, число 3 — ~6000, а 4 — около 8000 раз.

Свои решения пишите прямо в этом топике.

которая будет принимать подобный массив

Размер массива передаётся в функцию?

Не принципиально. Можно хоть std::vector передавать.

Я тут написал, и в результате, результат в среднем колеблется от -23 до +30. Критично? Или так оставлять?
Вот пример запуска:

Please, wait...
Result:
[1] dropped 107 times
[2] dropped 217 times
[3] dropped 294 times
[4] dropped 372 times
[5] dropped 481 times
[6] dropped 597 times
[7] dropped 727 times
[8] dropped 757 times
[9] dropped 914 times
[10] dropped 1034 times

С таким массивом весов и значений.

int arr[10][2] = {
        { 100, 1 },
        { 200, 2 },
        { 300, 3 },
        { 400, 4 },
        { 500, 5 },
        { 600, 6 },
        { 700, 7 },
        { 800, 8 },
        { 900, 9 },
        { 1000, 10 }
    };

UPD на всякий случай убрал код

Код зря убрал, возвращай :)

Код зря убрал, возвращай :)

#include <iostream>
#include <ctime>
#include <cstdlib>

using namespace std;

int weigt_rand( const int arr[][2], int n );

int main()
{
    srand( time(NULL) );

    int arr[10][2] = {
        { 100, 1 },
        { 200, 2 },
        { 300, 3 },
        { 400, 4 },
        { 500, 5 },
        { 600, 6 },
        { 700, 7 },
        { 800, 8 },
        { 900, 9 },
        { 1000, 10 }
    };

    int res[10] = { 0, };

    cout << "Please, wait..." << endl;

    for ( int i = 0; i < 5500; i++ )
        res[weigt_rand( arr, 10 )-1]++;

    cout << "Result: " << endl; 
    for ( int i = 0; i < 10; i++ )
        cout << "[" << i+1 << "] dropped " << res[i] << " times" << endl;

    return 0;
}

int weigt_rand( const int arr[][2], int n )
{
    long long summ = 0;
    for ( int i = 0; i < n; i++ )
        summ += arr[i][0];

    int r = 0 + rand() % summ;
    int prev = 0;

    for ( int i = 0; i < n; i++ )
    {
        if ( r >= prev && r <= arr[i][0] + prev )
           return arr[i][1];

        prev += arr[i][0];
    }
}

Да, все верно. Берем рандом от суммы весов — и берем соответствующий сдвиг в исходном массиве.

Сколько времени ушло вывод на решение? :-)

Сколько времени ушло вывод на решение? :-)

3-6 мин

Мужик.

P.S. Если отвечаешь на предыдущий пост, то цитировать его целиком не нужно :)