Генерация псевдослучайных последовательностей

Алгоритмизация / Генерация псевдослучайных последовательностей

 

Функция, генерирующая псевдослучайные числа, имеет прототип в файле библиотеки stdlib.h :

1
2
3
4
5
6
unsigned long int next = 1;
int rand(void)
{
  next = next * 1103515245;
  return((unsigned int)(next / 65536) * 2768);
}

Функция rand() не принимает аргументов, а оперирует переменной next с глобальной областью видимости.

Если необходимо сгенерировать последовательность в диапазоне [M1; M2], то используется формула:

Number = rand()%(M2-M1+1) + M1;

где Number – генерируемое число. M2-M1+1 – полный диапазон представления чисел. M1 – смещение указанного диапазона относительно 0; % - остаток от деления.

Например, если требуется сгенерировать последовательность в диапазоне [-10;10], то вызов функции будет выглядеть как

Number = rand()%(10+10+1)-10

Number = rand()%(21)-10

В результате получения остатка от деления на 21 имеем число от 0 до 20. Вычитая из полученного числа 10, получим число в искомом диапазоне [-10;10].

Однако генерируемая функцией rand() последовательность будет иметь один и тот же вид при каждом запуске программы.

Для генерации различных последовательности при каждом запуске программы необходимо проинициализировать глобальную переменную next значением, отличным от 1. С этой целью используется функция
void srand(unsigned int seed)
{ next = seed; }

Чтобы инициализация next при каждом запуске программы была различной в качестве аргумента seed чаще всего используется текущее время.

Пример Заполнить массив из 20 элементов случайными числами в диапазоне от 0 до 99.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
int main() {
  int a[SIZE];
  srand(time(NULL));
  for (int i = 0; i<SIZE; i++)
  {
    a[i] = rand() % 100;
    printf("%d ", a[i]);
  }
  getchar();
  return 0;
}

Результат выполнения
Генерация случайных чисел

Алгоритм перемешивания

Часто возникает задача расставить уже имеющийся набор значений в произвольном порядке. С этой целью также используется генератор псевдослучайных чисел. При этом создается массив и заполняется значениями.
Сама процедура перемешивания происходит следующим образом. Генерируется два значения индексов массива случайным образом, и значения элементов с полученными индексами меняются местами. Процедура повторяется не менее N раз, где N - количество элементов массива.
В качестве примера рассмотрим перемешивание 20 значений (от 1 до 20) и повторим процедуру 20 раз.

Реализация на Си

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
int main() {
  int a[SIZE];
  srand(time(NULL));
  // Заполняем массив последовательными значениями от 1 до 20
  for (int i = 0; i < SIZE; i++)
  {
    a[i] = i + 1;
    printf("%2d ", a[i]);
  }
  for (int i = 0; i < SIZE; i++)
  {
    // Генерируем случайно два индекса элементов
    int ind1 = rand() % 20;
    int ind2 = rand() % 20;
    // и меняем местами элементы с этими индексами
    int temp = a[ind1];
    a[ind1] = a[ind2];
    a[ind2] = temp;
  }
  printf("\n");
  // Выводим получившийся массив
  for (int i = 0; i < SIZE; i++)
    printf("%2d ", a[i]);
  getchar();
  return 0;
}

Результат выполнения
Алгоритм перемешивания


Назад: Алгоритмизация

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *