Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2022 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Materiały dla klasy III

Liczby pseudolosowe

SPIS TREŚCI

Co to jest liczba pseudolosowa?

Liczba losowa (ang. random number) jest liczbą r  należącą do pewnego zbioru wartości {r1, ..., rn}, której konkretna wartość jest przypadkowa i nie można jej dokładnie przewidzieć. Takie liczby mają ogromne zastosowanie we wszelkiego rodzaju symulacjach i grach losowych. Przykładem takiej liczby jest np. wynik rzutu kostką - może wypaść od 1 do 6 oczek, jednakże jeśli kostka nie jest oszukana, to każda z tych liczb jest tak samo prawdopodobna.

Liczby czysto losowe są trudne do uzyskania w komputerze, ponieważ wymagałyby operacji, której wynik nie jest zdefiniowany, a wszelkie działania komputera są precyzyjnie zdefiniowane. 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.

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 większych problemów wygenerować wszystkie dalsze – tej cechy nie posiadają liczby losowe, w przeciwnym razie totolotek straciłby sens.

Na początek:  podrozdziału   strony 

Generatory liczb pseudolosowych

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) % 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 tylko 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ć w tej samej kolejności.

Jeśli współczynniki a, c  i m  są źle dobrane, to okres 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...

Generator LCG
(C)2022 mgr Jerzy Wałaszek
m =
a =
c =
X0 =


...

Jako zadane do oceny należy napisać program, który odczytuje współczynniki m, a, c oraz X0 i wyświetla wszystkie liczby generowane przez generator pseudolosowy o wczytanych parametrach. Projekt ma nazwę P17.

Na początek:  podrozdziału   strony 

Generacja liczb pseudolosowych w C++

Umiejętność projektowania generatora pseudolosowego może być czasem przydatna, jednakże na ogół korzysta się z generatora wbudowanego w język C++.  Tak naprawdę tych generatorów jest kilka, ale my zajmiemy się najprostszym z nich, ponieważ posiada on podobne własności do generatora opisanego w poprzednim podrozdziale. Generator zwraca liczby pseudolosowe z zakresu od 0 do RAND_MAX. Stała RAND_MAX zależy od konkretnej implementacji C++, lecz nie jest mniejsza od 32767, czyli od 215 - 1. Sprawdźmy ten zakres w naszym kompilatorze C++. Uruchom program:
// Liczby pseudolosowe
//--------------------

#include <iostream>
#include <cstdlib>

using namespace std;

int main()
{
    cout << "Zakres liczb pseudolosowych" << endl
         << "---------------------------" << endl << endl
         << 0 << " ... " << RAND_MAX << endl << endl;

    return 0;
}

Generator pseudolosowy w C++ posiada okres dużo większy, niż wynika to z jego zakresu: po prostu zwracane jest 15 najmłodszych bitów wygenerowanej liczby. W ten sposób otrzymuje się lepsze liczby pseudolosowe.

Liczby pseudolosowe otrzymuje się przez wywołanie funkcji rand(). Uruchom poniższy program:

// Liczby pseudolosowe
//--------------------

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

using namespace std;

int main()
{
    int i;

    for(i = 1; i < 10; i++)
        cout << "Liczba pseudolosowa nr " << i << ": "
             << setw(5) << rand() << endl;

    cout << endl;

    return 0;
}

Zapamiętaj trzy pierwsze liczby pseudolosowe i uruchom program ponownie. Otrzymałeś te same liczby, ponieważ przy starcie programu generator jest inicjowany tym samym ziarnem X0. Ziarno pseudolosowe można zmieniać za pomocą funkcji srand(). Uruchom poniższy program:

// Liczby pseudolosowe
//--------------------

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

using namespace std;

int main()
{
    int i,x;

    cout << "Wpisz ziarno pseudolosowe: ";
    cin  >> x;
    cout << endl;

    srand(x);

    for(i = 1; i < 10; i++)
        cout << "Liczba pseudolosowa nr " << i << ": "
             << setw(5) << rand() << endl;
    cout << endl;

    return 0;
}

Uruchom program ponownie i wpisz to samo ziarno. Otrzymasz ten sam ciąg liczb pseudolosowych.

Funkcję srand() należy wywołać przed rozpoczęciem generacji pierwszej liczby pseudolosowej. Z jej argumentu powstaną wszystkie następne liczby pseudolosowe.

Inicjalizacja generatora liczb pseudolosowych

Generator pseudolosowy jest inicjowany za pomocą funkcji:

srand(x0);

Argument x0 zostanie użyty jako ziarno generacji liczb pseudolosowych.  Oby otrzymywać w programach bardziej losowe ciągi liczb pseudolosowych, generator inicjujemy wybraną wartością losową, np. wynikiem funkcji time(), który zmienia się co sekundę. Funkcja time() wymaga dołączenia pliku nagłówkowego ctime. Uruchom poniższy program:

// Liczby pseudolosowe
//--------------------

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

using namespace std;

int main()
{
    int i;

    srand(time(NULL));

    for(i = 1; i < 10; i++)
        cout << "Liczba pseudolosowa nr " << i << ": "
             << setw(5) << rand() << endl;

    cout << endl;
    return 0;
}

Ponieważ czas jest zliczany niezależnie od procesów obliczeniowych komputera, to nie wiadomo, w którym momencie program zostanie uruchomiony i wywołana będzie funkcja time(). Dlatego jej wynik możemy potraktować jako losowy. Wpisanie go do ziarna generatora pseudolosowego spowoduje generowanie innej sekwencji liczb pseudolosowych przy każdym uruchomieniu programu.

Inicjalizację generatora pseudolosowego wykonujemy tylko jeden raz, zawsze na początku programu, przed generacją liczb pseudolosowych. Nie ma sensu umieszczanie wywołania funkcji srand(time(NULL)) wewnątrz pętli tworzącej kolejne liczby pseudolosowe – efekt będzie wręcz odwrotny do zamierzonego:

// Liczby pseudolosowe
//--------------------

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

using namespace std;

int main()
{

    while(true) // Pętla nieskończona
    {
       srand(time(NULL));
       cout << setw(10) << time(NULL)
            << setw(7)  << rand() << endl;
    }

    return 0;
}

Generacja całkowitych liczb pseudolosowych

Dostęp do kolejnych liczb pseudolosowych uzyskujemy za pomocą funkcji rand(), która zwraca wygenerowaną przez generator liczbę pseudolosową z zakresu od 0 do RAND_MAX. Funkcja rand() nie zwraca całej liczby pseudolosowej, tylko jej dolne 15 bitów. Takie rozwiązanie przyjęto dlatego, iż okazuje się, że generatory LCG generują starsze bity z mniejszymi okresami powtarzania niż okresy bitów starszych. Zwracanie młodszych bitów po części niweluje tę wadę.

Wynik funkcji rand() można ograniczyć za pomocą operacji reszty z dzielenia. Np. aby otrzymać liczby pseudolosowe z zakresu od 0 do 9, należy wynik rand() podzielić przez 10 (największa reszta ma zawsze wartość o 1 mniejszą od dzielnika) i zwrócić resztę, co robi operator %. Uruchom poniższy program:

// Liczby pseudolosowe
//--------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int i, g;

    cout << "Podaj górny zakres liczb pseudolosowych: ";
    cin  >> g;
    g++;
    cout << endl;

    srand(time(NULL));

    for(i = 0; i < 3 * g; i++)
        cout << rand() % g << " ";

    cout << endl << endl;

    return 0;
}

Jeśli chcemy otrzymywać liczby z zakresu od A do B, to musimy najpierw wyliczyć ilość liczb pomiędzy A i B:

L = B - A + 1

Następnie generujemy liczby z zakresu od 0 do L:

rand() % (B - A + 1)

I na koniec wygenerowane liczby przesuwamy o A, aby znalazły się we właściwym przedziale:

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

Poniższy program zwraca 20 wyników rzutu kostką (A = 1, B = 6):
// Liczby pseudolosowe
//--------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main()
{
    setlocale(LC_ALL,"");

    int i;

    srand(time(NULL));

    cout << "Wynik 20 rzutów kostką:" << endl
         << "-----------------------" << endl << endl;
    for(i = 0; i < 20; i++)
        cout << 1 + rand() % 6 << " ";

    cout << endl << endl;

    return 0;
}

Na początek:  podrozdziału   strony 

Liczby pseudolosowe bez powtórzeń

Częstym problemem jest wylosowanie określonej ilości liczb pseudolosowych bez powtórzeń, np. generujemy rozdanie kart i nie chcemy, aby gracz otrzymał na rękę powtarzające się karty. Problem ten można rozwiązać na kilka sposobów, a my omówimy dwa z nich.

Pierwszy sposób polega na kolejnym generowaniu liczb pseudolosowych i składowaniu ich w tablicy. Jeśli wygenerowana liczba jest w tablicy, to generację powtarzamy dotąd, aż wygenerujemy liczbę, której w tablicy jeszcze nie ma. Wtedy wpisujemy ją do tablicy i w ten sam sposób generujemy pozostałe liczby.

Poniższy program generuje bez powtórzeń 10 liczb z 20. Program jest napisany ogólnie i poprzez zmianę stałych N, A i B można modyfikować jego działanie.

// Liczby pseudolosowe bez powtórzeń
//----------------------------------

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

using namespace std;

// Definicje stałych

const int N = 10;        // Ilość liczb do generacji
const int A = 1;         // Dolny zakres liczb
const int B = A + N + 9; // Górny zakres liczb

// Funkcja wypełnia tablicę wartością nieużywaną
void ustaw_tab(int t[])
{
    for(int i = 0; i < N; i++) t[i] = B + 1;
}

// Funkcja zwraca true, jeśli liczba jest w tablicy
// Inaczej zwraca false
bool jest_w_tab(int t[], int x)
{
    for(int i = 0; i < N; i++)
        if(t[i] == x) return true;
        else if(t[i] == B + 1) break;
    return false;
}

int main()
{
    int tablica[N];
    int i, liczba;

    srand(time(NULL));

    ustaw_tab(tablica);

    // Losujemy

    for(i = 0; i < N; i++)
    {
        do
            liczba = A + rand() % (B - A + 1);
        while(jest_w_tab(tablica,liczba));
        tablica[i] = liczba;
    }

    // Wyświetlamy wyniki

    for(i = 0; i < N; i++) cout << setw(4) << tablica[i];

    cout << endl << endl;

    return 0;
}

Drugi sposób polega na przygotowaniu tablicy o zadanej liczbie wartości, a następnie pomieszaniu jej i wybraniu z tablicy n pierwszych liczb:

// Liczby pseudolosowe bez powtórzeń
//----------------------------------

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

using namespace std;

// Definicje stałych

const int N = 10; // Ilość liczb do generacji
const int A = 1;  // Dolny zakres liczb
const int B = A + N + 9; // Górny zakres liczb
const int R = B - A + 1; // Rozmiar tablicy liczb

// Funkcja wypełnia tablicę kolejnymi liczbami
// z losowanego zakresu
void ustaw_tab(int t[])
{
    for(int i = 0; i < R; i++) t[i] = A + i;
}

// Funkcja miesza komórki tablicy
void mieszaj(int t[])
{
    int i,j,k,x;
    for(k = 0; k < R * 10; k++)
    {
        i = rand() % R;
        j = rand() % R;
        x = t[i];
        t[i] = t[j];
        t[j] = x;
    }
}

int main()
{
    int tablica[R],i;

    srand(time(NULL));

    ustaw_tab(tablica);

    mieszaj(tablica);

    // Wyświetlamy wynik

    for(i = 0; i < N; i++) cout << setw(4) << tablica[i];

    cout << endl << endl;

    return 0;
}
Na początek:  podrozdziału   strony 

Przykładowe zastosowania liczb pseudolosowych

// Symulator kostki do gry
//------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <conio.h>

using namespace std;
// -----
//|*   *|
//|* * *|
//|*   *|
// -----
void kostka(int n)
{
    cout << " -----" << endl;
    switch(n)
    {
        case 1: cout << "|     |" << endl
                     << "|  *  |" << endl
                     << "|     |" << endl;
                break;
        case 2: cout << "|    *|" << endl
                     << "|     |" << endl
                     << "|*    |" << endl;
                break;
        case 3: cout << "|    *|" << endl
                     << "|  *  |" << endl
                     << "|*    |" << endl;
                break;
        case 4: cout << "|*   *|" << endl
                     << "|     |" << endl
                     << "|*   *|" << endl;
                break;
        case 5: cout << "|*   *|" << endl
                     << "|  *  |" << endl
                     << "|*   *|" << endl;
                break;
        case 6: cout << "|*   *|" << endl
                     << "|*   *|" << endl
                     << "|*   *|" << endl;
                break;
    }
    cout << " -----" << endl;
}
int main()
{
    setlocale(LC_ALL,"");

    srand(time(NULL));


    while(true)
    {
        kostka(1 + rand() % 6);
        cout << endl << "Naciśnij dowolny klawisz..." << endl << endl;
        getch(); // Zwraca kod klawisza
    }

    return 0;
}
// Symulator toto-lotka
//---------------------

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

using namespace std;

int main()
{
    setlocale(LC_ALL,"");
    srand(time(NULL));

    // Inicjujemy zmienne

    int bile[49],trafienia[7],i;

    for(i = 0; i < 49; i++) bile[i] = i + 1;
    for(i = 0; i < 7; i++) trafienia[i] = 0;

    // Rozpoczynamy symulację

    cout << "Symulator TOTO-LOTKA" << endl
         << "--------------------" << endl << endl;
    cout << "Wprowadź swoje 6 liczb: ";
    int kupon[6];
    for(i = 0; i < 6; i++) cin >> kupon[i];
    cout << "Ile losowań?: ";
    int ilelos;
    cin >> ilelos;
    cout << endl;

    int j,k,los,x;
    for(los = 1; los <= ilelos; los++)
    {
        cout << "Losowanie " << setw(5) << los << " : ";

        // Mieszamy bile
        for(k = 0; k < 1000; k++)
        {
            i = rand() % 49;
            j = rand() % 49;
            x = bile[i];
            bile[i] = bile[j];
            bile[j] = x;
        }

        // Pierwsze 6 bil jest wynikiem losowania
        for(i = 0; i < 6; i++) cout << setw(3) << bile[i];
        cout << " : ";
        int traf = 0;
        for(i = 0; i < 6; i++)
        {
            for(j = 0; j < 6; j++)
                if(bile[j] == kupon[i])
                {
                    traf++;
                    cout << setw(3) << kupon[i];
                }
        }
        trafienia[traf] ++;
        cout << endl;
    }

    cout << endl << "-------------------------------------" << endl << endl
         << "Trafienia:" << endl;
    for(i = 3; i < 7; i++)
        cout << i << " : " << trafienia[i] << endl;
    cout << endl << endl;

    return 0;
}
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2022 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.