Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
SPIS TREŚCI |
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.
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
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
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
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...
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.
// 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.
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
// 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; } |
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; } |
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; } |
// 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; } |
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.