Реклама на портале

Генерация случайных чисел в языке си. Случайные числа в стандартном си Генератор случайных чисел си

Перевод статьи Random numbers широко известного в узких кругах Джона Скита. Остановился на этой статье, так как в своё время сам столкнулся с описываемой в ней проблемой.

Просматривая темы по .NET и C# на сайте StackOverflow, можно увидеть бесчисленное множество вопросов с упоминанием слова «random», в которых, по сути, поднимается один и тот же извечный и «неубиваемый» вопрос: почему генератор случайных чисел System.Random «не работает» и как это «исправить». Данная статья посвящена рассмотрению данной проблемы и способов её решения.

Постановка проблемы

На StackOverflow, в новостных группах и рассылках все вопросы по теме «random» звучат примерно так:
Я использую Random.Next для генерации нескольких случайных чисел, но метод возвращает одно и то же число при его множественных вызовах. Число меняется при каждом запуске приложения, однако в рамках одного выполнения программы оно постоянное.

В качестве примера кода приводится примерно следующее:
// Плохой код! Не использовать! for (int i = 0; i < 100; i++) { Console.WriteLine(GenerateDigit()); } ... static int GenerateDigit() { Random rng = new Random(); // Предположим, что здесь много логики return rng.Next(10); }
Итак, что здесь неправильно?

Объяснение

Класс Random не является истинным генератором случайных чисел, он содержит генератор псевдо случайных чисел. Каждый экземпляр класса Random содержит некоторое внутреннее состояние, и при вызове метода Next (или NextDouble , или NextBytes) метод использует это состояние для возврата числа, которое будет казаться случайным. После этого внутреннее состояние меняется таким образом, чтобы при следующем вызове метода Next он возвратил другое кажущееся-случайным число, отличное от возвращённого ранее.

Все «внутренности» работы класса Random полностью детерминистичны . Это значит, что если вы возьмёте несколько экземпляров класса Random с одинаковым начальным состоянием, которое задаётся через параметр конструктора seed , и для каждого экземпляра вызовите определённые методы в одинаковом порядке и с одинаковыми параметрами, то в конце вы получите одинаковые результаты.

Так что ж плохого в вышеприведённом коде? Плохо то, что мы используем новый экземпляр класса Random внутри каждой итерации цикла. Конструктор Random, не принимающий параметров , принимает значение текущей даты и времени как seed (начальное состояние). Итерации в цикле «прокрутятся» настолько быстро, что системное время «не успеет измениться» по их окончании; таким образом, все экземпляры Random получат в качестве начального состояния одинаковое значение и поэтому возвратят одинаковое псевдослучайное число.

Как это исправить?

Есть немало решений проблемы, каждое со своими плюсами и минусами. Мы рассмотрим несколько из них.
Использование криптографического генератора случайных чисел
.NET содержит абстрактный класс RandomNumberGenerator , от которого должны наследоваться все реализации криптографических генераторов случайных чисел (далее - криптоГСЧ). Одну из таких реализаций содержит и.NET - встречайте класс RNGCryptoServiceProvider . Идея криптоГСЧ в том, что даже если он всё так же является генератором псевдослучайных чисел, он обеспечивает достаточно сильную непредсказуемость результатов. RNGCryptoServiceProvider использует несколько источников энтропии, которые фактически являются «шумами» в вашем компьютере, и генерируемую им последовательность чисел очень тяжело предсказать. Более того, «внутрикомпьютерный» шум может использоваться не только в качестве начального состояния, но и между вызовами следующих случайных чисел; таким образом, даже зная текущее состояние класса, этого не хватит для вычисления как следующих чисел, которые будут сгенерированы в будущем, так и тех, которые были сгенерированы ранее. Вообще-то точное поведение зависит от реализации. Помимо этого, Windows может использовать специализированное аппаратное обеспечение, являющееся источником «истинных случайностей» (например, это может быть датчик распада радиоактивного изотопа) для генерации ещё более защищённых и надёжных случайных чисел.

Сравним это с ранее рассматриваемым классом Random. Предположим, вы вызвали Random.Next(100) десять раз и сохранили результаты. Если вы имеете достаточно вычислительной мощи, то можете сугубо на основании этих результатов вычислить начальное состояние (seed), с которым был создан экземпляр Random, предсказать следующие результаты вызова Random.Next(100) и даже вычислить результаты предыдущих вызовов метода. Такое поведение катастрофически неприемлемо, если вы используете случайные числа для обеспечения безопасности, в финансовых целях и т.д. КриптоГСЧ работают существенно медленнее класса Random, но генерируют последовательность чисел, каждое из которых более независимо и непредсказуемо от значений остальных.

В большинстве случаев более низкая производительность не является препятствием - им является плохой API. RandomNumberGenerator создан для генерации последовательностей байтов - и всё. Сравните это с методами класса Random, где есть возможность получения случайного целого числа, дробного числа, а также набора байтов. Ещё одно полезное свойство - возможность получения случайного числа в указанном диапазоне. Сравните эти возможности с массивом случайных байтов, который выдаёт RandomNumberGenerator. Исправить ситуацию можно, создав свою оболочку (враппер) вокруг RandomNumberGenerator, которая будет преобразовывать случайные байты в «удобный» результат, однако это решение нетривиально.

Тем не менее, в большинстве случаев «слабость» класса Random вполне подходит, если вы сможете решить проблему, описанную в начале статьи. Посмотрим, что здесь можно сделать.

Используйте один экземпляр класса Random при множественных вызовах
Вот он, корень решения проблемы - использовать лишь один экземпляр Random при создании множества случайных чисел посредством Random.Next. И это очень просто - посмотрите, как можно изменить вышеприведённый код:
// Этот код будет получше Random rng = new Random(); for (int i = 0; i < 100; i++) { Console.WriteLine(GenerateDigit(rng)); } ... static int GenerateDigit(Random rng) { // Предположим, что здесь много логики return rng.Next(10); }
Теперь в каждой итерации будут разные числа, … но это ещё не всё. Что будет, если мы вызовем этот блок кода два раза подряд? Правильно, мы создадим два экземпляра Random с одинаковым начальным значением и получим два одинаковых набора случайных чисел. В каждом наборе числа будут различаться, однако между собой эти наборы будут равны.

Есть два способа решения проблемы. Во-первых, мы можем использовать не экземплярное, а статическое поле, содержащее экземпляр Random, и тогда вышеприведённый кусок кода создаст лишь один экземпляр, и будет его использовать, вызываясь сколько угодно раз. Во-вторых, мы можем вообще убрать оттуда создание экземпляра Random, переместив его «повыше», в идеале - на самый «верх» программы, где будет создан единичный экземпляр Random, после чего он будет передаваться во все места, где нужны случайные числа. Это отличная идея, которая красиво выражается зависимостями, но она будет работать до тех пор, пока мы используем лишь один поток.

Потокобезопасность

Класс Random не потокобезопасен. Учитывая то, как мы любим создавать один экземпляр и использовать его по всей программе на протяжении всего времени её выполнения (синглтон, привет!), отсутствие потокобезопасности становится реальной занозой. Ведь если мы используем один экземпляр одновременно в нескольких потоках, то есть вероятность обнуления его внутреннего состояния, и если это произойдёт, то с этого момента экземпляр станет бесполезным.

Снова-таки, здесь есть два пути решения проблемы. Первый путь по-прежнему предполагает использование одного экземпляра, однако на этот раз с использованием блокировки ресурса посредством монитора. Для этого необходимо создать оболочку вокруг Random, которая будет оборачивать вызов его методов в оператор lock , обеспечивающий эксклюзивный доступ к экземпляру для вызывающей стороны. Этот путь плох тем, что снижает производительность в многопоточно-интенсивных сценариях.

Другой путь, который я опишу ниже - использование по одному экземпляру на каждый поток. Единственное, нам нужно удостовериться, что при создании экземпляров мы используем разные начальные значения (seed), а потому мы не можем использовать конструкторы по умолчанию. Во всём остальном этот путь относительно прямолинеен.

Безопасный провайдер

К счастью, новый обобщённый класс ThreadLocal , появившийся в.NET 4, очень сильно облегчает написание провайдеров, обеспечивающих по одному экземпляру на поток. Просто нужно в конструктор ThreadLocal передать делегат, который будет ссылаться на получение значения собственно нашего экземпляра. В данном случае я решил использовать единственное начальное значение (seed), инициализируя его при помощи Environment.TickCount (именно так действует конструктор Random без параметров). Далее полученное количество тиков инкрементируется каждый раз, когда нам нужно получить новый экземпляр Random для отдельного потока.

Нижепредставленный класс полностью статический и содержит лишь один публичный (открытый) метод GetThreadRandom. Этот метод сделан методом, а не свойством, в основном из-за удобства: благодаря этому все классы, которым нужен экземпляр Random, будут зависеть от Func (делегат, указывающий на метод, не принимающий параметров и возвращающий значение типа Random), а не от самого класса Random. Если тип предназначен для работы в одном потоке, он может вызвать делегат для получения единого экземпляра Random и после чего использовать его повсюду; если же тип должен работать в многопоточных сценариях, он может вызывать делегат каждый раз, когда ему требуется генератор случайных чисел. Нижеприведенный класс создаст столько экземпляров класса Random, сколько есть потоков, и каждый экземпляр будет стартовать с различного начального значения. Если нам нужно использовать провайдер случайных чисел как зависимость в других типах, мы можем сделать так: new TypeThatNeedsRandom(RandomProvider.GetThreadRandom) . Ну а вот и сам код:
using System; using System.Threading; public static class RandomProvider { private static int seed = Environment.TickCount; private static ThreadLocal randomWrapper = new ThreadLocal(() => new Random(Interlocked.Increment(ref seed))); public static Random GetThreadRandom() { return randomWrapper.Value; } }
Достаточно просто, не правда ли? Всё потому, что весь код направлен на выдачу правильного экземпляра Random. После того, как экземпляр создан и возвращён, совершенно неважно, что вы будете с ним делать дальше: все дальнейшие выдачи экземпляров совершенно не зависят от текущего. Конечно, клиентский код имеет лазейку для злонамеренного неправильного использования: он может получить один экземпляр Random и передать его в другие потоки вместо вызова в тех, других потоках, нашего RandomProvider.

Проблемы с дизайном интерфейса

Одна проблема всё равно остаётся: мы используем слабо защищённый генератор случайных чисел. Как упоминается ранее, существует намного более безопасная во всех отношениях версия ГСЧ в RandomNumberGenerator, реализация которого находится в классе RNGCryptoServiceProvider. Однако его API достаточно сложно использовать в стандартных сценариях.

Было бы очень приятно, если бы провайдеры ГСЧ в фреймворке имели отдельные «источники случайности». В таком случае мы могли бы иметь единый простой и удобный API, который бы поддерживался как небезопасной-но-быстрой реализацией, так и безопасной-но-медленной. Что-ж, мечтать не вредно. Возможно, подобный функционал появится в следующих версиях.NET Framework. Возможно, кто-то не из Microsoft предложит свою реализацию адаптера. (К сожалению, я не буду этим кем-то… правильная реализация подобной задумки удивительно сложна.) Вы также можете создать свой класс, отнаследовав его от Random и переопределив методы Sample и NextBytes, однако неясно, как именно они должны работать, и даже собственная реализация Sample может быть намного сложнее, нежели кажется. Может быть, в следующий раз…

Перевод статьи Random numbers широко известного в узких кругах Джона Скита. Остановился на этой статье, так как в своё время сам столкнулся с описываемой в ней проблемой.

Просматривая темы по .NET и C# на сайте StackOverflow, можно увидеть бесчисленное множество вопросов с упоминанием слова «random», в которых, по сути, поднимается один и тот же извечный и «неубиваемый» вопрос: почему генератор случайных чисел System.Random «не работает» и как это «исправить». Данная статья посвящена рассмотрению данной проблемы и способов её решения.

Постановка проблемы

На StackOverflow, в новостных группах и рассылках все вопросы по теме «random» звучат примерно так:
Я использую Random.Next для генерации нескольких случайных чисел, но метод возвращает одно и то же число при его множественных вызовах. Число меняется при каждом запуске приложения, однако в рамках одного выполнения программы оно постоянное.

В качестве примера кода приводится примерно следующее:
// Плохой код! Не использовать! for (int i = 0; i < 100; i++) { Console.WriteLine(GenerateDigit()); } ... static int GenerateDigit() { Random rng = new Random(); // Предположим, что здесь много логики return rng.Next(10); }
Итак, что здесь неправильно?

Объяснение

Класс Random не является истинным генератором случайных чисел, он содержит генератор псевдо случайных чисел. Каждый экземпляр класса Random содержит некоторое внутреннее состояние, и при вызове метода Next (или NextDouble , или NextBytes) метод использует это состояние для возврата числа, которое будет казаться случайным. После этого внутреннее состояние меняется таким образом, чтобы при следующем вызове метода Next он возвратил другое кажущееся-случайным число, отличное от возвращённого ранее.

Все «внутренности» работы класса Random полностью детерминистичны . Это значит, что если вы возьмёте несколько экземпляров класса Random с одинаковым начальным состоянием, которое задаётся через параметр конструктора seed , и для каждого экземпляра вызовите определённые методы в одинаковом порядке и с одинаковыми параметрами, то в конце вы получите одинаковые результаты.

Так что ж плохого в вышеприведённом коде? Плохо то, что мы используем новый экземпляр класса Random внутри каждой итерации цикла. Конструктор Random, не принимающий параметров , принимает значение текущей даты и времени как seed (начальное состояние). Итерации в цикле «прокрутятся» настолько быстро, что системное время «не успеет измениться» по их окончании; таким образом, все экземпляры Random получат в качестве начального состояния одинаковое значение и поэтому возвратят одинаковое псевдослучайное число.

Как это исправить?

Есть немало решений проблемы, каждое со своими плюсами и минусами. Мы рассмотрим несколько из них.
Использование криптографического генератора случайных чисел
.NET содержит абстрактный класс RandomNumberGenerator , от которого должны наследоваться все реализации криптографических генераторов случайных чисел (далее - криптоГСЧ). Одну из таких реализаций содержит и.NET - встречайте класс RNGCryptoServiceProvider . Идея криптоГСЧ в том, что даже если он всё так же является генератором псевдослучайных чисел, он обеспечивает достаточно сильную непредсказуемость результатов. RNGCryptoServiceProvider использует несколько источников энтропии, которые фактически являются «шумами» в вашем компьютере, и генерируемую им последовательность чисел очень тяжело предсказать. Более того, «внутрикомпьютерный» шум может использоваться не только в качестве начального состояния, но и между вызовами следующих случайных чисел; таким образом, даже зная текущее состояние класса, этого не хватит для вычисления как следующих чисел, которые будут сгенерированы в будущем, так и тех, которые были сгенерированы ранее. Вообще-то точное поведение зависит от реализации. Помимо этого, Windows может использовать специализированное аппаратное обеспечение, являющееся источником «истинных случайностей» (например, это может быть датчик распада радиоактивного изотопа) для генерации ещё более защищённых и надёжных случайных чисел.

Сравним это с ранее рассматриваемым классом Random. Предположим, вы вызвали Random.Next(100) десять раз и сохранили результаты. Если вы имеете достаточно вычислительной мощи, то можете сугубо на основании этих результатов вычислить начальное состояние (seed), с которым был создан экземпляр Random, предсказать следующие результаты вызова Random.Next(100) и даже вычислить результаты предыдущих вызовов метода. Такое поведение катастрофически неприемлемо, если вы используете случайные числа для обеспечения безопасности, в финансовых целях и т.д. КриптоГСЧ работают существенно медленнее класса Random, но генерируют последовательность чисел, каждое из которых более независимо и непредсказуемо от значений остальных.

В большинстве случаев более низкая производительность не является препятствием - им является плохой API. RandomNumberGenerator создан для генерации последовательностей байтов - и всё. Сравните это с методами класса Random, где есть возможность получения случайного целого числа, дробного числа, а также набора байтов. Ещё одно полезное свойство - возможность получения случайного числа в указанном диапазоне. Сравните эти возможности с массивом случайных байтов, который выдаёт RandomNumberGenerator. Исправить ситуацию можно, создав свою оболочку (враппер) вокруг RandomNumberGenerator, которая будет преобразовывать случайные байты в «удобный» результат, однако это решение нетривиально.

Тем не менее, в большинстве случаев «слабость» класса Random вполне подходит, если вы сможете решить проблему, описанную в начале статьи. Посмотрим, что здесь можно сделать.

Используйте один экземпляр класса Random при множественных вызовах
Вот он, корень решения проблемы - использовать лишь один экземпляр Random при создании множества случайных чисел посредством Random.Next. И это очень просто - посмотрите, как можно изменить вышеприведённый код:
// Этот код будет получше Random rng = new Random(); for (int i = 0; i < 100; i++) { Console.WriteLine(GenerateDigit(rng)); } ... static int GenerateDigit(Random rng) { // Предположим, что здесь много логики return rng.Next(10); }
Теперь в каждой итерации будут разные числа, … но это ещё не всё. Что будет, если мы вызовем этот блок кода два раза подряд? Правильно, мы создадим два экземпляра Random с одинаковым начальным значением и получим два одинаковых набора случайных чисел. В каждом наборе числа будут различаться, однако между собой эти наборы будут равны.

Есть два способа решения проблемы. Во-первых, мы можем использовать не экземплярное, а статическое поле, содержащее экземпляр Random, и тогда вышеприведённый кусок кода создаст лишь один экземпляр, и будет его использовать, вызываясь сколько угодно раз. Во-вторых, мы можем вообще убрать оттуда создание экземпляра Random, переместив его «повыше», в идеале - на самый «верх» программы, где будет создан единичный экземпляр Random, после чего он будет передаваться во все места, где нужны случайные числа. Это отличная идея, которая красиво выражается зависимостями, но она будет работать до тех пор, пока мы используем лишь один поток.

Потокобезопасность

Класс Random не потокобезопасен. Учитывая то, как мы любим создавать один экземпляр и использовать его по всей программе на протяжении всего времени её выполнения (синглтон, привет!), отсутствие потокобезопасности становится реальной занозой. Ведь если мы используем один экземпляр одновременно в нескольких потоках, то есть вероятность обнуления его внутреннего состояния, и если это произойдёт, то с этого момента экземпляр станет бесполезным.

Снова-таки, здесь есть два пути решения проблемы. Первый путь по-прежнему предполагает использование одного экземпляра, однако на этот раз с использованием блокировки ресурса посредством монитора. Для этого необходимо создать оболочку вокруг Random, которая будет оборачивать вызов его методов в оператор lock , обеспечивающий эксклюзивный доступ к экземпляру для вызывающей стороны. Этот путь плох тем, что снижает производительность в многопоточно-интенсивных сценариях.

Другой путь, который я опишу ниже - использование по одному экземпляру на каждый поток. Единственное, нам нужно удостовериться, что при создании экземпляров мы используем разные начальные значения (seed), а потому мы не можем использовать конструкторы по умолчанию. Во всём остальном этот путь относительно прямолинеен.

Безопасный провайдер

К счастью, новый обобщённый класс ThreadLocal , появившийся в.NET 4, очень сильно облегчает написание провайдеров, обеспечивающих по одному экземпляру на поток. Просто нужно в конструктор ThreadLocal передать делегат, который будет ссылаться на получение значения собственно нашего экземпляра. В данном случае я решил использовать единственное начальное значение (seed), инициализируя его при помощи Environment.TickCount (именно так действует конструктор Random без параметров). Далее полученное количество тиков инкрементируется каждый раз, когда нам нужно получить новый экземпляр Random для отдельного потока.

Нижепредставленный класс полностью статический и содержит лишь один публичный (открытый) метод GetThreadRandom. Этот метод сделан методом, а не свойством, в основном из-за удобства: благодаря этому все классы, которым нужен экземпляр Random, будут зависеть от Func (делегат, указывающий на метод, не принимающий параметров и возвращающий значение типа Random), а не от самого класса Random. Если тип предназначен для работы в одном потоке, он может вызвать делегат для получения единого экземпляра Random и после чего использовать его повсюду; если же тип должен работать в многопоточных сценариях, он может вызывать делегат каждый раз, когда ему требуется генератор случайных чисел. Нижеприведенный класс создаст столько экземпляров класса Random, сколько есть потоков, и каждый экземпляр будет стартовать с различного начального значения. Если нам нужно использовать провайдер случайных чисел как зависимость в других типах, мы можем сделать так: new TypeThatNeedsRandom(RandomProvider.GetThreadRandom) . Ну а вот и сам код:
using System; using System.Threading; public static class RandomProvider { private static int seed = Environment.TickCount; private static ThreadLocal randomWrapper = new ThreadLocal(() => new Random(Interlocked.Increment(ref seed))); public static Random GetThreadRandom() { return randomWrapper.Value; } }
Достаточно просто, не правда ли? Всё потому, что весь код направлен на выдачу правильного экземпляра Random. После того, как экземпляр создан и возвращён, совершенно неважно, что вы будете с ним делать дальше: все дальнейшие выдачи экземпляров совершенно не зависят от текущего. Конечно, клиентский код имеет лазейку для злонамеренного неправильного использования: он может получить один экземпляр Random и передать его в другие потоки вместо вызова в тех, других потоках, нашего RandomProvider.

Проблемы с дизайном интерфейса

Одна проблема всё равно остаётся: мы используем слабо защищённый генератор случайных чисел. Как упоминается ранее, существует намного более безопасная во всех отношениях версия ГСЧ в RandomNumberGenerator, реализация которого находится в классе RNGCryptoServiceProvider. Однако его API достаточно сложно использовать в стандартных сценариях.

Было бы очень приятно, если бы провайдеры ГСЧ в фреймворке имели отдельные «источники случайности». В таком случае мы могли бы иметь единый простой и удобный API, который бы поддерживался как небезопасной-но-быстрой реализацией, так и безопасной-но-медленной. Что-ж, мечтать не вредно. Возможно, подобный функционал появится в следующих версиях.NET Framework. Возможно, кто-то не из Microsoft предложит свою реализацию адаптера. (К сожалению, я не буду этим кем-то… правильная реализация подобной задумки удивительно сложна.) Вы также можете создать свой класс, отнаследовав его от Random и переопределив методы Sample и NextBytes, однако неясно, как именно они должны работать, и даже собственная реализация Sample может быть намного сложнее, нежели кажется. Может быть, в следующий раз…

Очень часто в программах возникает необходимость использования случайных чисел - от заполнения массива до криптографии. Для получения последовательности случайных чисел в языке C# имеется класс Random . Этот класс предусматривает два конструктора:

  • Random () - инициализирует экземпляр класса Random с помощью начального значения, зависящего от текущего времени. Как известно, время может быть представлено в тиках - 100-наносекундных импульсах, начиная с 1 января 0001 года. И значение времени в тиках представляет собой 64-битное целое число, которое и будет использоваться для инициализации экземпляра генератора случайных чисел.
  • Random (Int32 ) - инициализирует экземпляр класса Random с помощью указанного начального значения. Такая инициализация генератора случайных чисел может быть удобна на этапе отладки программы, поскольку в этом случае при каждом запуске программы будут генерироваться одни и те же "случайные" числа.
Основным методом данного класса является метод Next() , позволяющий получить случайное число и имеющий ряд перегрузок:
  • Next() - возвращает случайное целое неотрицательное число формата Int32 .
  • Next(Int32 ) - возвращает случайное целое неотрицательное число, которое меньше указанного значения.
  • Next(Int32 min, Int32 max) - возвращает случайное целое число в указанном диапазоне. При этом должно соблюдаться условие min
А также методы
  • NextBytes(Byte ) - заполняет элементы указанного массива байтов случайными числами.
  • NextDouble() - возвращает случайное число с плавающей запятой, в диапазоне )
    break ; // совпадение найдено, элемент не подходит
    }
    if (j == i)
    { // совпадение не найдено
    a[i] = num; // сохраняем элемент
    i++; // переходим к следующему элементу
    }
    }
    for (int i = 0; i < 100; i++)
    {

    if (i % 10 == 9)
    Console .WriteLine();
    }
    Console .ReadKey();
    }
    }
    }

    Однако чем ближе к концу массива, тем больше генераций необходимо производить для получения неповторяющегося значения.
    Следующий пример отображает количество вызовов метода Next() для получения каждого элемента, а также общее количество сгенерированных случайных чисел для заполнения массива из 100 элементов неповторяющимися значениями.

    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53

    using System;
    namespace MyProgram
    {
    class Program
    {
    static void Main(string args)
    {
    Random rnd = new Random ();
    int a = new int ; // массив элементов
    int count = new int ; // массив количества генераций
    a = rnd.Next(0, 101);
    int c = 0; // счетчик количества генераций
    count = 1; // a генерируется только 1 раз
    for (int i = 1; i < 100;)
    {
    int num = rnd.Next(0, 101);
    c++; // сгенерировали элемент еще один раз
    int j;
    for (j = 0; j < i; j++)
    {
    if (num == a[j])
    break ;
    }
    if (j == i)
    {
    a[i] = num; i++;
    count[i] = c; c = 0; // сохраняем количество генераций
    }
    }
    // Вывод значений элементов
    Console .WriteLine("Значения элементов" );
    for (int i = 0; i < 100; i++)
    {
    Console .Write("{0,4} " , a[i]);
    if (i % 10 == 9)
    Console .WriteLine();
    }
    Console .WriteLine();
    // Вывод количества генераций
    Console .WriteLine("Количество генераций элементов" );
    int sum = 0;
    for (int i = 0; i < 100; i++)
    {
    sum += count[i];
    Console .Write("{0,4} " , count[i]);
    if (i % 10 == 9)
    Console .WriteLine();
    }
    Console .WriteLine("Общее количество генераций - {0}" , sum);
    Console .ReadKey();
    }
    }
    }

    void Main(string args)
    {
    Random rnd = new Random ();
    int a = new int ;
    for (int i = 0; i < 100; i++)
    a[i] = i;
    for (int i = 0; i < 50; i++)
    {
    int i1 = rnd.Next(0, 100); // первый индекс
    int i2 = rnd.Next(0, 100); // второй индекс
    // обмен значений элементов с индексами i1 и i2
    int temp = a;
    a = a;
    a = temp;
    }
    Console .WriteLine("Значения элементов" );
    for (int i = 0; i < 100; i++)
    {
    Console .Write("{0,4} " , a[i]);
    if (i % 10 == 9)
    Console .WriteLine();
    }
    Console .ReadKey();
    }
    }
    }

    Перемешивание значений является более эффективным если диапазон значений совпадает с их количеством (или близок к нему), поскольку в этом случае значительно сокращается количество генераций случайных элементов.

    Функция, генерирующая псевдослучайные числа, имеет прототип в файле библиотеки 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 с глобальной областью видимости.

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

    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
    #include
    #include
    #define SIZE 20
    int main() {
    int a;
    srand(time(NULL ));
    for (int i = 0; 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
    #include
    #include
    #define SIZE 20
    int main() {
    int a;
    srand(time(NULL ));

    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;
    a = a;
    a = temp;
    }
    printf("\n" );

    for (int i = 0; i < SIZE; i++)
    printf("%2d " , a[i]);
    getchar();
    return 0;
    }


    Результат выполнения


    Часто возникает задача произвольного выбора ранее заданных элементов массива. Причем необходимо предусмотреть отсутствие повторений в выборе этих элементов.
    Алгоритм такого выбора состоит в следующем:

    • Выбираем произвольно индекс элемента массива
    • Если элемент с таким индексом уже был ранее выбран, двигаемся вправо, пока не дойдём до следующего не выбранного элемента. При этом следим за тем, чтобы "движение вправо" не вышло за границы массива. Если фиксируется выход за границы массива, начинаем просмотр элементов массива с начала.
    • Выбираем элемент
    • Фиксируем элемент как выбранный
    • Повторяем указанные действия для всех остальных элементов

    Реализации на Си
    В результате получаем новый массив b , сформированный произвольной выборкой элементов массива a .

    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
    32
    33

    #include
    #include
    #include
    #define SIZE 20
    int main() {
    int a;
    int b; // результирующий массив
    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 == -1) // пока элемент "выбран"
    {
    ind++; // двигаемся вправо
    ind %= 20; // если дошли до правой границы, возвращаемся в начало
    }
    b[i] = a; // записываем следующий элемент массива b
    a = -1; // отмечаем элемент массива a как "выбранный"
    }
    printf("\n" );
    // Выводим получившийся массив
    for (int i = 0; i < SIZE; i++)
    printf("%2d " , b[i]);
    getchar();
    return 0;
    }


    Результат выполнения

    Приветствую всех, кто заскочил. В это короткой заметке будет пара слов о генерации псевдослучайных чисел на C/C++. В частности о том, как работать с самой простой функцией генерации — rand().

    Функция rand()

    Находится в стандартной библиотеке С++(stdlib.h). Генерирует и возвращает псевдослучайное число в диапазоне от 0 до RAND_MAX . Эта константа может отличаться в зависимости от компилятора или архитектуры процессора, в основном, это максимальное значение типа данных unsigned int . Параметров не принимает и никогда не принимала.

    Для того, чтобы генерация свершилась, нужно выставить семя(seed) с помощью вспомогательной функции из той же библиотеки — srand() . Она принимает число и ставит его в качестве отправной точки в генерации случайного числа. Если семя не выставить, то при каждом запуске программы, мы будет получать одинаковые случайные числа. Самым очевидным решением является отправить туда текущее системное время. Сделать это можно с помощью функции time(NULL). Эта функция находится в библиотеке time.h .

    С теорией разобрались, нашли все функции для генерации случайных чисел, теперь давайте погенерируем.

    Пример использования функции генерации случайных чисел rand()

    #include #include #include using namespace std; int main() { srand(time(NULL)); for(int i = 0; i < 10; i++) { cout << rand() << endl; } return 0; }

    Ранд нагенерировал нам 10 случайных чисел. В том, что они случайные вы можете убедиться, запуская программу вновь и вновь. Но этого недостаточно, поэтому нужно поговорить о диапазоне.

    Выставить границы диапазона для rand()

    Чтобы сгенерировать число в диапазоне от A до B включительно, нужно написать так:

    A + rand() % ((B + 1) - A);

    Значения границ могут быть в том числе и отрицательными, что позволяет генерировать отрицательное случайное число, посмотрим пример.

    #include #include #include using namespace std; int main() { srand(time(NULL)); int A = -2; int B = 8; for(int i = 0; i < 100; i++) { cout << A + rand() % ((B + 1) - A) << endl; } return 0; }