Модераторы: bsa

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Массив из диапозона чисел 
V
    Опции темы
volatile
Дата 14.1.2013, 23:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85



неравномерность = есть отношение выпадений самого вероятного к самому маловероятному.
PM MAIL   Вверх
NoviceF
Дата 15.1.2013, 09:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 313
Регистрация: 13.3.2012
Где: Ростов-на-Дону

Репутация: 2
Всего: 2



Цитата(volatile @  14.1.2013,  17:55 Найти цитируемый пост)
r = rand() % 26 - 10; 


Поясните, пожалуйста, тут же ранд может вернуть 26? Что происходит в этом случае (по условию же максимум нужно 25)?
PM MAIL   Вверх
bsa
Дата 15.1.2013, 09:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196



NoviceF, что является результатом оператора % ?
PM   Вверх
NoviceF
Дата 15.1.2013, 09:46 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 313
Регистрация: 13.3.2012
Где: Ростов-на-Дону

Репутация: 2
Всего: 2



Цитата(bsa @ 15.1.2013,  10:35)
NoviceF, что является результатом оператора % ?

Остаток от деления того, что слева, на то, что справа.

Если ранд вернёт число кратное 26, то результатом будет 0, в остальных случаях остаток будет в диапазоне от 1 до 25, так? )
PM MAIL   Вверх
bsa
Дата 15.1.2013, 10:08 (ссылка) |    (голосов:1) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196



Цитата(NoviceF @  15.1.2013,  10:46 Найти цитируемый пост)
так?
да
Тогда в чем был смысл предыдущего вопроса?
volatile, ты был прав. Равномерность примерно одинаковая, что для варианта с остатком от деления, что с умножением (примерно, 99.6% и 99.7% соответственно на N*1000000 опытах).
Код
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define N 26

int norm1(int max)
{
        return max * (rand() / (RAND_MAX + 1.0)); //можно использовать и целочисленный вариант, но так надежней
}

int norm2(int max)
{
        return rand() % max;
}

int main()
{
        int array[N];
        long long i;
        for(i = 0; i < N; ++i)
                array[i] = 0;
        //srand(time(NULL)); //закомментировано для точной воспроизводимости результатов
        for(i = N*1000000ll; i; --i) {
                int r = norm2(N);
                assert((r < N) && (r >= 0));
                ++array[r];
        }
        int min = array[0], max = array[0];
        for(i = 0; i < N; ++i) {
                printf("%d - %d\n", (int)i, array[i]);
                if (array[i] < min)
                        min = array[i];
                if (array[i] > max)
                        max = array[i];
        }
        printf("d = %.2f%%\n", (double)min/max*100);
        return 0;
}

PM   Вверх
volatile
Дата 15.1.2013, 23:23 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 16
Всего: 85



bsa, уважаю! smile

Цитата(bsa @  15.1.2013,  10:08 Найти цитируемый пост)
примерно, 99.6% и 99.7%

Фактически неравномерность у них меньше, здесь все забивает системный rand.
Там и uniform_rnd() показывает такую-же неравномерность, а должен быть идеальным.
по моим подсчетам неравномерность при N=26, для обоих методов составляет: =99.9207%
для uniform_rnd:  =100.0000%
я эти числа получил просто счетчиком пройдя весь диапазон от 0 до RAND_MAX, и посмотрел что на выходе.

Но можно пойти и другим путем, испоьзуя вашу программу.
Чтобы обострить неравномерность, будем генерить числа соизмеримые с RAND_MAX, 
при этом неравномерность резко возрастает, и становицца видна невооруженным глазом, даже сквозь системный rand().

Итак, на вашей программе, для:
N = int(0.55*RAND_MAX); и при количестве циклов 100*1000000ll
результаты, такие:
Код

norm1 = 44.68%
norm2 = 44.92%
norm3 = 90.18% (он же uniform_rnd)
---
при увеличении опытов norm1,norm2 стремяцца к ==> 50%; uniform_rnd ==> 100%

Резюме. при маленьком N, все замечательно и вообще по барабану какую формулу использовать.
При больших N, простые формулы дают очень плохую картину. Вероятность выпадения макс/мин в 2 раза, уже нельзя назвать ГСЧ.
и нужно использовать генератор с отбрасыванием, такой как uniform_rnd();

PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.0744 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.