Wpisany przez Andrzej Borucki,
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:
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
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:
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Andrzej Borucki | C# | .cs | .cs | ***** / 14 | |
dawidex44 | C/C++ | C++ | .cpp | .cpp | ***** / 5 |
Tomasz Lubiński | JavaScript | .js | .js | ***** / 14 |
Poprawiony: 28 września 2012 08:26
Komentarze
-11
#
Magda
2011-12-12 14:43
A w Mathematice jak to będzie wyglądać?
Odpowiedz | Odpowiedz z cytatem | Cytować
+1
#
siusiu
2016-08-05 09:46
gdzie kod w perl'u?
Odpowiedz | Odpowiedz z cytatem | Cytować
+1
#
polish
2018-01-14 21:56
a da sie cos takiego zrobić prościej? np exel?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz