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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Generowanie liczb pseudolosowych

SPIS TREŚCI
Podrozdziały

Problem

Dany, skończony zbiór liczb całkowitych należy 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, nN.
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. iN.
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 kroki K02...K07
tasowanie wykonujemy w pętli
K02:     i 1 ← losowa ( n  ) losujemy pierwszy indeks
K03:     i 2 ← losowa ( n  ) losujemy drugi indeks
K04:     x  ← Z [ i 1 ] zamieniamy miejscami Z [ i 1 ] i Z [ i 2 ]
K05:     Z [ i 1 ] ← Z [ i 2 ]  
K06:     Z [ i 2 ] ← x  
K07: Zakończ  

Przykładowe programy

Uwaga:

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.
Pascal
// Pseudolosowe tasowanie
// Data:   20.04.2008
// (C)2020 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.
C++
// Pseudolosowe tasowanie
// Data:   20.04.2008
// (C)2020 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;
}
Basic
' Pseudolosowe tasowanie
' Data:   20.04.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek


...

Na początek:  podrozdziału   strony 

Problem

Z przedziału całkowitego <a, b> należy wylosować bez powtórzeń n  liczb pseudolosowych.

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 ( n 2 ).

Algorytm losowania bez powtórzeń

Wejście:

n  –   liczba określająca, ile liczb pseudolosowych bez powtórzeń należy wylosować, nN.
a, b  – liczby określające całkowity przedział losowania, b  - a  ≥ n, a, bC.

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. iN.
j  – wykorzystywane do przeszukiwania tablicy T.  jN.
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 kroki K02...K06
 
K02:     x  ← a  + losowa ( b  - a  + 1 ) losujemy liczbę pseudolosową
K03:     Dla j  = 0, 1, ..., i  - 1:
    wykonuj krok K04
sprawdzamy, czy wylosowana liczba jest w T
K04:         Jeśli T [ j ] = x,
        to idź do kroku 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  

Przykładowe programy

Uwaga:

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.
Pascal
// Losowanie bez powtórzeń
// Data:   20.04.2008
// (C)2020 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.
C++
// Losowanie bez powtórzeń
// Data:   20.04.2008
// (C)2020 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 << " ";
    }
    delete [ ] T;
  }
  else
    cout << "n jest za duze!\n";
  cout << endl;
  return 0;
}
Basic
' Losowanie bez powtórzeń
' Data:   20.04.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek
a =
b =
n =

...

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
©2020 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.