Вероятностни алгоритми Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми Теоретична част



Дата22.07.2016
Размер21.17 Kb.
ТипЗадача
ЛУ-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. Да се състави програма, която имитира хвърлянето на: един зар; два зара едновременно; един зар – два пъти и два зара – два пъти.
Каталог: docs -> Bachelor -> II%20Kurs -> Sem%20IV -> SAA
SAA -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми
SAA -> Дървета Цел
SAA -> Евристически алгоритми
SAA -> Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
SAA -> Цел: Запознаване с метода за създаване на ефективно по – рекурсия. Създаване и използване на рекурсивни функции при решаване на сложни задачи. Теоретична част
SAA -> Лекция №3 Сложност на алгоритмите
SAA -> Задача за "Ход на коня". Задача 1: Ход на коня
SAA -> Усвояне на похватите за представяне на графи в по, програмна реализация на графи и решаване на задачи над графи
SAA -> Сортировка чрез вмъкване


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница