ЛУ-13:
Вероятностни алгоритми
Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми
Теоретична част:
Вероятностните алгоритми се илюстрират , както и други алгоритми, чрез решаване на вероятностни задачи. Една такава вероятностна задача е изборът на 13 произволни карти при игра на бридж. Тази задача спада към задачите за избот на М елемента от N съществуващи.[2].
Един подход за решавне на тази задача е обхождането на всички N елементи и избор на всеки от М-те елемента с вероятност M/N. Този подход е сравнително бавен и не гарантира, че след обхождането на N-те елемента, ше бъдат избрани точно M на брой.
Друг подход е генерирането на M на брой случайни числа и избирането на всяко генерирано случайно число, само ако до този момент не е било избрано (т.е., в множеството от M числа да няма повтарящи се). Този подход също е бавен, например, ако М=98, а N=100 и вече са избрани 97 числа.
Вероятностните алгоритми използват програмни генератори на псевдослучайни числа.
Генератори на случайни числа
Генераторите на случайни числа са програми, които образуват поредица от случайни числа, в зададен интервал, при определен закон на разпределение плътността на веоятностите.
Най-често се реализират и използват програми-генератори на равномерно разпредлени случайни числа в интервала [0..1), или в зададен числен интервал [0,m-1]. Една често използвана формула, предложена от Кнут, е следната[4]:
Yi=(A*Yi-1+C) mod M, (1)
Където А и С са подходящо избрани константи,Yo е начално число, което не се използва, но служи за “стартиране” на генерирането на следващите, вече случайни, числа.
Задача 1: Генериране на N на брой случайни цели числа
Задачата се формулира така: Да се напише програма на С/С++, която генерира N случайни числа в интервала [0..M-1] с използване на (1).
Примерен сорс-код на такава програма е даден на следващите редове.
// Програма за генериране на N случайни числа в интервала 0..M-1
// с използване на формулата Yi=(A*Yi-1+C) mod M
#include
void main(){
int N, M,Y0,Y;
cout<
cin>>N;
cout<cin>>M;
cout<cin>>А;
cout<cin>>C;
cout<cin>>Y0;
for (i=0;iY=(A*Y0+C) % M;
cout<
} }
Въпроси по темата и задачи за изпълнение:
1. Ако К1 е случайно число в интервала [0..0.9999], как може да се получи случайно число в интервала [0…M-1]?
2. Да се състави програма, която имитира хвърлянето на: един зар; два зара едновременно; един зар – два пъти и два зара – два пъти.
Сподели с приятели: |