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

©2024 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, hashing) 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:   ; tasowanie wykonujemy w pętli
     wykonuj kroki K02…K07
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

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 <ctime>

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
Python (dodatek)
# Pseudolosowe tasowanie
# Data:   17.02.2024
# (C)2020 mgr Jerzy Wałaszek
# ---------------------------

import random

z = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(10):
    print(z[i], end=" ")
print()
for i in range(30):
    i1 = random.randrange(0, 10)
    i2 = random.randrange(0, 10)
    z[i1], z[i2] = z[i2], z[i1]
for i in range(10):
    print(z[i], end=" ")
print()
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(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 kroki K02…K06
K02:   xa + losowa(b - a + 1) ; losujemy liczbę pseudolosową
K03:   Dla j = 0, 1, …, i - 1:   ; sprawdzamy, czy wylosowana
       wykonuj krok K04          ; liczba jest w T
K04:     Jeśli T[j] = x,         ; jeśli tak, powtarzamy losowanie
         to idź do kroku K02
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 <ctime>

using namespace std;

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

  srand(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
Python (dodatek)
# Losowanie bez powtórzeń
# Data:   17.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

import random

arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
n = int(arr[2])
if n <= b - a + 1:
    T = []
    for i in range(n):
        while True:
            test = True
            x = random.randrange(a, b + 1)
            for j in range(i):
                if T[j] == x:
                    test = False
                    break
            if test: break
        T.append(x)
        print(x, end=" ")
else:
    print("n jest za duże!")
print()
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
©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: i-lo@eduinf.waw.pl

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

Informacje dodatkowe.