Jak napisać algorytm generujący 10000 razy inną liczbę w zakresie 10000?
Pętla raczej odpada :-8 .....
- Rejestracja:około 22 lata
- Ostatnio:prawie 19 lat
0
jeśli dobrze zrozumiałem o co ci chodzi to jedno z rozwiązań może być takie
var
wylosowana,i,j:word;
tab_liczb:array [0..9999] of word;
czy_juz_byla:boolean;
begin
i:=1;
tab_liczb[0]:=random(10000);
while i<9999 do
begin
czy_juz_byla:=false;
wylosowana:=random(10000);
for j:=0 to i do
begin
if tab_liczb[j]= wylosowana then
begin
czy_juz_byla:=true;
break;
end;
end;
if czy_juz_byla=false then
begin
tab_liczb[j]:= wylosowana;
i:=i+1;
end;
end;
end;
- Rejestracja:ponad 22 lata
- Ostatnio:około 21 godzin
0
a to moja wersja, ociupinkę szybsza od tej wyżej, niestety złożoność obliczeniowa prawie taka sama (w najgorszym przypadku N^2):
const
MAX_SIZE = 1000;
var
randompool : array[1..MAX_SIZE] of boolean;
random_bezpowt : array[1..MAX_SIZE] of word; {tu wyląduje wynik}
i,j,max,result,min : word;
begin
Randomize;
max := MAX_SIZE; min := max;
for i := 1 to MAX_SIZE do randompool[i] := false;
repeat
j := random(max)+1;
if j < min then min := j; {pozycja najniższego true w tablicy}
i := min-1;
for result := min to MAX_SIZE do {odmierzamy j*false}
begin
if not randompool[result] then inc(i);
if i = j then break;
end;
randompool[result] := true;
random_bezpowt[max] := result;
dec(max);
until max = 0;
end.
Może ktoś ma pomysł na jakiś algorytm o złożoności N*logN?
[dopisane]
Albo przy pomocy TStringList i usuwania wylosowanych już. Było na forum parę razy.
Nie żartuj, TStringList jest za powolne! To będzie złożoność (N*logN)*BARDZO_DUZA_STALA
//ale złożoność przyzwoita :) można sobie pewnie napisac szybszą listę, jakby kto chciał. pq
- Rejestracja:ponad 21 lat
- Ostatnio:ponad 12 lat
0
Aż miło sie patrzy, gdy chłopaki sie produkują (wielkie jest piękne?) ...
Poza tym nie widze mozliwości, aby tego rodzaju losowanie nie było w pętli.
type boolbuf=packed array of boolean;
var i,j,k,l:integer;
t:boolbuf;
begin
l:=10000;
setlength(t,l);
for j:=0 to l-1 do t[i]:=false;
j:=l;
while(j>0)do
begin
k:=random(j);
asm inc [k] end;
i:=l;
while(k>0)do
begin
asm dec [i] end;
dec(k,byte(not t[i]))
end;
asm dec [j] end;
inc(byte(t[i])); // t[i]:=true :]
// tu... i to wartośc odpowiednio losowa.
robiecoś(i)
end;
setlength(t,0)
end;
// było, było, było, było.
- Rejestracja:około 22 lata
- Ostatnio:ponad 4 lata
- Postów:137
0
Zadanie jest conajmniej niedospecyfikowane, z powodu tego że autor odrzuca z góry najbardziej logiczne rozwiązanie.
Ja widzę dwa aspekty:
- Generowanie jakiegoś unikalnego identyfikatora/pinu o określonej długości. Tu pasują wszystkie rozwiazania przedmówców, ale chyba najlepszy jest ten ze string list. Losujemy tradycyjna metoda sprawdzamy czy juz byl, jak byl losujemy ponownie, jak nie to używamy i dorzucamy.
- Ktoś chce mieć wszystkie liczby z zakresu do 1000 ale w przypadkowej kolejności. Wpakujmy je więc do tablicy i w zależności od "ilości czasu" pomieszajmy trochę.
- Rejestracja:około 22 lata
- Ostatnio:prawie 11 lat
0
To może jeszcze jeden sposobik:
const
Zakres = 10000;
IloscLiczb = 999;
var
Lista: TList;
I, Index, Liczba: Integer;
begin
Lista := TList.Create;
try
Lista.Capacity := Zakres;
{zapełniamy listę liczbami z zakresu}
for I := 1 to Zakres do
Lista.Add(Pointer(I));
for I := 0 to IloscLiczb -1 do
begin
Index := Random(Zakres - I);
{ tu otrzymujemy kolejną liczbę }
Liczba := Integer(Lista.Items[Index]);
{ usuwamy z listy niewylosowanych }
Lista.Delete(Index);
end;
finally
Lista.Free;
end;
end;
Oczywiście IloscLiczb nie może być większa niż Zakres.
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.