Pascalban van egy 9 és egy 10 elemű tömböm mindkettőben random számok vannak 1-től 100-ig és meg kell vizsgálnom hogy a két tömbben van e egyenlő szám hogy lehetséges ez?

Fogod az első tömb első elemét és hozzá hasonlítod a második tömb összes elemét. Aztán a második, n. elemet amíg el nem fogynak az első tömb elemei.

Két for ciklus az egész.

9 és 10 emelnél valóban az első válaszoló által írt algoritmus a legegyszerűbb, mivel csak 90 db összehasonlítás, ez a gépnek semmi.

Viszont ha jóval nagyobb elemszámú lennének a tömbök, akkor pl. rendezheted mind2 tömböt növekvő sorrendbe, és sorban veheted az elemeket a 2 tömbből. Ez jóval bonyolultabb, de sokkal hatékonyabb. A te esetedben tényleg nincs rá szükség.

Az a megkötés pedig hogy 1-től 100-ig vannak az értékek mégjobban leegyszerűsíti a problémát. Így elég 2 db 100-as méretű bool tömböt felvenni. Végigmész az első tömbön, és a bool tömb adott elemét true-ra állítod a tömbödben lévő szám alapján. Ezt megcsinálod a másik tömbre is. Majd egyetlenegy for ciklussal (1-től 100-ig) összehasonlítod a bool tömböket, ha mind2-ben true-van ugyanazon a pozíción, akkor van egyforma szám.

Előttem szólónak:

Nem kell semmilyen bool tömb. A kérdés, hogy "van-e egyenlő", nem az, hogy adjuk meg ezek indexét, vagy mennyiségét.

Egy nem túl hatékony, de egyszerű ALGORITMUS:

bool van := hamis

ciklus i=0-tól 10-ig:

ciklus j=0-tól 9-ig:

ha t1[i] == t2[j]

van:=igaz

elág. vége

ciklus vége

ciklus vége

A feltételes elágazásba akár betehetünk egy ciklus megszakítást, ha csak azt kérdezzük, hogy van-e 2 egyforma. Így, amint megtalálta az elsőt leáll. Így valamivel hatékonyabbá tehetjük a kódot.

Előttem szólónak: Pont ezt írtam, hogy 9 és 10 elem esetén elég az egymásba ágyazott ciklus, hisz nagyon kevés elem van. Te is írtad, hogy nem hatékony. N*M összehasonlítás, ha az első tömb elemeinek száma N, a másodiké pedig M.

Ha jóval több elem lenne, akkor sokkal hatékonyabb két bool tömböt feltöleni. Ez M+N lépés lenne. Az összehasonlítás pedig konstans 100 lépés. Tehát összesen M+N+100.

Tegyük fel, hogy M=10000, N=20000, ekkor a te algoritmusod lépésszáma 200 millió, az enyém pedig 30100.

Igazad is van, meg nem is

Egy jóval nagyobb tömbnél valszeg nem 1-100-ig lennének a számok (igaz, ez csak egy random feladat, de mindegy), plusz sorba kell rendezned, az is lépésszám, és beleszámít

a harmadik meg, hogy a páronkénti összehasonlítás rendezett tömbökre sem működik, csomó párt nem találna meg

Előzőnek:

Úgy értem, hogy arra az algoritmusmora válaszoltál, amiben lényeges, hogy a számok 1 és 100 közöttiek, ha nem így van, akkor tekintsd a követketőket tárgytalannak.

Az említett általam írt algoritmusnál nem kell sorbarendezni. Valószínűleg nem érted az algoritmust.

Algoritmus:

- 100 elemű t1bool tömb létrehozása false értékekkel.

- 100 elemű t2bool tömb létrehozása false értékekkel.

ciklus i = 1-től M-ig

t1bool[tomb1[i]] = true; <= M lépés

ciklus vége

ciklus i = 1-től M-ig

t2bool[tomb2[i]] = true; <= N lépés

ciklus vége

ciklus i = 1-től 100 ig

ha t1bool[i] és t2bool[i] => return "van azonos szám" <= max 100 lépés

ciklus vége

return "nincs azonos szám"

tehát összességében max M+N+100 lépés, sorbarendezés nem szükséges.

Mivel rendezett tömbökről szó sincs, ezért az utolsó mondatod érvényét veszti. (Nem mintha nem lehetne 2 rendezett tömb esetén lineáris időben megtaláni az azonos elemeket, gondolkozz picit, nyilván nem ugyanaz lesz az indexük, de azért nem egy nagy kihívás)

Abban persze igazad van, hogy jóval több elemnél a számok valószínűleg nem 1 és 100 közöttiek lesznek, de akár lehetnének is, ha ez a követelmény, mért ne?

-----

Korábban írtam egy sorbarendezős algoritmust is, ennek a lépésszáma:

- 1. tömb sromarendezése megoldható M*log(M) lépésben

- 2. tömb sromarendezése megoldható N*log(N) lépésben

- azonos elemek keresése: min(M,N) lépésben megoldható

összesen:

M*log(M) + N*log(N) + min(M,N), ami lényegesen jobb, mint a triviális M*N-es algoritmus (nyilván az eredeti 9*10-es esetben előfordulhat, hogy rosszabb)