| Author |
Message
|
Guest
Poziom 10
|
 #1
 20 Sep 2004 19:39 [Pascal] Losowanie 4 liczb bez powtórzeń. |
|
|
|
hejka! mam troszke czasu i postanowilam napisac fajny programik , ale do jego realizacji jest mi potrzebny algorytm losowania 4 liczb, tak aby zadna z nich sie nie powtorzyla. raczej to nie jest trudne ale cos mi nie wychodzi:/,bede wdzieczna za pomoc.pa
Zamykam. - arnoldziq
|
|
| Back to top |
|
 |
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#2
20 Sep 2004 20:44 losowanie 4 liczb bez powtorzen |
|
|
|
t[1..N+1]
i=1
while (i<N+1)
. k=losowa()
. t[i]=k
. j=1
. while (t[j]<>k)
. . j=j+1
. if (j>=i)
. . i=i+1
jeśli ma się pecha to ten programik nigdy się nie zakończy
|
|
| Back to top |
|
|
Google
|
| #
20 Sep 2004 20:44 |
|
|
|
|
|
| Back to top |
|
|
Guest
Poziom 10
|
#3
21 Sep 2004 12:17 Re: losowanie 4 liczb bez powtorzen |
|
|
|
1.
Robisz tablice typu booleanz wszystkimi możliwymi do wylosowania elementami (tb:array[1..N] of boolean) i na początek wpisujesz do niej "false" (for i:=1 to N do tb[i]:=False)
Nastepnie losujesz liczbę i sprawdzasz jaka wartość tablicy jej odpowiada:
k:=random(N+1);
if tb[k] then //losujesz jeszcze raz
else .... tb[k]:=True .... // dalej robisz co Ci się podoba, masz pewność, że liczby wcześniej nie losowano
2.
Robisz tablicę czteroelementową i na początek wypełniasz ją jedną wartością, z poza przedziału losowań (np jeśli losujesz od 1 w górę - for i:=1 to 4 do tb[i]:=0; )
Losujesz liczbę (k:=random(N+1))
Sprawdzasz wszystkie elementy tablicy, czy któryś ma wartość k :
pmc:=false;
for i:=1 to 4 do if tb[i]=k then pmc:=True;
if pmc then //losujesz ponownie
else //robisz co Ci się podoba
Można to jeszcze zoptymalizować - liczyć losowania (oczywiście te nie powtórzone) i sprawdzać tylko tyle elementów tablicy, ile losowań.
|
|
| Back to top |
|
|
Google
|
| #
21 Sep 2004 12:17 |
|
|
|
|
|
| Back to top |
|
|
BoskiDialer
Poziom 22
Joined: 28 Nov 2003
Posts: 1533
Location: Żory
|
#4
21 Sep 2004 14:08 losowanie 4 liczb bez powtorzen |
|
|
|
Witam. właśnie na potrzeby tego tematu napisałem w Delphi takie coś:
| Code: |
const Zakres = 500;
const Ilosc = 4;
type PaczkaLiczb = array[0..Ilosc-1] of word;
function LosujLiczby:PaczkaLiczb;
var test:boolean;
wylosowane:array[0..Zakres-1] of boolean;
i,o,p:word;
begin
{oproznianie tablicy}
for i := 0 to Zakres-1 do
wylosowane[i] := false;
o := 0; {wyzerowanie liczby wylosowaych liczb}
repeat
p := random(zakres); {losuj}
if wylosowane[p] = false then
inc(o); {jesli takiej liczby niebylo to zwieksz licznik}
wylosowane[p] := true; {oznacz jako wylosowana}
until o>=Ilosc; {zakoncz petle jesli znaleziono dosc liczb}
o := 0;
{przepisz do wyniku losowe liczby}
For i := 0 to Zakres-1 do
if wylosowane[i] then
begin
result[o] := i;
inc (o);
end;
{tutaj liczby sa posortowane rosnaco}
{trzeba je pomieszac}
for i := 0 to Ilosc-2 do
for o := i+1 to Ilosc-1 do
if random(2)=0 then
begin
p := result[i];
result[i] := result[o];
result[o] := p;
end;
end;
|
i całość działa, całość używam tak:
| Code: |
procedure TForm1.Button1Click(Sender: TObject);
var DaneLosowe:PaczkaLiczb;i:word;
begin
randomize;
DaneLosowe := LosujLiczby;
for i:=0 to Ilosc-1 do
Memo1.Lines.add(inttostr( DaneLosowe[i] ));
end;
|
Jedyny kruczek to To że funkcja Random (delphi/pascal) niejest dokońca losowa :) opiera sie tylko o zegarek i programowy licznik więc łatwo przewidzieć wynik. podczas testów bez stosowania randomize za każdym razem miałem taki sam wynik.
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#5
21 Sep 2004 18:21 losowanie 4 liczb bez powtorzen |
|
|
|
Panowie, panowie!!
jak działają wasze pomysły kiedy chcę wylosować cztery liczby longint? albo co też czasem bywa potrzebują liczb rzeczywistych? jakieś pomysły ;) ?
no jak to zrobić? , czy któryś z was potrafi to uruchomić na swoim komputerze?
przepraczam, ale moja propozycja jest najprostrza, najlepsza i jedyna!!
-poprawka do programiku, tablica t wystarczy że ma N elementów.
Czy ktoś się nie zgodzi?
PS
a jeśli już wytaczać armaty, to dla wielkiego N można by pomyśleć o drzewach binarnych. Czemu?
|
|
| Back to top |
|
|
Google
|
| #
21 Sep 2004 18:21 |
|
|
|
|
|
| Back to top |
|
|
Guest
Poziom 10
|
#6
22 Sep 2004 09:42 Re: losowanie 4 liczb bez powtorzen |
|
|
|
| xitami wrote: |
Panowie, panowie!!
jak działają wasze pomysły kiedy chcę wylosować cztery liczby longint? albo co też czasem bywa potrzebują liczb rzeczywistych? jakieś pomysły ;) ?
|
Tak, do losowania z dużego zbioru użyłbym pomysłu który przedstawiłem w punkcie 2 (zadeklarowanie czteroelementowej tablicy dowolnego typu nie uważam za strzelanie z armaty).
Twoja metoda może jest najlepsza(co za skromność), ale (chyba mam ostatnio złe dni) za cho....re nie "kumam" o co chodzi :cry:
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#7
22 Sep 2004 12:17 losowanie 4 liczb bez powtorzen |
|
|
|
tJanusz: twoje rozwiązanie nr 2 po optymalizacji będzie wyglądało tak jak moje ;)
a co do skromności, chodziło mi tylko o to, że chyba nieda się tego zrobić prościej.
*piersza pętla: while i<=N. no bo i musi przebiec wszystkie wartości 1..N
*k pomocnicza zmienna
*t[i]=k, do pierwszego wolniego miejsca w tablicy zawsze! wstawiam wylosowaną liczbę
*j=1, while t[j]<>k, "j" szuka właśnie wylosowanej liczby, napewno ją znajdzie, co upraszcza warunki, nie muszę stosować "magicznych" liczb, nie muszę sprawdzać czy j nie poleciało za daleko, bardzo urzyteczny sposób z tzw. "wartownikiem"
*if j>=i, jeżeli "j" znalazło ją na ostatniej pozycji to i=i+1, w innym wypadku i pozostaje bez zmian, czyli musimy powtórzyć losowanie.
|
|
| Back to top |
|
|
BoskiDialer
Poziom 22
Joined: 28 Nov 2003
Posts: 1533
Location: Żory
|
#8
22 Sep 2004 19:43 Re: losowanie 4 liczb bez powtorzen |
|
|
|
| xitami wrote: |
| *if j>=i, jeżeli "j" znalazło ją na ostatniej pozycji to i=i+1, w innym wypadku i pozostaje bez zmian, czyli musimy powtórzyć losowanie. |
to jest jeden z najciekawszych problemów. właściwie patrząc liczby bendą losowe i bez powtóżeń, ale jeśli zostanie wylosowana liczba która już się powtóżyła to będzie ona inkrementowana do skutku aż wejdzie na pole puste, statystycznie biorąc jeśli np została wylosowana liczba 39 i została ona zapisana to wszystko jest w pożądku, ale wylosowanie kolejnej liczby 39 albo 40 da taki sam wynik 40 co ze statystycznego punktu widzenia da większe prawdopodobieństwo liczby 40 niż np 41 (40 będze miało prawdopodobieństwo 200% liczby 41 gdyż występuje pod dwoma pozycjami w tablicy) a więc liczby takie są opisane pewną małą regułą, przezco liczby niestają się w pełni losowe (pseudolosowe), podobna sytuacja będzie jeśli zostaną wylosowane np liczby 20,21 i 22, wystąpienie liczby 23 to 400% liczby np 30 ponieważ wylosowanie liczb 20,21,22 i 23 daje tą samą liczbe 23.
Co do losowania liczb rzeczywistych, można wylosować 8 bajtów, i zamapować (anonimowa unia) na typ rzeczywisty, oczywiście nieobejdzie sie bez możliwości wystąpienia +nieskończoność oraz -nieskończoność, gdyż typ rzeczywisty i takie stany przyjmuje.
inna metoda to wylosować jakąś dużą liczbe całkowitą, i podzielić ją przez np 0,0000001 co da liczbe rzeczywistą.
|
|
| Back to top |
|
|
Google
|
| #
22 Sep 2004 19:43 |
|
|
|
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#9
22 Sep 2004 22:10 losowanie 4 liczb bez powtorzen |
|
|
|
1. "i" jest licznikiem, nie losowaną liczbą (jest nią "k") z którą po losowaniu nic się nie dzieje.
można by w wypadku ponownego wylosowania wartości którą już mamy w tablicy kombinować ze sprawdzaniem kolejnej, czyli k+1, ale tu znowu trzeba sprawdzać czy już takiej nie było, jeśli była to k+2 i tak do skutku, kłopotliwe, trzeba jeszcze sprawdzać czy nie przekraczamy założonego zakresu, przy liczbach rzeczywistych jaka jest kolejna liczba? 0,1? a może 0,00000000001? żadna taka, tu ciekawostka, wiesz że np. 0,1 NIE DA SIĘ zapisać w komputerze? ;-) tak jest, no chyba że używamy liczb BCD, 0,1 jest liczbą okresową!
a statystycznie takie losowanie psuło by nam jakość losowanych liczb, ta metoda "lubiła by" ciągi.
2. a czemu kombinować? algorytm wymaga tylko żeby wartości w tablicy dawały się testować na równość, mogą być dowolnego typu np. string.
|
|
| Back to top |
|
|
BoskiDialer
Poziom 22
Joined: 28 Nov 2003
Posts: 1533
Location: Żory
|
#10
23 Sep 2004 13:50 losowanie 4 liczb bez powtorzen |
|
|
|
Hm..
"i podzielić ją przez np 0,0000001 co da liczbe rzeczywistą"
drobna pomyłka :) dzielenie przez ułamek to mnożenie przez odwrotność, to będzie liczba całkowita.
można podzielić liczbe losową całkowitą przez np 100000 powstanie liczba rzeczywista.. co do zapisu liczb rzeczywistych na komputerze są one zapisane w postaci wykładniczej, np 123.456 będzie zapisane jako 123456 * 10^(-3). (123456 to mentysa a -3 to wykładnik) do liczb rzeczywistych służy koprocesor czyli procesor arytmetyczny..
|
|
| Back to top |
|
|
Xitami
Poziom 21
Joined: 10 Aug 2004
Posts: 1126
Location: Gliwice
|
#11
23 Sep 2004 14:16 losowanie 4 liczb bez powtorzen |
|
|
|
czemu koprocesor? nawet atmelek na 8 nóżkach radzi sobie z liczbami rzeczywistymi, a co do zapisu liczb, to jest dokładnie tak jak piszesz ale inaczej ;)
Komputery liczą dwójkowo, kiedyś owszem były takie co liczyły dziesiętnie np. ENIAC ;) ale nawet w PC urzywa się czasem zapisu BCD, między innymi dla tego, że jest ten kłopot z 1/10. Wagi bitów w liczbie rzeczywistej to: 1/2, 1/4, 1/8, 1/16 itd.
|
|
| Back to top |
|
|
