Функция, генерирующая псевдослучайные числа, имеет прототип в файле библиотеки stdlib.h :
2
3
4
5
6
int rand(void)
{
next = next * 1103515245;
return (unsigned int)(next / 65536) * 2768;
}
Функция rand() не принимает аргументов, а оперирует переменной next с глобальной областью видимости.
Если необходимо сгенерировать последовательность в диапазоне [M1; M2], то используется формула:
{\displaystyle{Number = rand()\%(M2-M1+1) + M1}}
где
- {\displaystyle{Number}} – генерируемое число,
- {\displaystyle{M2-M1+1}} – полный диапазон представления чисел,
- {\displaystyle{M1}} – смещение указанного диапазона относительно 0;
- {\displaystyle{\%}} — остаток от деления.
Например, если требуется сгенерировать последовательность в диапазоне [-10;10], то вызов функции будет выглядеть как
Number = rand()%(10+10+1)-10
Number = rand()%(21)-10
В результате получения остатка от деления на 21 имеем число от 0 до 20. Вычитая из полученного числа 10, получим число в искомом диапазоне [-10;10].
Однако генерируемая функцией rand() последовательность будет иметь один и тот же вид при каждом запуске программы.
Для генерации различных последовательности при каждом запуске программы необходимо проинициализировать глобальную переменную next значением, отличным от 1. С этой целью используется функция
2
{ next = seed; }
Чтобы инициализация next при каждом запуске программы была различной в качестве аргумента seed чаще всего используется текущее время.
Пример Заполнить массив из 20 элементов случайными числами в диапазоне от 0 до 99.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#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 раз.
Реализация на Си
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 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;
}
Алгоритм произвольного выбора
Часто возникает задача произвольного выбора ранее заданных элементов массива. Причем необходимо предусмотреть отсутствие повторений в выборе этих элементов.
Алгоритм такого выбора состоит в следующем:
- Выбираем произвольно индекс элемента массива
- Если элемент с таким индексом уже был ранее выбран, двигаемся вправо, пока не дойдём до следующего не выбранного элемента. При этом следим за тем, чтобы «движение вправо» не вышло за границы массива. Если фиксируется выход за границы массива, начинаем просмотр элементов массива с начала.
- Выбираем элемент
- Фиксируем элемент как выбранный
- Повторяем указанные действия для всех остальных элементов
Реализации на Си
В результате получаем новый массив b, сформированный произвольной выборкой элементов массива a.
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
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 20
int main()
{
int a[SIZE];
int b[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 ind = rand() % 20; // выбираем произвольный индекс
while (a[ind] == -1) // пока элемент "выбран"
{
ind++;
// двигаемся вправо
ind %= 20;
// если дошли до правой границы, возвращаемся в начало
}
b[i] = a[ind];
// записываем следующий элемент массива b
a[ind] = -1; // отмечаем элемент массива a как "выбранный"
}
printf("\n");
// Выводим получившийся массив
for (int i = 0; i < SIZE; i++)
printf("%2d ", b[i]);
getchar();
return 0;
}