Autor artykułu: mgr Jerzy Wałaszek, wersja1.0
©2013 mgr
Jerzy Wałaszek
I LO w Tarnowie
|
|
Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2013 mgr
Jerzy Wałaszek
|
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.
| n | – | liczba elementów w tablicy, n
N |
| Z[ ] | – | tablica elementów, indeksy rozpoczynają się od 0 |
Tablica Z[ ] z potasowaną zawartością
| 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 |
| 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: | x ← Z[i1] | ; zamieniamy miejscami Z[i1] i Z[i2] |
| K05: | Z[i1] ← Z[i2] | |
| K06: | Z[i2] ← x | |
| K07: | Zakończ |
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).
| 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 - a
≥
n, a,b
C |
n różnych od siebie liczb pseudolosowych z przedziału <a,b>
| 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 |
| K01: | Dla i = 0,1,...,n-1 wykonuj K02...K06 | |
| K02: | x ← a + 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 |
 | I Liceum Ogólnokształcące |
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe