Pascalban hogyan tudnék úgy random számokkal teljesen feltölteni egy tömböt, hogy minden szám csak 1-szer fordul elő?

A generálási intervallum legyen legalább akkora mint a tömb mérete.

Most kapásból 3 módszer jutott eszembe illetve több, de csak a 3 legegyszerűbbet írom le

1.

Végig mész a tömbön egy for-ral és addig generálsz egy új számot amíg olyan számot nem kapsz ami még nem fordult elő a tömbben az aktuális tömbindex-1 ig a tömbbe amit szintén egy forral tudsz eldönteni.

2.

Ha kis számokról van szó akkor használhatsz halmazt (set of byte) és nézed hogy a halmazba van e az aktuálisan generált szám csak akkor rakod be a tömbbe az aktuális helyre ha a halmaz nem tartalmazza majd berakod a halmazba is. Gyorsabb mint az 1.-es módszer de nagy tömbre nem működik.(Mert a halmazba csak 0-255-ig egész értékeket lehet berakni.)(Kis trükkel működővé lehet tenni nagy tömbökre is.)

3.

Index táblát használsz(segéd tömböt pl), ami garantálja hogy minden szám egyszer forduljon elő. Lényegesen gyorsabb mint az előző 2 (nagyobb tömbökön jól látszik a különbség.)

Mekkora tömböt?

Milyen elemekkel? (egész, valós? vagy nem is szám? milyen intervallumban található?)

12:45

Leírom

1 )

const

intervallumMeret=1000;

legKisebbElem=1;

tombmeret=20;

var

i1,i2,generaltszam:longint;

tomb:array [1..tombmeret] of longint;

ezvolt:boolean;

begin

randomize;

for i1:=1 to length(tomb) do

begin

repeat

generaltszam:=random(intervallumMeret)+legKisebbElem;

ezvolt:=false;

for i2:=1 to i1-1 do

if generaltszam=tomb[i2] then

ezvolt:=true;

until ezvolt=false;

tomb[i1]:=generaltszam;

end;

for i1:=1 to length(tomb) do

write(tomb[i1]:5,',');

end.

2.a )

const

intervallumMeret=40;

legKisebbElem=1;

tombmeret=13;

{Intervallummeret es a legKisebbElem es intervallumMeret es osszeguk nem eshet kivul a byte ertelmezesi tartomanyan}

var

i,generaltszam:byte;

tomb:array [1..tombmeret] of byte;

halmaz:set of byte;

begin

randomize;

halmaz:=[];{Halmaz uresitese}

for i:=1 to length(tomb) do

begin

repeat

generaltszam:=random(intervallumMeret)+legKisebbElem;

until not (generaltszam in halmaz);{eleme e a halmaznak a generaltszam}

tomb[i]:=generaltszam;

halmaz:=halmaz+[generaltszam];{berakjuk a halmazba a generaltszam-ot}

end;

for i:=1 to length(tomb) do

write(tomb[i]:5,',');

end.

2.b)

const

intervallumMeret=10;

legKisebbElem=1;

tombmeret=10;

var

i,generaltszam:longint;

tomb:array [1..tombmeret] of longint;

halmaz:array [legKisebbElem .. intervallumMeret] of boolean;{ A trukk az hogy egy boolean array-t tekinthetek halmaznak ugy hogy az i-edik eleme true ha tartalmazza i-t, false ha nem tartalmazza i-t}

begin

randomize;

{halmaz:=[];} {Halmaz uresitese}

for i:=legKisebbElem to intervallumMeret do

halmaz[i]:=false;

for i:=1 to length(tomb) do

begin

repeat

generaltszam:=random(intervallumMeret)+legKisebbElem;

{until not (generaltszam in halmaz);}{eleme e a halmaznak a generaltszam}

until not halmaz[generaltszam];

tomb[i]:=generaltszam;

{halmaz:=halmaz+[generaltszam];}{berakjuk a halmazba a generaltszam-ot}

halmaz[generaltszam]:=true;

end;

for i:=1 to length(tomb) do

write(tomb[i]:5,',');

end.

3)

const

intervallumMeret=5;

legKisebbElem=1;

tombmeret=5;

{Itt nem kell nezni hogy olyan szamot generalt e ami mar volt e, mert az IndexTabla ezt garantalja.}

{Alapotlet az hogy a generalhato szamok halmazanak elemeit breakjuk egy akkora

tombbe mint ahany eleme van ennek a halmaznak.

Majd ezek kozul egyet kivalasztunk, erteket es indexet megjegyezzuk,

utana a legutolso elem erteket betesszuk az imenti indexu helyre (belathato kombinatorikailag hogy helyes), ezutan csokkentjuk a tomb meretet.

Az implenetacioba egy rekorddal van megoldva, a tomb meretet nem csokkentjuk hanem egy valtozot csokkentunk es

ugy tekintjuk mintha ez a valtozo hatarozna meg a tomb meretet.}

type

IndexTabla=record

maxindex:longint;

indexek:array [1 .. intervallumMeret] of longint;

end;

procedure initIndextabla(var it:IndexTabla);

var

i:longint;

begin

for i:=1 to intervallumMeret do

it.indexek[i]:=i-1+legKisebbElem;

it.maxindex:=intervallumMeret;

end;

function randomszamgeneral(var it:IndexTabla):longint;

var

genszamindex,eredmeny:longint;

begin

genszamindex:=random(it.maxindex)+1;

eredmeny:=it.indexek[genszamindex];

it.indexek[genszamindex]:=it.indexek[it.maxindex];

dec(it.maxindex);

randomszamgeneral:=eredmeny;

end;

var

i:longint;

tomb:array [1..tombmeret] of longint;

it:IndexTabla;

begin

randomize;

initIndextabla(it);

for i:=1 to length(tomb) do

tomb[i]:=randomszamgeneral(it);

for i:=1 to length(tomb) do

write(tomb[i]:5,',');

end.

1-es módszer a legegyszerűbb és a legrosszabb futási idejű egyben.

A 3-as módszer a leg bonyorultabb és a leggyorsabb futási idejű is egyben.

Kicsit kapkodtam, korrigáltam a 2 b megoldást, mert csak ha legKisebbElem=1-re van állítva csak akkor jó. legKisebbElem=100 ra írtam át (ez a megfelelő kereten belül tetszőlegesen átírható.)

const

intervallumMeret=10;

legKisebbElem=100;

tombmeret=10;

var

i,generaltszam:longint;

tomb:array [1..tombmeret] of longint;

halmaz:array [legKisebbElem .. intervallumMeret+legKisebbElem-1] of boolean;{ A trukk az hogy egy boolean array-t tekinthetek halmaznak ugy hogy az i-edik eleme true ha tartalmazza i-t, false ha nem tartalmazza i-t}

begin

randomize;

{halmaz:=[];} {Halmaz uresitese}

for i:=legKisebbElem to intervallumMeret+legKisebbElem-1 do

halmaz[i]:=false;

for i:=1 to length(tomb) do

begin

repeat

generaltszam:=random(intervallumMeret)+legKisebbElem;

{until not (generaltszam in halmaz);}{eleme e a halmaznak a generaltszam}

until not halmaz[generaltszam];

tomb[i]:=generaltszam;

{halmaz:=halmaz+[generaltszam];}{berakjuk a halmazba a generaltszam-ot}

halmaz[generaltszam]:=true;

end;

for i:=1 to length(tomb) do

write(tomb[i]:5,',');

end.