Losowanie bez powtórzeń
Yures
Losowanie liczb w tablicy - Kilka prostych poleceń
W tym artykule postaram się przedstawić oraz w miarę możliwości wyjaśnić działanie poniższego kodu.
Zacznijmy od określenia bloku VAR:
var
Tab :Array [1..10] of Integer;
Pom :Array [1..22] of Byte;
Buff :Integer;
W tym miejscu warto objaśnić znaczenie zmiennych :
- Tablica Tab - Określa ilość liczb które chcemy wylosować.
- Tablica Pom - Będzie przyjmowała dwa stany 0 i 1 gdzie 0 będzie znaczyło że liczby jeszcze nie wylosowaliśmy, a 1 znaczy że liczbę już wcześniej wylosowaliśmy.
- Zmienna Buff - Będzie się tam kryła wylosowana liczba.
A teraz przejdźmy do kodu:
Na samym początku musimy wyzerować tablice pom:
For i:=1 to 22 do
begin
Pom[i]:=0 ;
end;
Następnie możemy już losować nasze liczby :
Randomize;
For i:=1 to 10 do
begin
Repeat Buff:=Random(22)+1; until (pom[Buff]=0) ;
Tab[i]:=Buff;
pom[buff]:=1 ;
end;
Zakres tablicy Pom musi odpowiadać ilości liczb które chcemy losować. Czyli jeżeli chcemy losować spośród 100 liczb tablica ta musi być w zakresie [1..100]
A teraz kilka słów objaśnienia:
Określamy ile liczb wylosujemy, służy do tego pętla for to do. Następnie losowana jest liczba która zostaje zapisana do 'Tymczasowej' zmiennej buff, liczba ta ma swoje miejsce w tablicy pom. Jeśli pom=0 wtedy przypisywana jest liczba w buff do tablicy Tab a tablicy pom o indeksie buff zostaje nadana wartość 1 - co oznacza ze taka liczba została wylosowana. Jeśli na samym początku pom o indeksie buff wynosi 1 wtedy następuje ponowne losowanie i tak do skutku.
W całości nasz program powinien wygladac tak:
program foo;
{$APPTYPE CONSOLE}
uses
SysUtils;
var
Tab :Array [1..10] of Integer;
Pom :Array [1..22] of Integer;
Buff :Integer;
begin
For i:=1 to 22 do
begin
Pom[i]:=0 ;
end;
Randomize;
For i:=1 to 10 do
begin
Repeat Buff:=Random(22)+1; until (pom[Buff]=0) ;
Tab[i]:=Buff;
pom[buff]:=1 ;
end;
end.
A ja bym sobie wziął np parę kostek do gry i bym sobie porzucał jak się powtórzy to do kosza za karę i juz ...:) he he
Tragiczny artykuł. Żenada. Po co w ogóle pisać o czymś, o czym nie ma się zielonego pojęcia ?
Losowanie bez powtórzeń robi się kompletnie inaczej i wcale do tego nie trzeba tablicy dynamicznej (tzn. można, ale tablica statyczna też jest OK).
Mianowicie, należy za każdym razem zamieniać element już wylosowany z OSTATNIM elementem. Czyli np. jak była tablicy
1 2 3 4 5 6 i wylosowaliśmy trójkę to zamieniamy 1 2 6 4 5 3 i zmniejszamy liczbę n o 1. W ten sposób uzyskamy złożoność liniową, a nie nieskończoną w pesymistycznym przypadku.
Artykuł do poprawienia -.-
bardziej profesjonalne (i bardziej hc ;]) rozwiązania są tutaj: http://4programmers.net/Forum/498550
To jest raczej przykład, jak NIE NALEŻY robić losowania bez powtórzeń. Po pierwsze pesymistyczna złożoność algorytmu dąży do nieskończoności. Kolejne losowania trwają coraz dłużej, a w najgorszym przypadku algorytm wpadnie w nieskończoną pętlę.
Losowanie bez powtórzeń wykonuje się na tablicy dynamicznej, która jest skracana po każdym wylosowaniu.
a po co 2 tablice? Dziwna to metoda.