Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 65, средняя оценка - 4.68
SIvan
3 / 3 / 1
Регистрация: 10.05.2011
Сообщений: 19
#1

Генерация случайных чисел в заданном диапазоне. - C++

18.07.2011, 18:11. Просмотров 8449. Ответов 21
Метки нет (Все метки)

Здесь сказано
Не используйте % (получение остатка от деления) для ограничения получаемых случайных чисел. Это не самый лучший метод получения случайных чисел определенного диапазона значений
Почему?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.07.2011, 18:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Генерация случайных чисел в заданном диапазоне. (C++):

Генерация случайных чисел на заданном диапазоне - C++
Здравствуйте, прошу прощения, если такая тема уже проскакивала. Есть простой генератор чисел (алгоритм Леммера): #include...

Генерация случайных чисел в диапазоне 0 - 1 - C++
Привет. Прошу помочь с рандомными числами. Нужны числа от 0 или 1

Генерация случайных вещественных чисел в диапазоне 0..1 - C++
Какнить можно заставить rand() работать по аналогии в Паскале, т.е. выдавать числа от 0 до 1 (0,000000054, 0,743325235, 0,0052411 и...

Генерация псевдослучайных чисел в заданном диапазоне - C++
Датчики случайных чисел можно привлекать при подборе проверочных исходных данных для программ. Получить с помощью датчика случайных...

Генерация случайных чисел типа double во всем диапазоне - C++
Нужна помощь в написании программы, генерирующей псевдослучайные числа типа double на всем диапазоне, используя функцию rand(). Я пытался...

Сформировать массив случайных целых чисел в заданном диапазоне - C++
Такая вот задачка не получается решить(написать) её. (хочу понять-разобраться что и как) Сформировать массив А из 20 случайных целых...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
sandye51
программист С++
684 / 586 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
18.07.2011, 18:32 #2
мне кажется это бред)
0
Kastaneda
Форумчанин
Эксперт С++
4653 / 2862 / 228
Регистрация: 12.12.2009
Сообщений: 7,271
Записей в блоге: 2
Завершенные тесты: 1
18.07.2011, 18:46 #3
Цитата Сообщение от sandye51 Посмотреть сообщение
мне кажется это бред)
А мне нет!



Я думаю так:

Рассмотрим такой подход:
C++
1
int a=rand()%100;//получаем число от 0 до 99
при таком подходе очень высокая вероятность повторения получаемого числа, даже если rand() будет каждай раз возвращать неповторяющиеся числа. Т.е. при rand()=150 и rand()=250 (350, 450 и т.д.) мы получим число 50 (а в диапазоне от 0 до RAND_MAX у нас очень большая вероятность получить одинаковые числа), что, естественно, нам не нужно.
А так, как показанно по ссылке:
C++
1
2
3
4
5
6
7
8
int randomNumber(int hi)  // Правильный генератор случайных чисел для области значений [0,hi]
    {
       // Получение области значений [0,1)
       const float scale = rand()/float(RAND_MAX);
 
       // Возврат значения в области значений [0,hi]
       return int(scale*hi + 0.5); // неявное приведение типа и отброс дробной части числа
    }
повторяющееся число мы имеем шанс получить только, если rand() вернула число, которое уже было. При всех других значениях числа повторяться не будут (это исключено логикой получения числа).
Поэтому, при желании получить много случайных чисел в нужном диапазоне, вариант 2 конечно предпочтительней.
1
An1ka
65 / 70 / 2
Регистрация: 30.06.2011
Сообщений: 176
18.07.2011, 18:48 #4
Ну подобные генераторы не совершенны... и генерируют они псевдослучайные числа, у которых дальнейшая генерация полностью зависит от первой инициализации seed.
C
1
void srand ( unsigned int seed);
0
Kastaneda
Форумчанин
Эксперт С++
4653 / 2862 / 228
Регистрация: 12.12.2009
Сообщений: 7,271
Записей в блоге: 2
Завершенные тесты: 1
18.07.2011, 18:51 #5
Цитата Сообщение от An1ka Посмотреть сообщение
Ну подобные генераторы не совершенны... и генерируют они псевдослучайные числа, у которых дальнейшая генерация полностью зависит от первой инициализации seed.
C
1
void srand ( unsigned int seed);
Ну об этом речи нет, мы же о другом говорим.
А действительно случайное число можно получить используя аппаратные генераторы.
0
easybudda
Модератор
Эксперт CЭксперт С++
9627 / 5575 / 947
Регистрация: 25.07.2009
Сообщений: 10,710
18.07.2011, 20:22 #6
По-моему это из маразматического шаманства что-то... Просто из любопытства сделал вот такую штуку
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
    
#define NUM_TESTS 100000000
    
int randomNumber(int hi)  // Правильный генератор случайных чисел для области значений [0,hi]
{
    // Получение области значений [0,1)
    const float scale = rand()/(float)RAND_MAX;
 
    // Возврат значения в области значений [0,hi]
    return (int)(scale*hi + 0.5); // неявное приведение типа и отброс дробной части числа
}
    
int main(void){
    int counters[2][10] = { 0 }, i;
    
    srand(time(NULL));
    for ( i = 0; i < NUM_TESTS; ++i ){
        ++counters[0][rand() % 10];
        ++counters[1][randomNumber(9)];
    }
    
    printf("Distribution of %d numbers from 0 to 9:\n", NUM_TESTS);
    printf("#       Use %%          Use function\n");
    for ( i = 0; i < 10; ++i )
        printf("%d%15d%15d\n", i, counters[0][i], counters[1][i]);
    
    return 0;
}
вывела
Код
C:\cpp\other>gcc -o many_randoms many_randoms.c

C:\cpp\other>many_randoms.exe
Distribution of 100000000 numbers from 0 to 9:
#       Use %          Use function
0       10003390        5555490
1       10001169       11105983
2       10001368       11105353
3        9994094       11111500
4        9997676       11117890
5       10003123       11113689
6       10001206       11113432
7       10003832       11104756
8        9996405       11116064
9        9997737        5555843

C:\cpp\other>many_randoms.exe
Distribution of 100000000 numbers from 0 to 9:
#       Use %          Use function
0        9995435        5553140
1       10004696       11115578
2       10001687       11104934
3       10003189       11114208
4       10000565       11116535
5       10000915       11108100
6       10002122       11110761
7        9999504       11105725
8       10000108       11112267
9        9991779        5558752

C:\cpp\other>many_randoms.exe
Distribution of 100000000 numbers from 0 to 9:
#       Use %          Use function
0        9997536        5555975
1       10003821       11110893
2        9998371       11113640
3        9998315       11113127
4       10002654       11107470
5       10002168       11110817
6       10001548       11110728
7        9997697       11105850
8        9999866       11111303
9        9998024        5560197

C:\cpp\other>
Если я правильно понимаю, значение каждого счётчика должно к 10000000 стремиться, так с оператором % оно как-то лучше получилось...
1
Kastaneda
Форумчанин
Эксперт С++
4653 / 2862 / 228
Регистрация: 12.12.2009
Сообщений: 7,271
Записей в блоге: 2
Завершенные тесты: 1
18.07.2011, 20:32 #7
Цитата Сообщение от easybudda Посмотреть сообщение
Если я правильно понимаю, значение каждого счётчика должно к 10000000 стремиться
Почему?
0
easybudda
Модератор
Эксперт CЭксперт С++
9627 / 5575 / 947
Регистрация: 25.07.2009
Сообщений: 10,710
18.07.2011, 20:37 #8
Цитата Сообщение от Kastaneda Посмотреть сообщение
Почему?
Потому, что на 100000000 испытаний при равномерном распределении каждого из 10 чисел от 0 до 9 должно получаться по 100000000 / 10 = 10000000 штук, нет?
0
Kastaneda
Форумчанин
Эксперт С++
4653 / 2862 / 228
Регистрация: 12.12.2009
Сообщений: 7,271
Записей в блоге: 2
Завершенные тесты: 1
18.07.2011, 20:43 #9
Цитата Сообщение от easybudda Посмотреть сообщение
при равномерном распределении
Ну хз, на то они и (псевдо)случайные ))

Почему-то пограничных значений в случае с ф-цией наполовину меньше...
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,001
18.07.2011, 21:14 #10
easybudda, просто для полноты картины, покажи значение RAND_MAX.

Теперь по числам. Второй способ, по-моему, в статье описан с ошибками. Мне совершенно не понятно, к чему там округление вместо простого отбрасывания.
Больше похожей на правду кажется такая формула:
C
1
(int)(rand()/(RAND_MAX+1.0)*hi);
Диапазон [0, hi), то есть верхний предел не включается.
Ну и о качестве. Исследований я пока не проводил, но в случае, когда hi намного меньше RAND_MAX, результат по-моему должен быть примерно одинаково хорошим. А когда hi близко к RAND_MAX, то оба генератора представляются мне плохими. Хотя и по разному плохими
Короче, авторы статьи, мне кажется, излишне педантичны. Там, где требуется высокое качество псевдослучайной последовательности вряд ли будут использовать rand().
0
Evg
Эксперт CАвтор FAQ
17809 / 6019 / 388
Регистрация: 30.03.2009
Сообщений: 16,535
Записей в блоге: 26
18.07.2011, 21:23 #11
Цитата Сообщение от easybudda Посмотреть сообщение
Потому, что на 100000000 испытаний при равномерном распределении каждого из 10 чисел от 0 до 9 должно получаться по 100000000 / 10 = 10000000 штук, нет?
Ты не правильно проверяешь. Вопрос не только в том, какие будут числа, но и в их последовательности. Т.е. последовательность 1 1 1 1 2 2 2 2 3 3 3 3 .... по твоему методу будет равномерно распределённой, хотя такая последовательность никому не нужна. Как проверять правильность - хз, это вопрос к математикам
0
easybudda
Модератор
Эксперт CЭксперт С++
9627 / 5575 / 947
Регистрация: 25.07.2009
Сообщений: 10,710
18.07.2011, 21:29 #12
Цитата Сообщение от grizlik78 Посмотреть сообщение
Там, где требуется высокое качество псевдослучайной последовательности вряд ли будут использовать rand().
Полностью согласен. А там, где хватает rand() вполне подойдёт и rand() % HI, и незачем такие вот марсианские конструкции наворачивать. Я вообще за простые решения - они может и не всегда лучшие, за то понятные...

Добавлено через 5 минут
Цитата Сообщение от Evg Посмотреть сообщение
Ты не правильно проверяешь. Вопрос не только в том, какие будут числа, но и в их последовательности.
Это разные тесты. Тест на равномерное распределение чисел способ с шаманской формулой явно не прошёл, а последовательность, видимо, нужно проверять количеством идущих подряд одинаковых чисел...
0
Masel
4 / 4 / 0
Регистрация: 01.04.2009
Сообщений: 72
18.07.2011, 21:34 #13
Да вы че, ребят

оба предложенных варианта абсолютно равноценны в вопросе "случайности". Софистикой занимаетесь)
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,001
18.07.2011, 21:42 #14
Цитата Сообщение от easybudda Посмотреть сообщение
а последовательность, видимо, нужно проверять количеством идущих подряд одинаковых чисел...
Ну, вообще-то существует огромное количество различных статистических тестов. Пожалуй кое-какие из них я даже попробую, попозже. Правда гарантированно определить, что генератор является плохим нельзя, это можно утверждать лишь с некоторой заданной вероятностью.
Цитата Сообщение от Masel Посмотреть сообщение
оба предложенных варианта абсолютно равноценны в вопросе "случайности". Софистикой занимаетесь)
Masel, не факт. То есть оба неслучайны по определению, это да. Но хороший псевдослучайный генератор должен иметь свойства как можно ближе к свойствам истинно случайной последовательности. В статистическом смысле, конечно. Если интересно, можно про это почитать во втором томе "Искусства программирования" Дональда Кнута. Там же и некоторые тесты описаны.
Что же касается rand(), он обычно реализован с использованием линейного конгруэнтного генератора, а у него младшие биты имеют характеристики хуже старших, поэтому вариант с остатком рискует оказаться "менее случайным". Но не думаю, что сильно, ведь самые младшие биты rand() и не выдаёт.
0
Kastaneda
Форумчанин
Эксперт С++
4653 / 2862 / 228
Регистрация: 12.12.2009
Сообщений: 7,271
Записей в блоге: 2
Завершенные тесты: 1
18.07.2011, 21:58 #15
А я в своей логике (пост#3) ошибку нашел!
Например имеем MAX_RAND = 32767, а hi=10, тогда одинаковые значения (например 5) мы будем иметь при

(int)(scale*hi + 0.5)=5
4.6 <= scale*hi <= 5.4
0.46 <= scale <=0.54


т.е. при 15072 <= rand() <= 17694, т.е. имеем диапазон 17694-15072=2622 при котором вернутся одинаковые значения. А при rand()%11 имеем RAND_MAX/11=2978 чисел, при которых вернутся одинаковые числа.

Не по теме:

Вот, теперь вроде правильно, хотя сплю уже, могу ошибаться...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.07.2011, 21:58
Привет! Вот еще темы с ответами:

Генерация массива случайных чисел равномерно распределенных в заданном интервале и упорядочение массива - C++
Помогите создать ПО (на любом языке программирования) позволяющее, генерирующее массив заданной длины со случайными числами, равномерно...

генерация рандомных чисел в диапазоне - C++
Добрый день подскажите (или дайте кусочек кода) как реализовать генерацию рандомных чисел

Генерация случайных чисел - C++
#include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;clocale&gt; #include &lt;time.h&gt; #include &lt;stdlib.h&gt; using namespace std; int main ()...

Генерация случайных чисел - C++
Подскажите пожалуйста правильно ли я осуществил перевод строк из С в С++, сомневаюсь С - randomize(); С++ - srand(NULL); С ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
18.07.2011, 21:58
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru