Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Random в C (Си)

Ответить
Настройки темы
C/C++ - Random в C (Си)

Аватара для ganselo

Старожил


Сообщения: 232
Благодарности: 90

Профиль | Сайт | Отправить PM | Цитировать


Изменения
Автор: ganselo
Дата: 13-11-2008
Дан массив:
int *x;
x=new int[n];

Я его заполняю рандомно:
Код: Выделить весь код
srand(time(NULL));
for (int i=0; i<n; i++)
x[i]=rand()%100;
Как исключить вероятность того, чтобы значение элементов не могли повториться(т.е чтобы элементы были уникальны)??
Я пробовал так:
Код: Выделить весь код
for (int i=0; i<n; i++)
{
     x[i]=rand()%100;
     for (int j=0; j<n; j++)
     {
           if (i!=j)
           {
               if (x[i]==x[j]) x[i]=rand()%100;
            }
       }
}
Но тут после того как программа нашла схожий элемент и заменила с помощью рэнтома, есть вероятность что этот заменённый элемент может быть не уникальным, по отношению к предыдущим.
Как добится того, чтобы элементы массива были уникальны и при этом время выполнения было как можно минимально.

Отправлено: 19:30, 13-11-2008

 

Новый участник


Сообщения: 49
Благодарности: 17

Профиль | Отправить PM | Цитировать


Цитата ganselo:
Следовательно n увеличится ровно столько раз сколько будит равна размерность массива. И поэтому значение элементов массива не будит превосхадить размерности массива. »
Ты прав, в том примере случайно не число, а индекс в массиве.

Тогда такой вариант:
Код: Выделить весь код
1:     #include<conio.h>
2:     #include<stdio.h>
3:     #include<stdlib.h>
4:     #include<time.h>
5:     #include<mem.h>
6:     
7:     
8:     
9:     #define ASIZE        200
10:    #define RANDOMSID    500
11:    
12:    int main()
13:     {
14:     srand(time(NULL));
15:     int values[ ASIZE ], random_id[ RANDOMSID ], randomiza, i, j;
16:    
17:     memset( &random_id, 0, sizeof(random_id) );
18:    
19:    
20:     for( i=0, j=0, randomiza=0; i<ASIZE; )
21:      {
22:      randomiza = rand() % RANDOMSID;
23:      if( !random_id[ randomiza ] )
24:       {
25:       random_id[ j++ ] = 1;
26:       values[ i++ ] = randomiza;
27:       }
28:      }
29:    
30:     for(unsigned n=0; n<200; n++ )
31:      {
32:      printf( "%d ", values[ n ] );
33:      }

Отправлено: 14:41, 14-11-2008 | #11



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля.

pva pva вне форума

Аватара для pva

Ветеран


Сообщения: 1180
Благодарности: 279

Профиль | Отправить PM | Цитировать


Извияюсь, что в прошлом примере не поставил разделитель при выводе на экран, чем сбил столку. Иногда не проверяю код :-[
Для случая когда диапазон гораздо больше последовательности, которую надо выдать, предлагаю очередной "хитрый" способ:
Код: Выделить весь код
// Опять же предполагаю, что число возможных комбинаций не меньше числа требуемых
// Снова используем принцип случайного перемешивания.
// Но на этот раз хитро делаем выборку. Главное - чтобы она была отсортирована и без повторений.
// использую C++, если возникнут вопросы - переведу на С

static const int rand_range = 500;
static const unsigned rand_count = 200;

// допустим мы уже получили все комбинации и отсортировали их по возрастанию
// рассчитаем вероятность того, что ра расстояние между соседними двумя < x
// пусть числа выпадают с равномерным на [0,M] распределением
// вероятность что число попадёт N раз в отрезок [X,M] равна ((M-X)/M)^N
// тогда вероятность что при N испытаниях расстояние до ближайшего значения_
// будет X равно F(X) = 1 - ((M-X)/M)^N
// по теореме http://www.nsu.ru/mmf/tvims/chernova/tv/lec/node32.html#SECTION000821
// генерируем случайную величину, которая задаёт расстояния между значениями
// dX = (M - X)*(1 - (1 - R)^(1/N))
// где R - равномерно распределённая на [0,1] величина.
// суммируя dX получаем строго возрастающую последовательность

vector<int> rands(rand_count);

{  // заполняем
    int prev = 0;

    for (unsigned count=rands.size(); 0<--count; )
    {
        // dX = (M - X)*(1 - (1 - R)^(1/N))
        // стараемся сделать так, чтобы хватило места для последующих элементов /*1*/

        prev += (double(rand_range - count /*1*/) - double(prev)) *
                    (1. - pow(1. - double(rand())/RAND_MAX), 1./count));

        rands[count] = prev;

        // на единицу смещаем чтобы не выпало одинаковых значений,
        // т.к. данное распределение при округлении может давать 0
        ++prev;
    }
    rands[0] = (double(rand_range) - double(prev)) *(double(rand())/RAND_MAX);
}

// перемешиваем
for (unsigned count=rands.size(); 0<--count; )
{
    std::swap(first[rand() % count], first[count]);
}

// вывод в stdout
for(unsigned count=0; count<rands.size(); ++count)
{
    std::cout << rands[count] << "\n";
}

Последний раз редактировалось pva, 16-11-2008 в 20:00. Причина: забыл случай count=0

Это сообщение посчитали полезным следующие участники:

Отправлено: 19:52, 16-11-2008 | #12


Аватара для ganselo

Старожил


Сообщения: 232
Благодарности: 90

Профиль | Сайт | Отправить PM | Цитировать


Цитата pva:
предлагаю очередной "хитрый" способ: »
Спасибо всё работает
Цитата pva:
если возникнут вопросы - переведу на С »
Не стоит... всё понятно.

-------
К величайшему сожалению "история учит нас тому, что она ничему не учит".


Отправлено: 10:16, 21-11-2008 | #13



Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » C/C++ - Random в C (Си)

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
C/C++ - [решено] Random element deleting HD295 Программирование и базы данных 2 19-05-2009 19:35
Delphi - прога с использованьем "Random" ShadowMas Программирование и базы данных 2 21-11-2008 21:19




 
Переход