Pomoce:

Instalacja Code Blocks i tworzenie projektu aplikacji konsoli.
Wprowadzenie do języka C++, strumienie i zmienne
Komputer podejmuje decyzje
Pętle warunkowe
Pętla iteracyjna

Liczby pseudolosowe

Liczba losowa (ang. random number) jest liczbą r należącą do pewnego zbioru wartości {r1, ..., rn} wybieranych z pewnym prawdopodobieństwem. Jeśli jako r może pojawić się każda z liczb zbioru z tym samym prawdopodobieństwem p(r) = 1/n, to mówimy o równomiernym rozkładzie prawdopodobieństwa liczb losowych z tego zbioru. Na przykład rozważmy rzut kostką. Każdy rzut daje liczbę losową r ze zbioru {1,2,3,4,5,6}. Jeśli kostka nie jest oszukana, to każda z możliwych wartości r pojawia się w rzucie kostką z prawdopodobieństwem p(r) = 1/6. Liczby losowe r posiadają zatem równomierny rozkład prawdopodobieństwa.

Problem z otrzymaniem liczb losowych wynika z deterministycznego charakteru komputera i wykonywanych przez niego operacji. Gdy człowiek dokonuje rzutu kością, nie wie co wypadnie. Taka sama operacja na komputerze wymaga działania, którego wynik jest nieprzewidywalny - żadna z operacji wykonywanych przez procesor nie posiada takiej cechy (o ile procesor jest sprawny). Problem starano się rozwiązać wykorzystując zewnętrzne źródła sygnałów losowych (np. generatory białego szumu), jednakże w tego typu urządzenia nie są standardowo wyposażano komputery osobiste - należałoby wspomnieć o próbach wykorzystania szumów kart graficznych, jednakże system ten nie rozpowszechnił się z prostej przyczyny - różne karty dźwiękowe szumią różnie, a te z górnej półki nie szumią prawie wcale. Dlatego osiągane wyniki nie były jednakowe i pomysł zarzucono.

Z drugiej strony liczby losowe używane są powszechnie przy programowaniu komputerów - gry losowe, symulacje różnych procesów losowych, statystycznych, testowanie algorytmów dla losowych zestawów danych itp. Ponieważ nie możemy w prosty sposób mieć prawdziwych liczb losowych, musimy się zadowolić ich sztucznym odpowiednikiem - liczbami pseudolosowymi (ang. pseudorandom numbers). Liczby pseudolosowe wyglądają jak losowe, lecz tworzy się je algorytmicznie. Oznacza to, iż znając wzór generacyjny oraz kilka kolejnych liczb pseudolosowych możemy bez problemu wygenerować wszystkie dalsze - tej cechy nie posiadają liczby losowe, w przeciwnym razie totolotek straciłby sens.

 

Generatory LCG

Do rozwiązania problemu generacji liczb pseudolosowych opracowano specjalne funkcje modularne zwane liniowymi generatorami kongruencyjnymi liczb pseudolosowych (ang. pseudorandom number linear congruential generator - w skrócie LCG) o następującej postaci:

 

Xn = (a × Xn-1 + c) mod m
Xn  - n-ta liczba pseudolosowa
Xn-1  - poprzednia liczba pseudolosowa
a  - mnożnik
c  - przyrost
m  - moduł

 

Ze wzoru wynika, iż kolejna liczba pseudolosowa Xn powstaje z poprzedniej Xn-1. Liczby te tworzą zatem ściśle określony ciąg kolejno następujących po sobie wartości.

Drugą cechą charakterystyczną jest to, iż liczba pseudolosowa Xn jest resztą z dzielenia przez moduł m. Skoro tak, to może przyjmować wartości od 0 do m - 1. Z pierwszej i drugiej własności wynika, iż po m cyklach obliczeniowych, liczby pseudolosowe zaczynają się powtarzać:

 

X0X1X2 → ...  → Xm-2  → Xm-1 X0X1 ...

 

Jeśli współczynniki a, c i m są źle dobrane, to cykl powtarzania może być krótszy niż m.

 

Rozróżniamy dwa podstawowe rodzaje generatorów LCG:

 

Addytywny LCG: Xn = (aXn-1 + c) mod m
Multiplikatywny LCG:: Xn = aXn-1 mod m

 

Podstawowa różnica pomiędzy nimi jest taka, iż generator addytywny LCG może generować liczby pseudolosowe z zakresu od 0 do m - 1, a generator multiplikatywne generuje je z zakresu od 1 do m - 1. Poniżej podajemy prosty algorytm doboru współczynników dla generatora LCG.

 

Określamy zakres liczb pseudolosowych 0...Xmax (dla LCG multiplikatywnego jest to 1...Xmax). Moduł m jest zawsze o 1 większy od maksymalnej liczby w zakresie, czyli:

 

m = Xmax + 1

 

Przyrost c musi być względnie pierwszy z modułem m. Możemy m rozłożyć na czynniki pierwsze i dla c wybieramy czynniki nie występujące w m. Możemy również generować pseudolosowe c i sprawdzać, czy spełnia warunek:

 

NWD(c,m) = 1

 

Mnożnik dobieramy wykorzystując regułę, iż wyrażenie a - 1 jest podzielne przez każdy czynnik pierwszy modułu m. Jeśli moduł m dzieli się przez 4, to a - 1 również powinno być podzielne przez 4.

 

Przykład:

Zaprojektować addytywny generator LCG generujący liczby pseudolosowe w przedziale od 0 do 11.

Z warunków zadania mamy:

 

Xmax = 11
m = Xmax + 1 = 11 + 1 = 12

 

Przyrost c musi być względnie pierwszy z m. Moduł m rozkładamy na iloczyn czynników pierwszych:

 

m = 2 × 2 × 3

 

Na przyrost c możemy wybrać dowolną liczbę nie posiadającą czynników 2 i 3. Na przykład może to być:

 

c = 7

 

Wyrażenie a - 1 musi być podzielne przez 4 i 3.

 

a - 1 = 4 × 3 = 12
a = 12 + 1 = 13

 

Otrzymujemy następujący wzór generatora LCG:    Xn = (13 × Xn-1 + 7) mod 12   → LCG(12,13,7)

 

Ponieważ wzór ten pozwala obliczyć kolejną liczbę pseudolosową Xn z liczby poprzedniej Xn-1, musimy określić wartość startową X0, od której rozpocznie się generacja liczb pseudolosowych. Wartość tę nazywamy ziarnem pseudolosowym (ang. pseudorandom seed). Ziarno wpływa na miejsce w pierścieniu liczb pseudolosowych, od którego rozpocznie się generacja następnych liczb.

Przyjmijmy X0 = 0 i policzmy wszystkie kolejne liczby pseudolosowe, które tworzy nasz generator LCG:

 

X1 = 13 ×   0 + 7 mod 12 =  7 mod 12 =  7  
X2 = 13 ×  7 + 7 mod 12 =  98 mod 12 =  2  
X3 = 13 ×  2 + 7 mod 12 =  33 mod 12 =  9  
X4 = 13 ×  9 + 7 mod 12 =  124 mod 12 =  4  
X5 = 13 ×  4 + 7 mod 12 =  59 mod 12 =  11  
X6 = 13 ×  11 + 7 mod 12 =  150 mod 12 =  6  
X7 = 13 ×  6 + 7 mod 12 =  85 mod 12 =  1  
X8 = 13 ×  1 + 7 mod 12 =  20 mod 12 =  8  
X9 = 13 ×  8 + 7 mod 12 =  111 mod 12 =  3  
X10 = 13 ×  3 + 7 mod 12 =  46 mod 12 =  10  
X11 = 13 ×  10 + 7 mod 12 =  137 mod 12 =  5  
X12 = 13 ×  5 + 7 mod 12 =  72 mod 12 =  0  
X13 = 13 ×  0 + 7 mod 12 =  7 mod 12 =  7  = X1 - ciąg zaczyna się powtarzać
X14 = 13 ×  7 + 7 mod 12 =   98 mod 12 =  2  = X2
...

 

Dla X0 = 0 otrzymaliśmy ciąg liczb pseudolosowych: 7 2 9 4 11 6 1 8 3 10 5 0 7 2 9 4 ...

Jeśli przyjmiemy inną wartość za X0, to otrzymamy ten sam ciąg, lecz startujący od innego punktu:

 

Dla X0 = 1 mamy : 8 3 10 5 0 7 2 9 4 11 6 1 ...
Dla X0 = 2 mamy : 9 4 11 6 1 8 3 10 5 0 7 2 ...
Dla X0 = 3 mamy : 10 5 0 7 2 9 4 11 6 1 8 3 ...

 

Następstwo kolejnych liczb pseudolosowych jest zawsze takie samo - np. po liczbie 3 zawsze wystąpi liczba 10.

Z powyższych rozważań można wyciągnąć wniosek, iż każdy generator LCG da się jednoznacznie scharakteryzować czwórką parametrów:

 

LCG(m,a,c,X0)
m - moduł
a - mnożnik
c - przyrost
X0 - ziarno

 

W praktycznych realizacjach dąży się do dużych okresów generatora LCG - wtedy liczby pseudolosowe powtarzają się dopiero po wielu miliardach przebiegów. Jako przykład niech posłuży poniższy generator LCG zaproponowany przez prof. D. Knutha:

 

LCG(34359738368, 3141592653, 2718281829, Xo)

m = 34359738368 = 235
a = [π × 109]
c = [e × 109],  e - podstawa logarytmów naturalnych, e = 2,7182818284590452353602874713527...

 

Program generujący ciąg liczb pseudolosowych

 

// Generator liczb pseudolosowych
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>

using namespace std;

int main()
{
    unsigned m,a,c,X0,i;

    cout << "m = "; cin >> m;
    cout << "a = "; cin >> a;
    cout << "c = "; cin >> c;
    cout << "X0= "; cin >> X0;

    cout << endl;

    // generujemy m + 5 liczb pseudolosowych

    for(i = 1; i <= m + 5; i++)
    {
        X0 = (a * X0 + c) % m;
        cout << X0 << " ";
    }

    cout << endl << endl;

    return 0;
}

 

Generator liczb pseudolosowych w języku C++

Język C++ posiada wbudowany dobry generator liczb pseudolosowych, do którego dostęp mamy za pomocą dwóch funkcji:

 

rand() -  zwraca kolejną liczbę pseudolosową w zakresie od 0 do RAND_MAX. Funkcja rand() i stała RAND_MAX zdefiniowane są w pliku nagłówkowym cstdlib. Plik ten należy dołączyć do każdego programu wykorzystującego tę funkcję. Stała RAND_MAX ma wartość 32767 (lecz w innych implementacjach C++ może być większa - zawsze to sprawdzaj!).
srand(X0) -  umożliwia zainicjowanie ziarna generatora pseudolosowego. Jeśli nie zainicjujemy X0, to funkcja rand() będzie generowała zawsze ten sam ciąg liczb pseudolosowych. Ziarno inicjujemy zwykle wartością zwracaną przez funkcję time(), ponieważ wartość ta przy każdym uruchomieniu programu będzie inna i w efekcie otrzymamy inny ciąg liczb pseudolosowych. Funkcja time() wymaga dołączenia pliku nagłówkowego time.h.

 

Generator pseudolosowy języka C++ pozwala nam uzyskiwać wartości pseudolosowe w zakresie od 0 do 32767. Poniższy program generuje 20 pierwszych liczb pseudolosowych:

 

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

int main()
{
    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() << endl;

    return 0;
}

 

Zwróć uwagę, iż przy każdym uruchomieniu programu są to te same liczby:

 

   41
18467
 6334
26500
19169
15724
11478
29358
26962
24464

 

Spowodowane jest to tym, iż ziarno generatora zawsze startuje od takiej samej wartości. Aby to zmienić, musimy je na początku programu zainicjować wartością, która będzie przy każdym uruchomieniu inna. Tutaj wykorzystujemy funkcję time(), która zwraca wartość bieżącego czasu. Istotne dla nas jest jedynie to, iż wartość ta różni się przy każdym uruchomieniu programu, gdyż czas nieubłaganie płynie do przodu. Wynik funkcji time() jest ziarnem generatora i przekazujemy go jako parametr do funkcji srand(), która ustawi to ziarno.

 

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() << endl;

    return 0;
}

 

Teraz każde uruchomienie daje inny ciąg liczb pseudolosowych. Generator pseudolosowy należy inicjować nowym ziarnem tylko raz, na samym początku programu.

 

Generacja liczb pseudolosowych o zadanym zakresie

Funkcja rand() zwraca nam liczby pseudolosowe o zakresie od 0 do 32767. Jeśli chcemy mieć mniejszy zakres tych liczb, np. od 0 do m - 1, m < 32768, to wynik funkcji rand() poddajemy operacji modulo m:

 

rand() % m  - daje liczby pseudolosowe w zakresie od 0 do m - 1.

 

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    int m;

    cout << "m = "; cin >> m;

    cout << endl;

    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << rand() % m << endl;

    return 0;
}

 

Jeśli liczby pseudolosowe mają być generowane w zakresie od a do b, to stosujemy wzór:

 

a + rand() % (b - a + 1) - daje liczby pseudolosowe w zakresie od a do b włącznie.

 

// Liczby pseudolosowe w C++
// (C)2010 I LO w Tarnowie
//-------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

int main()
{
    int a,b;

    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;

    cout << endl;

    srand(time(NULL));

    for(int i = 1; i <= 20; i++) cout << setw(5) << a + rand() % (b - a + 1) << endl;

    return 0;
}

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.