Generowanie liczb pseudolosowych


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Mieszanie pseudolosowe
Losowanie bez powtórzeń

 

Problem

Dany, skończony zbiór liczb całkowitych pomieszać pseudolosowo.

 

 

Mieszanie pseudolosowe

Zadanie mieszania, tasowania (ang. shuffle) zawartości tablicy sprowadza się do wykonywania w pętli zamiany miejscami dwóch elementów tablicy o wylosowanych indeksach. Pętla musi być wykonana tyle razy, aby tasowanie objęło wszystkie elementy – w praktyce wystarcza ilość wykonań równa 3n, gdzie n jest ilością elementów.

 

Algorytm mieszania pseudolosowego

Wejście
n     liczba elementów w tablicy, n N
Z  – tablica elementów, indeksy rozpoczynają się od 0
Wyjście:

Tablica Z z potasowaną zawartością

Zmienne pomocnicze
i  –  licznik obiegów pętli. i N
x   przechowuje element tablicy Z przy zamianie zawartości. Typ ten sam, co elementy tablicy Z.
losowa(x)  – funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x - 1
Lista kroków:
K01: Dla i = 1,2,...,3n: wykonuj K02...K07 ; tasowanie wykonujemy w pętli
K02:     i1 ← losowa(n) ; losujemy pierwszy indeks
K03:     i2 ← losowa(n) ; losujemy drugi indeks
K04:     xZ[i1] ; zamieniamy miejscami Z[i1] i Z[i2]
K05:     Z[i1] ← Z[i2]  
K06:     Z[i2] ← x  
K07: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tasuje tablicę 10 elementów całkowitych o kolejnych wartościach od 0 do 9.  Tablica jest najpierw wyświetlana przed tasowaniem, a następnie po tasowaniu.

 

Lazarus
// Pseudolosowe tasowanie
// Data:   20.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

program prg;

var Z : array[0..9] of integer = (0,1,2,3,4,5,6,7,8,9);
    i1,i2,i,x : integer;

begin
  randomize;
  for i := 0 to 9 do write(Z[i],' ');
  writeln;
  for i := 1 to 30 do
  begin
    i1 := random(10);
    i2 := random(10);
    x  := Z[i1]; Z[i1] := Z[i2]; Z[i2] := x;
  end;
  for i := 0 to 9 do write(Z[i],' ');
  writeln;
end.
Code::Blocks
// Pseudolosowe tasowanie
// Data:   20.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

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

using namespace std;

int main()
{
  int Z[] = {0,1,2,3,4,5,6,7,8,9};
  int i1,i2,i,x;

  srand((unsigned) time(NULL));
  for(i = 0; i < 10; i++) cout << Z[i] << " ";
  cout << endl;
  for(i = 1; i <= 30; i++)
  {
    i1 = rand() % 10;
    i2 = rand() % 10;
    x  = Z[i1]; Z[i1] = Z[i2]; Z[i2] = x;
  }
  for(i = 0; i < 10; i++) cout << Z[i] << " ";
  cout << endl;
  return 0;
}
Free Basic
' Pseudolosowe tasowanie
' Data:   20.04.2008
' (C)2012 mgr Jerzy Wałaszek
'---------------------------

Dim Z(9) As Integer => {0,1,2,3,4,5,6,7,8,9}
Dim As Integer i1,i2,i

Randomize Timer
For i = 0 To 9: Print Z(i);: Next
Print
For i = 1 To 30
  i1 = Int(Rnd * 10)
  i2 = Int(Rnd * 10)
  Swap Z(i1),Z(i2)
Next
For i = 0 To 9: Print Z(i);: Next
Print
End
Wynik
0 1 2 3 4 5 6 7 8 9
7 2 3 1 6 4 0 9 5 8

 

Pseudolosowe tasowanie
(C)2012 mgr Jerzy Wałaszek


...

 

Problem

Wylosować z przedziału całkowitego <a,b> n liczb pseudolosowych bez powtórzeń.

 

 

Losowanie bez powtórzeń

Zadanie losowania bez powtórzeń można rozwiązać na kilka różnych sposobów. Jeśli przedział <a,b> jest mały (np. zawiera 80 kolejnych liczb Multi-Lotka), to możemy go odwzorować w tablicy, następnie zawartość tej tablicy potasować poprzednio podanym algorytmem i jako wynik zwrócić pierwsze n elementów. Tasowanie nie dubluje elementów tablicy, zatem otrzymamy n liczb bez powtórzeń. Taki algorytm posiada klasę złożoności obliczeniowej O(n).

Jeśli przedział <a,b> jest bardzo duży, a n stosunkowo małe, to postępujemy w sposób następujący. Przygotowujemy pustą tablicę o n elementach. Losujemy liczbę pseudolosową. Jeśli wylosowana liczba jest już w tablicy, to losujemy ponownie dotąd, aż wylosowanej liczby nie będzie w tablicy. Liczbę dopisujemy do tablicy. Jeśli tablica jest zapełniona, kończymy. W przeciwnym razie powtarzamy losowanie. Algorytm w takiej postaci posiada optymistyczną klasę złożoności obliczeniowej O(n2).

 

Algorytm losowania bez powtórzeń

Wejście
n     liczba określająca, ile liczb pseudolosowych bez powtórzeń należy wylosować, n N
a,b  – liczby określające całkowity przedział losowania, b - an, a,b C
Wyjście:

n różnych od siebie liczb pseudolosowych z przedziału <a,b>

Zmienne pomocnicze
T  –  tablica przechowująca wylosowane liczby pseudolosowe. Indeksy od 0 do n-1.
i  –  licznik wylosowanych liczb pseudolosowych. i N
j   wykorzystywane do przeszukiwania tablicy T.  j N
x  – wylosowana liczba pseudolosowa
losowa(x)  – funkcja zwracająca liczbę pseudolosową z zakresu od 0 do x - 1
Lista kroków:
K01: Dla i = 0,1,...,n-1 wykonuj K02...K06  
K02:     xa + losowa(b - a + 1) ; losujemy liczbę pseudolosową
K03:     Dla j = 0,1,...,i - 1 wykonuj K04 ; sprawdzamy, czy wylosowana liczba jest w T
K04:         Jeśli T[j] = x, to idź do K02 ; jeśli tak, powtarzamy losowanie
K05:     T[i] ← x ; jeśli nie, zapamiętujemy w T wylosowaną liczbę
K06:     Wyprowadź x ; wyprowadzamy liczbę na wyjście
K07: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

W pierwszym wierszu program odczytuje trzy liczby: a,b – krańce przedziału, n – ilość liczb pseudolosowych do wylosowania. Jeśli długość przedziału <a,b> pozwala na wygenerowanie zadanej ilości różnych liczb pseudolosowych, to program je generuje i wyświetla w następnym wierszu. W przeciwnym razie wypisuje odpowiedni komunikat.

 

Lazarus
// Losowanie bez powtórzeń
// Data:   20.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

program prg;

type Tintarray = array of integer;

var a,b,i,j,n,x : integer;
    T    : Tintarray;
    test : boolean;
begin
  randomize;
  readln(a,b,n);
  if n <= b - a + 1 then
  begin
    setlength(T,n);
    for i := 0 to n - 1 do
    begin
      repeat
        test := true;
        x := a + random(b-a+1);
        for j := 0 to i - 1 do
          if T[j] = x then
          begin
            test := false;
            break;
          end;
      until test;
      T[i] := x;
      write(x,' ');
    end;
  end
  else
    writeln('n jest za duze!');
  writeln;
end.
Code::Blocks
// Losowanie bez powtórzeń
// Data:   20.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

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

using namespace std;

int main()
{
  int a,b,i,j,n,x, * T;
  bool test;

  srand((unsigned)time(NULL));
  cin >> a >> b >> n;
  if(n <= b - a + 1)
  {
    T = new int[n];
    for(i = 0; i < n; i++)
    {
      do
      {
        test = true;
        x = a + rand()%(b-a+1);
        for(j = 0; j < i; j++)
          if(T[j] == x)
          {
            test = false;
            break;
          }
      } while(!test);
      T[i] = x;
      cout << x << " ";
    }
  }
  else
    cout << "n jest za duze!\n";
  cout << endl;
  delete [] T;
  return 0;
}
Free Basic
' Losowanie bez powtórzeń
' Data:   20.04.2008
' (C)2012 mgr Jerzy Wałaszek
'---------------------------

Dim As Integer a,b,i,j,n,x,test

Randomize Timer
Input a,b,n
If n <= b - a + 1 Then
  Dim T(n-1) As Integer
  For i = 0 To n - 1
    Do
      test = 1
      x = a + Int(Rnd*(b-a+1))
      For j = 0 To i - 1
        If T(j) = x Then
          test = 0
          Exit For
        End If
      Next
    Loop Until test = 1
    T(i) = x
    Print x;
  Next
Else
  Print "n jest za duze!"
End If
Print
End
Wynik
1 80 20
39 79 12 38 80 3 11 33 9 76 19 21 8 14 37 29 24 71 50 1

 

Losowanie bez powtórzeń
(C)2012 mgr Jerzy Wałaszek

a = , b = , n =


...

 



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.