Programowanie w języku Delphi » Gotowce

Losowanie bez powtórzeń

  • 2008-12-21 22:49
  • 5 komentarzy
  • 1862 odsłony
  • Oceń ten tekst jako pierwszy

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.


5 komentarzy

Henryk555 2009-07-23 12:33

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

qq 2008-12-12 22:01

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 -.-

ŁF 2008-12-11 14:45

bardziej profesjonalne (i bardziej hc ;]) rozwiązania są tutaj: http://forum.4programmers.net/viewtopic.php?p=498550

Intelli 2008-12-08 11:40

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.

SebaZ 2008-12-07 21:35

a po co 2 tablice? Dziwna to metoda.