Генериране на случайни числа на езика C. Генериране на (псевдо)случайни числа Използвайте един екземпляр на класа Random за множество повиквания

Генериране на случайни числа на езика C. Генериране на (псевдо)случайни числа Използвайте един екземпляр на класа Random за множество повиквания
Генериране на случайни числа на езика C. Генериране на (псевдо)случайни числа Използвайте един екземпляр на класа Random за множество повиквания
30.11.2023

Превод на статията Случайни числа от Джон Скийт, широко известен в тесни кръгове. Спрях се на тази статия, защото по едно време самият аз се сблъсках с проблема, описан в нея.

Преглеждане на теми от .NETИ ° С#на уебсайта StackOverflow можете да видите безброй въпроси, в които се споменава думата „случаен“, които всъщност повдигат същия вечен и „неразрушим“ въпрос: защо генераторът на случайни числа System.Random „не работи“ и как да „ оправи го" " Тази статия е посветена на разглеждането на този проблем и начините за неговото решаване.

Формулиране на проблема

В StackOverflow, в дискусионни групи и пощенски списъци, всички въпроси по темата „случаен“ звучат по следния начин:
Използвам Random.Next за генериране на множество произволни числа, но методът връща едно и също число, когато се извиква многократно. Броят се променя при всяко стартиране на приложението, но в рамките на едно изпълнение на програмата е постоянен.

Примерен код е нещо подобно:
// Лош код! Не използвай! за (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 с едно и също начално състояние, което е указано чрез параметъра на конструктора семе, и за всеки екземпляр извикайте определени методи в същия ред и с едни и същи параметри, тогава в крайна сметка ще получите същите резултати.

И така, какво не е наред с горния код? Лошото е, че използваме нов екземпляр на класа Random във всяка итерация на цикъла. Конструкторът Random, който не приема параметри, приема текущата дата и час като начално. Итерациите в цикъла ще се „превъртат“ толкова бързо, че системното време „няма да има време да се промени“ след тяхното завършване; по този начин всички екземпляри на Random ще получат същата стойност като първоначалното си състояние и следователно ще върнат едно и също псевдослучайно число.

Как да го оправя?

Има много решения на проблема, всяко със своите плюсове и минуси. Ще разгледаме няколко от тях.
Използване на криптографски генератор на произволни числа
.NET съдържа абстрактен клас RandomNumberGenerator, от който всички реализации на криптографски генератори на произволни числа (наричани по-нататък cryptoRNGs) трябва да наследяват. .NET също съдържа една от тези реализации - отговаря на класа RNGCryptoServiceProvider. Идеята на крипто-RNG е, че дори ако все още е генератор на псевдослучайни числа, той осигурява доста силна непредсказуемост на резултатите. RNGCryptoServiceProvider използва множество източници на ентропия, които по същество са „шум“ във вашия компютър, а последователността от числа, които генерира, е много трудна за предсказуемост. Нещо повече, "вътрешният компютърен" шум може да се използва не само като първоначално състояние, но и между повикванията към последващи произволни числа; по този начин, дори да се знае текущото състояние на класа, няма да е достатъчно да се изчислят както следващите числа, които ще бъдат генерирани в бъдеще, така и тези, които са били генерирани преди това. Всъщност точното поведение зависи от изпълнението. Освен това Windows може да използва специализиран хардуер, който е източник на „истинска произволност“ (например сензор за разпадане на радиоактивни изотопи), за да генерира още по-сигурни и надеждни произволни числа.

Нека сравним това с предишния обсъден клас Random. Да приемем, че сте извикали Random.Next(100) десет пъти и сте запазили резултатите. Ако имате достатъчно изчислителна мощност, можете, въз основа единствено на тези резултати, да изчислите първоначалното състояние (seed), с което е създаден произволният екземпляр, да предвидите следващите резултати от извикването на Random.Next(100) и дори да изчислите резултатите от предишни извиквания на метод. Това поведение е изключително неприемливо, ако използвате произволни числа за сигурност, финансови цели и т.н. Крипто RNG работят значително по-бавно от класа Random, но генерират поредица от числа, всяко от които е по-независимо и непредвидимо от стойностите на другите.

В повечето случаи лошата производителност не нарушава сделката - лошият API е. RandomNumberGenerator е предназначен да генерира последователности от байтове - това е всичко. Сравнете това с методите на класа Random, където е възможно да се получи произволно цяло число, дробно число, а също и набор от байтове. Друго полезно свойство е възможността за получаване на случайно число в определен диапазон. Сравнете тези възможности с масива от произволни байтове, които генерира RandomNumberGenerator. Можете да коригирате ситуацията, като създадете своя собствена обвивка (обвивка) около RandomNumberGenerator, която ще преобразува произволни байтове в „удобен“ резултат, но това решение е нетривиално.

В повечето случаи обаче "слабостта" на класа Random е добре, ако можете да разрешите проблема, описан в началото на статията. Да видим какво можем да направим тук.

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

Има два начина за решаване на проблема. Първо, можем да използваме не екземпляр, а статично поле, съдържащо екземпляр на Random, и тогава горната част от кода ще създаде само един екземпляр и ще го използва, като го извиква толкова пъти, колкото е необходимо. Второ, можем напълно да премахнем създаването на случаен екземпляр от там, като го преместим „по-високо“, в идеалния случай до самия „върх“ на програмата, където ще бъде създаден единичен случаен екземпляр, след което ще бъде прехвърлен на всички места където са необходими произволни числа. Това е страхотна идея, добре изразена чрез зависимости, но ще работи, докато използваме само една нишка.

Безопасност на резбата

Класът Random не е безопасен за нишки. Имайки предвид колко обичаме да създаваме единичен екземпляр и да го използваме в цялата програма за цялото времетраене на нейното изпълнение (singleton, здравей!), липсата на безопасност на нишката се превръща в истинска болка в задника. В крайна сметка, ако използваме един екземпляр едновременно в няколко нишки, тогава има вероятност вътрешното му състояние да бъде нулирано и ако това се случи, тогава от този момент нататък екземплярът ще стане безполезен.

Отново има два начина за решаване на проблема. Първият път все още включва използването на един екземпляр, но този път чрез заключване на ресурс чрез монитор. За да направите това, трябва да създадете обвивка около Random, която ще обвива извикванията към неговите методи в оператор за заключване, осигурявайки изключителен достъп до екземпляра за повикващия. Този път е лош, защото намалява производителността в сценарии с интензивно използване на нишки.

Друг начин, който ще опиша по-долу, е да използвате един екземпляр на нишка. Единственото нещо, което трябва да сме сигурни е, че използваме различни семена, когато създаваме екземпляри, така че не можем да използваме конструктори по подразбиране. В противен случай този път е сравнително лесен.

Сигурен доставчик

За щастие, новият общ клас ThreadLocal , въведен в .NET 4, прави много лесно писането на доставчици, които предоставят един екземпляр на нишка. Просто трябва да предадете делегат на конструктора ThreadLocal, който ще се отнася за получаване на стойността на самия екземпляр. В този случай реших да използвам една начална стойност, като я инициализирам с помощта на Environment.TickCount (което е точно как работи Random конструкторът без параметри). След това полученият брой отметки се увеличава всеки път, когато трябва да получим нов произволен екземпляр за отделна нишка.

Класът по-долу е напълно статичен и съдържа само един публичен (отворен) метод GetThreadRandom. Този метод е направен метод, а не свойство, главно за удобство: това ще гарантира, че всички класове, които се нуждаят от екземпляр на Random, ще зависят от Func (делегат, сочещ към метод, който не приема параметри и връща стойност от тип Random), а не от самия клас Random. Ако даден тип е предназначен да работи в една нишка, той може да извика делегат, за да получи единичен екземпляр на Random и след това да го използва навсякъде; ако типът трябва да работи в многонишкови сценарии, той може да извиква делегата всеки път, когато се нуждае от генератор на произволни числа. Класът по-долу ще създаде толкова екземпляри на класа Random, колкото има нишки, и всеки екземпляр ще започне от различна начална стойност. Ако трябва да използваме доставчика на произволни числа като зависимост в други типове, можем да направим това: new TypeThatNeedsRandom(RandomProvider.GetThreadRandom) . Е, ето и самия код:
използване на системата; използване на System.Threading; публичен статичен клас RandomProvider ( private static int seed = Environment.TickCount; private static ThreadLocal randomWrapper = нов ThreadLocal (() => ново произволно(Interlocked.Increment(ref seed))); public static Random GetThreadRandom() ( return randomWrapper.Value; ) )
Достатъчно просто, нали? Това е така, защото целият код е насочен към създаване на правилното копие на Random. След като един екземпляр бъде създаден и върнат, няма значение какво правите с него след това: всички следващи издавания на екземпляри са напълно независими от текущия. Разбира се, клиентският код има вратичка за злонамерена злоупотреба: той може да вземе едно копие на Random и да го предаде на други нишки, вместо да извиква нашия RandomProvider на тези други нишки.

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

Един проблем все още остава: ние използваме слабо защитен генератор на случайни числа. Както споменахме по-рано, има много по-сигурна версия на RNG в RandomNumberGenerator, чиято реализация е в класа RNGCryptoServiceProvider. Неговият API обаче е доста труден за използване в стандартни сценарии.

Би било много хубаво, ако доставчиците на RNG в рамките имат отделни „източници на произволност“. В този случай бихме могли да имаме един-единствен, прост и удобен API, който ще се поддържа както от несигурната, но бърза реализация, така и от сигурната, но бавна. Е, няма нищо лошо в сънуването. Може би подобна функционалност ще се появи в бъдещите версии на .NET Framework. Може би някой, който не е от Microsoft, ще предложи собствена реализация на адаптера. (За съжаление, аз няма да съм този човек... правилното внедряване на нещо подобно е изненадващо сложно.) Можете също така да създадете свой собствен клас, като извлечете от Random и замените методите Sample и NextBytes, но не е ясно как точно трябва да работа или дори вашата собствена извадка за внедряване може да бъде много по-сложна, отколкото изглежда. Може би следващия път…

В образователните алгоритмични проблеми необходимостта от генериране на произволни цели числа е доста често срещана. Разбира се, можете да ги получите от потребителя, но може да възникнат проблеми с попълването на масива със 100 произволни числа.

На помощ ни идва стандартната библиотечна функция на езика C (не C++) rand().

int rand(void);

Той генерира псевдослучайно цяло число в диапазона от стойности от 0 до RAND_MAX. Последното е константа, която варира в зависимост от реализацията на езика, но в повечето случаи е 32767.
Ами ако имаме нужда от произволни числа от 0 до 9? Типичен изход от тази ситуация е да се използва операцията за деление по модул.

Ако имаме нужда от числа от 1 (не 0) до 9, тогава можем да добавим едно...

Идеята е следната: генерираме произволно число от 0 до 8 и след добавяне на 1 то се превръща в произволно число от 1 до 9.

И последно най-тъжното.
За съжаление функцията rand() генерира псевдослучайни числа, т.е. числа, които изглеждат произволни, но всъщност са поредица от стойности, изчислени с помощта на умен алгоритъм, който приема така нареченото зърно като параметър. Тези. Числата, генерирани от функцията rand(), ще зависят от стойността, която зърното има в момента на извикването му. И зърното винаги се задава от компилатора на стойност 1. С други думи, последователността от числа ще бъде псевдослучайна, но винаги една и съща.
И това не е това, от което се нуждаем.

Функцията srand() помага да се коригира ситуацията.

void srand(unsigned int seed);

Той задава зърното равно на стойността на параметъра, с който е извикан. И последователността от числа също ще бъде различна.

Но проблемът си остава. Как да направим зърното случайно, защото всичко зависи от него?
Типичен изход от тази ситуация е използването на функцията time().

time_t време (time_t* таймер);

Той също е наследен от езика C и, когато се извиква с нулев указател като параметър, връща броя секунди, изминали от 1 януари 1970 г. Не, това не е шега.

Сега можем да предадем стойността на тази функция във функцията srand() (която прави имплицитно прехвърляне) и ще имаме прекрасно произволно зърно.
И номерата ще бъдат прекрасни и неповтарящи се.

За да използвате функциите rand() и srand(), трябва да включите заглавен файл , и да използвате time() - файл .

Ето пълен пример.

#включи
#включи
#включи

използване на пространство от имена std;

int main()
{
cout<< "10 random numbers (1..100): " << endl;
srand(време(NULL));
за (int i=0;i<10;i++) cout << rand() % 100 + 1 << " ";
cin.get();
връщане 0;
}

Превод на статията Случайни числа от Джон Скийт, широко известен в тесни кръгове. Спрях се на тази статия, защото по едно време самият аз се сблъсках с проблема, описан в нея.

Преглеждане на теми от .NETИ ° С#на уебсайта StackOverflow можете да видите безброй въпроси, в които се споменава думата „случаен“, които всъщност повдигат същия вечен и „неразрушим“ въпрос: защо генераторът на случайни числа System.Random „не работи“ и как да „ оправи го" " Тази статия е посветена на разглеждането на този проблем и начините за неговото решаване.

Формулиране на проблема

В StackOverflow, в дискусионни групи и пощенски списъци, всички въпроси по темата „случаен“ звучат по следния начин:
Използвам Random.Next за генериране на множество произволни числа, но методът връща едно и също число, когато се извиква многократно. Броят се променя при всяко стартиране на приложението, но в рамките на едно изпълнение на програмата е постоянен.

Примерен код е нещо подобно:
// Лош код! Не използвай! за (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 с едно и също начално състояние, което е указано чрез параметъра на конструктора семе, и за всеки екземпляр извикайте определени методи в същия ред и с едни и същи параметри, тогава в крайна сметка ще получите същите резултати.

И така, какво не е наред с горния код? Лошото е, че използваме нов екземпляр на класа Random във всяка итерация на цикъла. Конструкторът Random, който не приема параметри, приема текущата дата и час като начално. Итерациите в цикъла ще се „превъртат“ толкова бързо, че системното време „няма да има време да се промени“ след тяхното завършване; по този начин всички екземпляри на Random ще получат същата стойност като първоначалното си състояние и следователно ще върнат едно и също псевдослучайно число.

Как да го оправя?

Има много решения на проблема, всяко със своите плюсове и минуси. Ще разгледаме няколко от тях.
Използване на криптографски генератор на произволни числа
.NET съдържа абстрактен клас RandomNumberGenerator, от който всички реализации на криптографски генератори на произволни числа (наричани по-нататък cryptoRNGs) трябва да наследяват. .NET също съдържа една от тези реализации - отговаря на класа RNGCryptoServiceProvider. Идеята на крипто-RNG е, че дори ако все още е генератор на псевдослучайни числа, той осигурява доста силна непредсказуемост на резултатите. RNGCryptoServiceProvider използва множество източници на ентропия, които по същество са „шум“ във вашия компютър, а последователността от числа, които генерира, е много трудна за предсказуемост. Нещо повече, "вътрешният компютърен" шум може да се използва не само като първоначално състояние, но и между повикванията към последващи произволни числа; по този начин, дори да се знае текущото състояние на класа, няма да е достатъчно да се изчислят както следващите числа, които ще бъдат генерирани в бъдеще, така и тези, които са били генерирани преди това. Всъщност точното поведение зависи от изпълнението. Освен това Windows може да използва специализиран хардуер, който е източник на „истинска произволност“ (например сензор за разпадане на радиоактивни изотопи), за да генерира още по-сигурни и надеждни произволни числа.

Нека сравним това с предишния обсъден клас Random. Да приемем, че сте извикали Random.Next(100) десет пъти и сте запазили резултатите. Ако имате достатъчно изчислителна мощност, можете, въз основа единствено на тези резултати, да изчислите първоначалното състояние (seed), с което е създаден произволният екземпляр, да предвидите следващите резултати от извикването на Random.Next(100) и дори да изчислите резултатите от предишни извиквания на метод. Това поведение е изключително неприемливо, ако използвате произволни числа за сигурност, финансови цели и т.н. Крипто RNG работят значително по-бавно от класа Random, но генерират поредица от числа, всяко от които е по-независимо и непредвидимо от стойностите на другите.

В повечето случаи лошата производителност не нарушава сделката - лошият API е. RandomNumberGenerator е предназначен да генерира последователности от байтове - това е всичко. Сравнете това с методите на класа Random, където е възможно да се получи произволно цяло число, дробно число, а също и набор от байтове. Друго полезно свойство е възможността за получаване на случайно число в определен диапазон. Сравнете тези възможности с масива от произволни байтове, които генерира RandomNumberGenerator. Можете да коригирате ситуацията, като създадете своя собствена обвивка (обвивка) около RandomNumberGenerator, която ще преобразува произволни байтове в „удобен“ резултат, но това решение е нетривиално.

В повечето случаи обаче "слабостта" на класа Random е добре, ако можете да разрешите проблема, описан в началото на статията. Да видим какво можем да направим тук.

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

Има два начина за решаване на проблема. Първо, можем да използваме не екземпляр, а статично поле, съдържащо екземпляр на Random, и тогава горната част от кода ще създаде само един екземпляр и ще го използва, като го извиква толкова пъти, колкото е необходимо. Второ, можем напълно да премахнем създаването на случаен екземпляр от там, като го преместим „по-високо“, в идеалния случай до самия „върх“ на програмата, където ще бъде създаден единичен случаен екземпляр, след което ще бъде прехвърлен на всички места където са необходими произволни числа. Това е страхотна идея, добре изразена чрез зависимости, но ще работи, докато използваме само една нишка.

Безопасност на резбата

Класът Random не е безопасен за нишки. Имайки предвид колко обичаме да създаваме единичен екземпляр и да го използваме в цялата програма за цялото времетраене на нейното изпълнение (singleton, здравей!), липсата на безопасност на нишката се превръща в истинска болка в задника. В крайна сметка, ако използваме един екземпляр едновременно в няколко нишки, тогава има вероятност вътрешното му състояние да бъде нулирано и ако това се случи, тогава от този момент нататък екземплярът ще стане безполезен.

Отново има два начина за решаване на проблема. Първият път все още включва използването на един екземпляр, но този път чрез заключване на ресурс чрез монитор. За да направите това, трябва да създадете обвивка около Random, която ще обвива извикванията към неговите методи в оператор за заключване, осигурявайки изключителен достъп до екземпляра за повикващия. Този път е лош, защото намалява производителността в сценарии с интензивно използване на нишки.

Друг начин, който ще опиша по-долу, е да използвате един екземпляр на нишка. Единственото нещо, което трябва да сме сигурни е, че използваме различни семена, когато създаваме екземпляри, така че не можем да използваме конструктори по подразбиране. В противен случай този път е сравнително лесен.

Сигурен доставчик

За щастие, новият общ клас ThreadLocal , въведен в .NET 4, прави много лесно писането на доставчици, които предоставят един екземпляр на нишка. Просто трябва да предадете делегат на конструктора ThreadLocal, който ще се отнася за получаване на стойността на самия екземпляр. В този случай реших да използвам една начална стойност, като я инициализирам с помощта на Environment.TickCount (което е точно как работи Random конструкторът без параметри). След това полученият брой отметки се увеличава всеки път, когато трябва да получим нов произволен екземпляр за отделна нишка.

Класът по-долу е напълно статичен и съдържа само един публичен (отворен) метод GetThreadRandom. Този метод е направен метод, а не свойство, главно за удобство: това ще гарантира, че всички класове, които се нуждаят от екземпляр на Random, ще зависят от Func (делегат, сочещ към метод, който не приема параметри и връща стойност от тип Random), а не от самия клас Random. Ако даден тип е предназначен да работи в една нишка, той може да извика делегат, за да получи единичен екземпляр на Random и след това да го използва навсякъде; ако типът трябва да работи в многонишкови сценарии, той може да извиква делегата всеки път, когато се нуждае от генератор на произволни числа. Класът по-долу ще създаде толкова екземпляри на класа Random, колкото има нишки, и всеки екземпляр ще започне от различна начална стойност. Ако трябва да използваме доставчика на произволни числа като зависимост в други типове, можем да направим това: new TypeThatNeedsRandom(RandomProvider.GetThreadRandom) . Е, ето и самия код:
използване на системата; използване на System.Threading; публичен статичен клас RandomProvider ( private static int seed = Environment.TickCount; private static ThreadLocal randomWrapper = нов ThreadLocal (() => ново произволно(Interlocked.Increment(ref seed))); public static Random GetThreadRandom() ( return randomWrapper.Value; ) )
Достатъчно просто, нали? Това е така, защото целият код е насочен към създаване на правилното копие на Random. След като един екземпляр бъде създаден и върнат, няма значение какво правите с него след това: всички следващи издавания на екземпляри са напълно независими от текущия. Разбира се, клиентският код има вратичка за злонамерена злоупотреба: той може да вземе едно копие на Random и да го предаде на други нишки, вместо да извиква нашия RandomProvider на тези други нишки.

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

Един проблем все още остава: ние използваме слабо защитен генератор на случайни числа. Както споменахме по-рано, има много по-сигурна версия на RNG в RandomNumberGenerator, чиято реализация е в класа RNGCryptoServiceProvider. Неговият API обаче е доста труден за използване в стандартни сценарии.

Би било много хубаво, ако доставчиците на RNG в рамките имат отделни „източници на произволност“. В този случай бихме могли да имаме един-единствен, прост и удобен API, който ще се поддържа както от несигурната, но бърза реализация, така и от сигурната, но бавна. Е, няма нищо лошо в сънуването. Може би подобна функционалност ще се появи в бъдещите версии на .NET Framework. Може би някой, който не е от Microsoft, ще предложи собствена реализация на адаптера. (За съжаление, аз няма да съм този човек... правилното внедряване на нещо подобно е изненадващо сложно.) Можете също така да създадете свой собствен клас, като извлечете от Random и замените методите Sample и NextBytes, но не е ясно как точно трябва да работа или дори вашата собствена извадка за внедряване може да бъде много по-сложна, отколкото изглежда. Може би следващия път…

Моля, спрете AdBlock на този сайт.

Понякога може да е необходимо да се генерират произволни числа. Прост пример.

Пример: Определяне на победителя в конкурс за репост.

Има списък от 53 души. Необходимо е да изберете победител от тях. Ако го изберете сами, може да ви обвинят в пристрастност. Така че решавате да напишете програма. Ще работи по следния начин. Въвеждате броя на участниците N, след което програмата извежда едно число - номерът на победителя.

Вече знаете как да получите номер от играч. Но как можете да принудите компютъра да мисли за произволно число? В този урок ще научите как да направите това.

функция rand().

Тази функция връща произволно цяло число в диапазона от нула до RAND_MAX. RAND_MAX е специална C константа, която съдържа максималната целочислена стойност, която може да бъде върната от функцията rand().

Функцията rand() е дефинирана в заглавния файл stdlib.h. Следователно, ако искате да използвате rand във вашата програма, не забравяйте да включите този заглавен файл. Константата RAND_MAX също е дефинирана в този файл. Можете да намерите този файл на вашия компютър и да видите значението му.

Нека видим тази функция в действие. Нека изпълним следния код:

Списък 1.

#включи // за използване на функцията printf #include // за използване на функцията rand int main(void) ( /* генерира пет произволни цели числа */ printf("%d\n", rand()); printf("%d\n", rand()); printf ("%d\n", rand()); printf("%d\n", rand()); printf("%d\n", rand()); )

Трябва да изглежда нещо подобно.

Фиг.1 Пет произволни числа, генерирани от функцията rand

Но бихме искали да получим числа от 1 до 53, а не всички подред. Ето няколко трика, които ще ви помогнат да ограничите функцията rand().

Ограничете произволните числа отгоре.

Всеки, който е чакал в училище момента, в който математиката ще му бъде полезна, пригответе се. Моментът настъпи. За да ограничите произволните числа отгоре, можете да използвате операцията за получаване на остатъка от делението, която научихте в последния урок. Вероятно знаете, че остатъкът от деление на числа K винаги е по-малък от числото K. Например, разделянето на 4 може да доведе до остатъци от 0, 1, 2 и 3. Следователно, ако искате да ограничите произволните числа отгоре до числото K, тогава просто вземете остатъка от деленето на K. Като този:

Списък 2.

#включи #включи int main(void) ( /* генерира пет произволни цели числа, по-малки от 100 */ printf("%d\n", rand()%100); printf("%d\n", rand()%100); printf ("%d\n", rand()%100); printf("%d\n", rand()%100); printf("%d\n", rand()%100); )


Фиг.2 Пет произволни числа по-малки от 100

Ограничете числата по-долу.

Функцията rand връща произволни числа от интервала. Ами ако се нуждаем само от числа, по-големи от M (например 1000)? Какво трябва да направя? Просто е. Нека просто добавим нашата стойност M към това, което върна функцията rand. След това, ако функцията върне 0, крайният отговор ще бъде M, ако 2394, тогава крайният отговор ще бъде M + 2394. С това действие изглежда преместваме всички числа напред с M единици.

Задайте горната и долната граница на функцията rand.

Например вземете числа от 80 до 100. Изглежда, че просто трябва да комбинирате двата метода по-горе. Ще получим нещо подобно:

Списък 3.

#включи #включи int main(void) ( /* генерира пет произволни цели числа, по-големи от 80 и по-малки от 100 */ printf("%d\n", 80 + rand()%100); printf("%d\n", 80 + rand ()%100); printf("%d\n", 80 + rand()%100); printf("%d\n", 80 + rand()%100); printf("%d\n " , 80 + rand()%100); )

Опитайте да стартирате тази програма. изненадан?

Да, този метод няма да работи. Нека стартираме тази програма на ръка, за да видим дали сме направили грешка. Да кажем, че rand() върна числото 143. Остатъкът при разделяне на 100 е 43. Тогава 80 + 43 = 123. Така че този метод не работи. Подобен дизайн ще произвежда числа от 80 до 179.

Нека разбием нашия израз стъпка по стъпка. rand()%100 може да върне числа от 0 до 99 включително. Тези. от сегмента.
Операция + 80 измества нашия сегмент 80 единици надясно. Получаваме.
Както можете да видите, нашият проблем е в дясната граница на сегмента; тя е изместена надясно със 79 единици. Това е нашето оригинално число 80 минус 1. Нека изчистим нещата и преместим дясната граница назад: 80 + rand()%(100 - 80 + 1) . Тогава всичко трябва да работи както трябва.

Като цяло, ако трябва да получим числа от сегмента, тогава трябва да използваме следната конструкция:
A + rand()%(B-A+1) .

Съгласно тази формула ще пренапишем последната ни програма:

Списък 4.

#включи #включи int main(void) ( /* генерира пет произволни цели числа от сегмента */ printf("%d\n", 80 + rand()%(100 - 80 + 1)); printf("%d\n", 80 + rand()%(100 - 79)); printf("%d\n", 80 + rand()%21); printf("%d\n", 80 + rand()%21); printf ("%d\n", 80 + rand()%21); )

Резултат:


Фиг.3 Случайни числа от диапазон

Е, сега можете да решите първоначалната задача от урока. Генериране на число от сегмент. Или не можеш?

Но първо малко по-полезна информация. Стартирайте последната програма три пъти подред и запишете произволните числа, които генерира. Забеляза ли?

Функция srand().

Да, всеки път се появяват едни и същи идентични числа. „Тъй-така генератор!“ - ти каза. И няма да сте съвсем прави. Всъщност едни и същи числа се генерират през цялото време. Но можем да повлияем на това, като използваме функцията srand(), която също е дефинирана в заглавния файл stdlib.h. Той инициализира генератора на произволни числа с начален номер.

Компилирайте и стартирайте тази програма няколко пъти:

Списък 5.

#включи #включи int main(void) ( srand(2); /* генерира пет произволни цели числа от сегмента */ printf("%d\n", 80 + rand()%(100 - 80 + 1)); printf("% d\n", 80 + rand()%(100 - 79)); printf("%d\n", 80 + rand()%21); printf("%d\n", 80 + rand() %21); printf("%d\n", 80 + rand()%21); )

Сега променете аргумента на функцията srand() на друго число (надявам се, че не сте забравили какво е аргумент на функция?) и компилирайте и стартирайте програмата отново. Поредицата от числа трябва да се промени. Веднага щом променим аргумента във функцията srand, последователността също се променя. Не е много практично, нали? За да промените последователността, трябва да прекомпилирате програмата. Само този номер да се вмъкне там автоматично.

И може да се направи. Например, нека използваме функцията time(), която е дефинирана в заглавния файл time.h. Тази функция, ако NULL се подаде като аргумент, връща броя секунди, изминали от 1 януари 1970 г. Ето един поглед как се прави.

Списък 6.

#включи #включи #включи // за използване на функцията time() int main(void) ( srand(time(NULL)); /* генерира пет произволни цели числа от сегмента */ printf("%d\n", 80 + rand()%( 100 - 80 + 1)); printf("%d\n", 80 + rand()%(100 - 79)); printf("%d\n", 80 + rand()%21); printf( " %d\n", 80 + rand()%21); printf("%d\n", 80 + rand()%21); )

Може да попитате какво е NULL? Резонен въпрос. Междувременно ще ви кажа каква е тази специална запазена дума. Мога също да кажа какво означава нулев указател, но... Това не ви предоставя никаква информация, така че препоръчвам да не мислите за това в момента. И просто го запомнете като някакъв хитър трик. В следващите уроци ще разгледаме това нещо по-подробно.

Много често в програмите има нужда от използване на произволни числа - от попълване на масив до криптография. За да се получи последователност от произволни числа, езикът C# има клас Random. Този клас предоставя два конструктора:

  • произволно()- инициализира екземпляр от класа Random с начална стойност, която зависи от текущото време. Както е известно, времето може да бъде представено в кърлежи- 100 наносекунди импулси от 1 януари 0001 г. А стойността на времето в тиковете е 64-битово цяло число, което ще се използва за инициализиране на екземпляра на генератора на произволни числа.
  • Произволен (Int32)- инициализира екземпляр на класа Random, използвайки зададената начална стойност. Инициализирането на генератор на произволни числа по този начин може да бъде удобно при отстраняване на грешки в програма, тъй като в този случай едни и същи „случайни“ числа ще се генерират всеки път, когато програмата се стартира.
Основният метод на този клас е методът Next(), който ви позволява да получите произволно число и има редица претоварвания:
  • Next() - връща произволно неотрицателно цяло число във формат Int32.
  • Следващия( Int32)- връща произволно неотрицателно цяло число, което е по-малко от зададената стойност.
  • Следващия( Int32 min, Int32 max)- връща произволно цяло число в посочения диапазон. В този случай трябва да е изпълнено условието min
А също и методи
  • NextBytes( байт)- запълва елементите на посочения байтов масив със случайни числа.
  • NextDouble() - връща произволно число с плаваща запетая в диапазона )
    прекъсване ; // намерено съвпадение, елементът не съвпада
    }
    ако (j == i)
    { // не е намерено съответствие
    a[i] = брой; // запазваме елемента
    i++; // отидете на следващия елемент
    }
    }
    за (int i = 0; i< 100; i++)
    {

    ако (i % 10 == 9)
    Console.WriteLine();
    }
    Конзола .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

    използване на системата;
    пространство от имена MyProgram
    {
    клас програма
    {
    static void Main(string args)
    {
    Random rnd = нов Random();
    int a = ново int; // масив от елементи
    int count = нов int; // масив от брой поколения
    a = rnd.Next(0, 101);
    int c = 0; // брояч на броя поколения
    брой = 1; // a се генерира само веднъж
    за (int i = 1; i< 100;)
    {
    int num = rnd.Next(0, 101);
    c++; // генерира елемента още веднъж
    int j;
    за (j = 0; j< i; j++)
    {
    if (num == a[j])
    прекъсване ;
    }
    ако (j == i)
    {
    a[i] = брой; i++;
    брой [i] = c; c = 0; // запазваме броя на поколенията
    }
    }
    // Отпечатване на стойности на елементи
    Конзола .WriteLine( „Стойности на елементи“);
    за (int i = 0; i< 100; i++)
    {
    Конзола .Write("(0,4) " , a[i]);
    ако (i % 10 == 9)
    Console.WriteLine();
    }
    Console.WriteLine();
    // Показване на броя на поколенията
    Конзола .WriteLine( „Брой генериране на елемент“);
    int сума = 0;
    за (int i = 0; i< 100; i++)
    {
    сума += брой[i];
    Конзола .Write("(0,4) " , count[i]);
    ако (i % 10 == 9)
    Console.WriteLine();
    }
    Конзола .WriteLine( "Общ брой поколения - (0)", сума);
    Конзола .ReadKey();
    }
    }
    }

    void Main (низови аргументи)
    {
    Random rnd = нов Random();
    int a = ново int;
    за (int i = 0; i< 100; i++)
    a[i] = i;
    за (int i = 0; i< 50; i++)
    {
    int i1 = rnd.Next(0, 100); // първи индекс
    int i2 = rnd.Next(0, 100); // втори индекс
    // обмен на стойности на елементи с индекси i1 и i2
    int temp = a;
    а = а;
    a = температура;
    }
    Конзола .WriteLine( „Стойности на елементи“);
    за (int i = 0; i< 100; i++)
    {
    Конзола .Write("(0,4) " , a[i]);
    ако (i % 10 == 9)
    Console.WriteLine();
    }
    Конзола .ReadKey();
    }
    }
    }

    Разбъркването на стойности е по-ефективно, ако диапазонът от стойности съвпада (или е близо до) броя на стойностите, тъй като в този случай броят на произволните генерирания на елементи е значително намален.