Wpisany przez Andrzej Borucki
czwartek, 08 grudnia 2011 15:28
Załóżmy, że mamy wylosować k liczb z n (oczywiście k ≤ n).
Aby uniknąć powtórzeń bierzemy tablicę numbers wielkości n i wypełniamy ją kolejnymi liczbami.
Losujemy indeks r pomiędzy 0 a n-1, liczba spod tego indeksu jest naszą wylosowaną.
Teraz przenosimy ostatnią liczbę w tablicy do pozycji r: numbers[r] = numbers[n - 1] i zmniejszamy n o jeden.
Algorytm ten można przedstawić następującym schematem blokowym:
Przykład:
Załóżmy, że chcemy wylosować 3 z 5 liczb (k = 3, n = 5).
Tworzymy pięcio-elementową tablicę i wypełniamy ją liczbami numbers = [1, 2, 3, 4, 5]
Losujemy liczbę pomiędzy 0 a 4. Wylosowaliśmy indeks 2. Pod tym indeksem znajduje się liczba 3 (indeksy w tablicy liczymy od 0). Czyli naszą wylosowaną liczbą jest 3. Przenosimy ostatnią pozycję z tablicy numbers w wylosowany indeks: numbers = [1, 2, 5, 4, 5].
Zmniejszamy o jeden zakres losowania. Zatem teraz tablica, z której losujemy wygląda następująco: numbers = [1, 2, 5, 4].
Losujemy liczbę pomiędzy 0 a 3. Wylosowaliśmy indeks 0. Pod tym indeksem znajduje się liczba 1. Czyli naszą wylosowaną liczbą jest 1. Przenosimy ostatnią pozycję z tablicy numbers w wylosowany indeks: numbers = [4, 2, 5, 4].
Zmniejszamy o jeden zakres losowania. Zatem teraz tablica, z której losujemy wygląda następująco: numbers = [4, 2, 5].
Losujemy liczbę pomiędzy 0 a 2. Wylosowaliśmy indeks 2. Pod tym indeksem znajduje się liczba 5. Czyli naszą wylosowaną liczbą jest 5. Wylosowaliśmy zatem liczby: 3, 1 oraz 5.
Zwróć uwagę, że wylosowane liczby nie powtarzają się mimo tego, że podczas naszego procesu dwa razy wylosowaliśmy indeks 2
Przykład w JavaScript:
Aby uniknąć powtórzeń bierzemy tablicę numbers wielkości n i wypełniamy ją kolejnymi liczbami.
Losujemy indeks r pomiędzy 0 a n-1, liczba spod tego indeksu jest naszą wylosowaną.
Teraz przenosimy ostatnią liczbę w tablicy do pozycji r: numbers[r] = numbers[n - 1] i zmniejszamy n o jeden.
Algorytm ten można przedstawić następującym schematem blokowym:
Przykład:
Załóżmy, że chcemy wylosować 3 z 5 liczb (k = 3, n = 5).
Tworzymy pięcio-elementową tablicę i wypełniamy ją liczbami numbers = [1, 2, 3, 4, 5]
Losujemy liczbę pomiędzy 0 a 4. Wylosowaliśmy indeks 2. Pod tym indeksem znajduje się liczba 3 (indeksy w tablicy liczymy od 0). Czyli naszą wylosowaną liczbą jest 3. Przenosimy ostatnią pozycję z tablicy numbers w wylosowany indeks: numbers = [1, 2, 5, 4, 5].
Zmniejszamy o jeden zakres losowania. Zatem teraz tablica, z której losujemy wygląda następująco: numbers = [1, 2, 5, 4].
Losujemy liczbę pomiędzy 0 a 3. Wylosowaliśmy indeks 0. Pod tym indeksem znajduje się liczba 1. Czyli naszą wylosowaną liczbą jest 1. Przenosimy ostatnią pozycję z tablicy numbers w wylosowany indeks: numbers = [4, 2, 5, 4].
Zmniejszamy o jeden zakres losowania. Zatem teraz tablica, z której losujemy wygląda następująco: numbers = [4, 2, 5].
Losujemy liczbę pomiędzy 0 a 2. Wylosowaliśmy indeks 2. Pod tym indeksem znajduje się liczba 5. Czyli naszą wylosowaną liczbą jest 5. Wylosowaliśmy zatem liczby: 3, 1 oraz 5.
Zwróć uwagę, że wylosowane liczby nie powtarzają się mimo tego, że podczas naszego procesu dwa razy wylosowaliśmy indeks 2
Przykład w JavaScript:
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Andrzej Borucki | C# |  | |
 / 0 | |
| Tomasz Lubiński | Java Script |  | |
 / 1 |
Poprawiony: czwartek, 08 grudnia 2011 15:31
Komentarze