Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2011 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