| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
color
Forumaš(ica)
Pridružen/a: 04. 04. 2003. (16:09:57)
Postovi: (AD)16
Spol: 
|
|
| [Vrh] |
|
C'Tebo
Moderator
Pridružen/a: 03. 11. 2002. (18:40:48)
Postovi: (26A)16
Lokacija: Zagreb
|
 Postano: 16:37 pon, 22. 9. 2003 Naslov: |
    |
|
|
Ne kontam šta oćeš?
Kakva polja? Koliko dimenzionalna? (1, 2, 3, ... , n?)
Je l' treba usporedit sve elemente polja ili samo provjerit jesu li polja ista?
Ne kontam šta oćeš?
Kakva polja? Koliko dimenzionalna? (1, 2, 3, ... , n?)
Je l' treba usporedit sve elemente polja ili samo provjerit jesu li polja ista?
_________________ Click me !
_______________________
Bad panda! |
|
| [Vrh] |
|
C'Tebo
Moderator
Pridružen/a: 03. 11. 2002. (18:40:48)
Postovi: (26A)16
Lokacija: Zagreb
|
| Postano: 16:45 pon, 22. 9. 2003 Naslov: Tek tako, meni za vježbu |
|
|
|
Recimo da trebaš usporediti dva polja (jednodimenzionalna):
[code:1]
int usporedi(int *p1, int *p2, int n)//prvo i drugo polje i broj elemenata
{
int i=0;
int isti=1;
do
{
if !(p1[i]==p2[i]) isti=0;
i+=1;
while ((i<n) && (isti))}
return isti;
}
[/code:1]
Vraća 1, ako su nizovi isti, 0 ako nisu. (Vjerujem da kod ima sintaktičkih pogrešaka za ubit se, pa bih molio dobre dušice ovog foruma da me isprave u svim eventualnim pogreškama, pliz)
Recimo da trebaš usporediti dva polja (jednodimenzionalna):
| Kod: |
int usporedi(int *p1, int *p2, int n)//prvo i drugo polje i broj elemenata
{
int i=0;
int isti=1;
do
{
if !(p1[i]==p2[i]) isti=0;
i+=1;
while ((i<n) && (isti))}
return isti;
}
|
Vraća 1, ako su nizovi isti, 0 ako nisu. (Vjerujem da kod ima sintaktičkih pogrešaka za ubit se, pa bih molio dobre dušice ovog foruma da me isprave u svim eventualnim pogreškama, pliz)
_________________ Click me !
_______________________
Bad panda! |
|
| [Vrh] |
|
color
Forumaš(ica)
Pridružen/a: 04. 04. 2003. (16:09:57)
Postovi: (AD)16
Spol:
|
|
| [Vrh] |
|
steelworker
Site Admin
Pridružen/a: 25. 04. 2003. (11:21:04)
Postovi: (698)16
Lokacija: 4-dimensional space-time continuum. Or some 11-dimensional continuum? Dunna, it's all relative.
|
| Postano: 14:51 sri, 24. 9. 2003 Naslov: |
|
|
|
Ak mozes mjenjati ta polja, onda ih prvo sortiraj, pa provedi C'Tebino usporedjivanje.
Ako ih ne mozes mijenjati, onda napravi nova pomocna u koja stavis ova sortirana i opet usporedi [i]po C'Tebi[/i] ta pomocna sortirana.
Napomena: Ne tvrdim da je to najoptimalnije rješenje, samo je rješenje (ali mislim da je najjednostavnije, a jednostavno je cesto najbolje :wink: ), uzmes quick-sort pa si brz, a i ovo C'Tebino je worst case [i]n[/i], pa si isto brz.
Ak mozes mjenjati ta polja, onda ih prvo sortiraj, pa provedi C'Tebino usporedjivanje.
Ako ih ne mozes mijenjati, onda napravi nova pomocna u koja stavis ova sortirana i opet usporedi po C'Tebi ta pomocna sortirana.
Napomena: Ne tvrdim da je to najoptimalnije rješenje, samo je rješenje (ali mislim da je najjednostavnije, a jednostavno je cesto najbolje  ), uzmes quick-sort pa si brz, a i ovo C'Tebino je worst case n, pa si isto brz.
_________________
I live like this 'cause I like it
And I've seen too much to pretend
You can't ignore the beauty in the things that you love
Like you can't stand the hatred and the lies
|
|
| [Vrh] |
|
C'Tebo
Moderator
Pridružen/a: 03. 11. 2002. (18:40:48)
Postovi: (26A)16
Lokacija: Zagreb
|
| Postano: 17:22 sri, 24. 9. 2003 Naslov: |
|
|
|
Gledaj, ukoliko ti ideš ovim putem:
Gledaš prvi element u prvom nizu i onda uspoređuješ taj el. sa svim ostalim elementima ne gine ti n^2 uspoređivanja. Dakle morao bi:
Čopit prvi element iz p1, usporedit sa svim el. iz p2, ako postoji, taj element nekako označit, da ga ovaj ne bi ponovo uspoređivo s nečim i isponova s drugim el. iz p1.
Tako bi išao i stao ili kad više nema elemenata iz p1 ili kad nemreš nać el. iz p1 u p2. U onom prvom slučaju bi još morao napraviti provjeru je li p1 iste duljine kao p2 (što možeš i prije).
Kada radiš sortiranje, najbolji slučaj je quicksort, što ti je nlog n (međutim, to je toliko premještaja, ne uspoređivanja) i još onaj kod od prije, što ti je n uspoređivanja.
Tako da mi se čini da je ono prvo bolje.
Gledaj, ukoliko ti ideš ovim putem:
Gledaš prvi element u prvom nizu i onda uspoređuješ taj el. sa svim ostalim elementima ne gine ti n^2 uspoređivanja. Dakle morao bi:
Čopit prvi element iz p1, usporedit sa svim el. iz p2, ako postoji, taj element nekako označit, da ga ovaj ne bi ponovo uspoređivo s nečim i isponova s drugim el. iz p1.
Tako bi išao i stao ili kad više nema elemenata iz p1 ili kad nemreš nać el. iz p1 u p2. U onom prvom slučaju bi još morao napraviti provjeru je li p1 iste duljine kao p2 (što možeš i prije).
Kada radiš sortiranje, najbolji slučaj je quicksort, što ti je nlog n (međutim, to je toliko premještaja, ne uspoređivanja) i još onaj kod od prije, što ti je n uspoređivanja.
Tako da mi se čini da je ono prvo bolje.
_________________ Click me !
_______________________
Bad panda! |
|
| [Vrh] |
|
|
:
