[ android~paranoid @ 24.01.2006. 13:42 ] @
Zadatak mi je da od niza brojeva recimo
3,6,4,5,11,11,7

Nadjem maksmalni podniz uzastopnih brojeva. U ovom slucaju ce to biti :
3,4,5,6,7

Bez nekog sortiranja ili tako nesto, samo prolaskom kroz niz.
[ vilyu @ 24.01.2006. 14:12 ] @
Čekaj, ili ima sortiranja, ili nema. Ako nema, već se samo prođe kroz niz, onda ne možeš da dobiješ 6-icu u rezultujućem nizu. Rešenje da samo jednom prođeš kroz niz bi bilo i da pritom kreiraš jednostruko ulančanu listu, ili stablo, gde svaki element stavljaš na odgovarajuće mesto, ali je i to sortiranje.
[ android~paranoid @ 24.01.2006. 14:25 ] @
Hej, taj zadatak u knjizi je posle nizova, a sortiranje nizova se nalazi kasnije, posle svake lekcije su zadaci koji se odnose samo na tu lekciju. Ja se dva dana ubijam pokusavajuci ovo da resim, mislio sam sa dve-tri for petlje ali nikako mi ne ide. Jos liste nisam radio bar u C-u, ni stabla :).
[ kime1 @ 24.01.2006. 19:59 ] @
Ako jedan prolazak podrazumeva jedan prolazak kroz početni niz,onda je ok :)... sortiraj ga u drugi niz,ili listu,uvedi pomoćnu promenjivu koja broji uzastopne podatke i nađi najveći podniz (kada se prekine,postaviš na nulu i kreneš odpočetka,pri sledećem prekidu upoređuješ sa trenutnim najvećim podnizom,ako je veći promeniš,ako ne,ništa)...
[ android~paranoid @ 24.01.2006. 20:06 ] @
Razumeo! :)
Rekoh bez sortiranja, ali nije ni bitno sad, samo sam hteo da vidim moze li se to bez sortiranja.

Pozdrav!
[ vilyu @ 24.01.2006. 20:43 ] @
Moze i bez sortiranja, samo program onda biva kompleksnosti n^n. Dakle,
napravis jednu for petlju da nadje najmanji element veci od prethodnog
nadjenog (za sam start, to je prvi element niza). A onda tu for petlju
obuhvatis jos jednom kojom n (n je broj elemenata niza) puta prodjes
kroz ceo niz. U svakom prolazu unutrasnjom petljom nalazis tacno jedan
novi element trazenog, rezultujuceg niza.

No ovom resenju treba pristupiti samo u skolske svrhe, a ne i
primenjivati ga u praksi.
[ android~paranoid @ 24.01.2006. 20:49 ] @
Tako sam i pokusavao nesto, ali nikako da se ispetljam iz toga.
Jos tu treba misliti o tome da bude najveci niz, ma, uradicu to sa sortiranjem.

Vama hvala.
[ vilyu @ 24.01.2006. 21:24 ] @
Ajde da probam iz glave
Code:

//prvo nadjemo najmanji i najveci element
min = niz[0];
max = niz[0];
for (i=1; i<n; i++) {
   if (niz[n] < min)
     min = niz[n];
   if (niz[n] > max)
     max = niz[n];
}

//prvi element zapamtimo
rez[0] = min;
br_nadjenih = 1;
prvi_veci = max;

nadjeno = 0;
for (i=0; i <= n; i++) {
   for (j=0; j <= n; j++) {
     if ( (niz[j] > min) and (niz[j] < prvi_veci) {
       prvi_veci = niz[j];
       nadjeno = 1;
     }
   }
   if (nadjeno) {
     rez[br_nadjenih] = prvi_veci;
     br_nadjenih++;
     nadjeno = 0;
     min = prvi_veci;
     prvi_veci = max;
   } else {
     rez[br_nadjenih] = prvi_veci; //odnosno max;
     break; //izadji iz petlje
   }

}


Dakle, logika je ova:
nadjes max i min element
min, je prvi clan rezultata, a potom trazis prvi_veci, kao najmanji veci
od poslednjeg nadjenog elementa (njega pamti promenljiva min). Kad ga
nadjes, dodas ga u rezultujuci niz, i povecas min da pamti da ne trazi
mani od tog. Ako ga ne nadje, to znaci da je prvi_veci, koji je max,
poslednji i najveci element koji jos nije unet u rezultat, pa ga dodas i
izadjes iz petlje.
[ kime1 @ 24.01.2006. 22:42 ] @
Besmisleno je da pokušavaš da uradiš bez sortiranja sa redom složenosti >= n^2, jer to je suština sortiranja.... da si pitao može li se to uraditi brže bez sortiranja,to je ok :) ,a ti nazovi to kako god :)...
[ android~paranoid @ 27.01.2006. 18:47 ] @
vilyu: Genijalna je ideja sa min i max! Program ipak nece raditi:

I)
Citat:
rez[0] = min;
Ne mora najmanji element u nizu da pripada tom podnizu. Ipak i u tom slucaju da je tako ne radi.

II)
Citat:
(niz[j] > min) and (niz[j] < prvi_veci)
Brojevi treba da budu uzastopni, onda bi trebalo ovo da bude (niz[j]==prvi_veci-1), al opet ne radi dobro.

Da mi ovo batalimo :) i ovaj primer ce posluziti nekako :)
[ NrmMyth @ 27.01.2006. 19:32 ] @
Ako mislis na najduzi podniz, onda je to DP... rekurzija.
Mogu ti rijesiti do nedjelje, jer sutra nisam kuci, a sad necu.
Vjerojatno ce netko vec uletjeti sa rijesenjem, ali ako nitko, ja cu.
Poz.
[ android~paranoid @ 27.01.2006. 19:45 ] @
Moze, resi ti to da vidim kako izgleda. Nije mi hitno.
[ vilyu @ 27.01.2006. 20:11 ] @
Pardon, prevideo sam da se radi o uzastopnim brojevima. Rešenje koje sam dao govori samo o rastućim. Pošto je reč o uzastopnim, onda ipak moraš da sortiraš niz, i potom da prebrojavaš od kog index-a tražiš najveći podniz i koliko taj podniz ima elemenata. Pamtiš index prvog elementa u sortiranom nizu i broj uzastopnih elemenata, a kad nađeš veći, onda njegov index i broj uzastopnih zapišeš preko onoga šta si pamtio.

[Ovu poruku je menjao vilyu dana 27.01.2006. u 21:12 GMT+1]
[ X Files @ 27.01.2006. 20:18 ] @
Zasto ne iskoristis kod koji sam ti dao pre neki dan? Evo ti onaj stari, samo
prilagodjen za novu situaciju /NETESTIRANO/


Code:

// funkcija koja prima char* kao argument...
void ispisi_podniz( char *unos )
{
   // privremeni niz gde ces stavljati koliko uzastopnih ima od te pozicije...
   int m[999];

   // vrti dok god ima brojeva u nizu...
   for ( int i=0; i<strlen(unos); i++ )
   {
      // koliko uzastopnih brojeva smo pronasli...
      int brojac_uzastopnih_opadajucih = 1;

      // prvi broj od koga ispitujemo da li su sledeci opadajuci...
      int pocetni = unos[i];

      // idi redom i gledaj da li je opadajuci
      for ( int j=i+1; ( j<strlen(unos) )&& (unos[j] < pocetni); j++ )
      {
         // saberi...
         ++brojac_uzastopnih_opadajucih;

         // sada ispitujemo od prethodnog...
         pocetni = unos[j];
      }

      // na poziciji i stavi koliko smo ih pronasli
      m[i] = brojac_uzastopnih_opadajucih;

      // ovo moze i ne mora (da se ubrza [i] petlja)
      if ( brojac_uzastopnih_opadajucih > 1 )
         i += brojac_uzastopnih_opadajucih-1;
   }

   // pronadji index maximalnog broja iz m[], ovo sigurn moze i krace, ali sada dajem samo netestiran primer
   int max = 0;
   int index_of_max = 0;

   for ( int i=0; i<strlen(unos); i++ )
      if ( m[i] >= max )
      {
        max = m[i];
        index_of_max = i;
      }

   // ispisi taj niz
   for ( int j=index_of_max; j<index_of_max+max; j++ )
      ShowMessage( unos[j] );

}

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   // ...
   char *unos = "1235432154354";
   // ...
   ispisi_podniz( unos );
   // ..
}


S obzirom da su u pomocnom nizu m[] zapamcene duzine svih opadajucih podnozova
lako mozes sam ispis modifikovati da ti ispiše sve podnizove koji su ISTE dužine, a
ne samo jedan.


[Ovu poruku je menjao X Files dana 28.01.2006. u 09:58 GMT+1]
[ NrmMyth @ 29.01.2006. 10:53 ] @
Moj grijeh, nisam dobro procitao tvoj zadatak. Znaci radi se o maximalnom nizu uzastopnih brojeva.
To vise nije DP nego Greedy algoritam.
X Files ti je dao rijesenje.
[ X Files @ 29.01.2006. 11:19 ] @
Onda sam i ja zeznuo. Ja sam dao primer za NAJDUZI OPDADAJUCI niz (!!!) i to
ne UZASPOPNIH, nego samo da je opadajuci TRENUTNI > PRETHODNOG.

[ android~paranoid @ 29.01.2006. 12:50 ] @
Citat:
Pamtiš index prvog elementa u sortiranom nizu i broj uzastopnih elemenata, a kad nađeš veći, onda njegov index i broj uzastopnih zapišeš preko onoga šta si pamtio.


Upravo sam tako uradio.

Citat:
void __fastcall TForm1::Button1Click(TObject *Sender)


Ovo dodje kao nesto iz Delphija ili je to c++? :)

Prepisacu i to za opadajuci niz, cisto da vidim kako funkcionise.
[ X Files @ 29.01.2006. 13:03 ] @
Code:

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   // ovde neki kod ...
}


Da. Ovo je Borland C++ Builder dogadjaj kada pritisnes taster Button1.

[ dragansm @ 29.01.2006. 14:31 ] @
Ukoliko nisi odustao od resavanja:
- recimo da je max dozvoljeni broj u ulaznom nizu Nmax
- napravis niz boolova "flags" duzine Nmax i postavis mu sve elemente na false.
- prodjes kroz listu unetih brojeva i postavis sve elemente flags na true sa indeksima koji postoje u ulaznom nizu. Ovako problem svodis na "nadji najduzi niz true elementa" u nizu flags.
- uvedi jednu promenljivu bestLen = 0 koja sadrzi najduzi niz true elemenata i drugu currLen = 0 koja sadrzi trenutnu duzinu niza true elemenata
- prolazi kroz sve elemente flags redom. Ako je element true uvecavaj currLen (ako je currLen prethodno bio 0 onda upisi index trenutnog elementa kao trenutni pocetak niza true elemenata u currStart), a ako nije postavi ga na currLen = 0. Ako je currLen > bestLen postavi bestLen na currLen i bestStart na currStart.
- na kraju u bestStart se nalazi pocetak najduzeg niza uzastopnih brojeva, au bestLen njegova duzina
[ NrmMyth @ 29.01.2006. 22:42 ] @
Citat:
Citat:
Pamtiš index prvog elementa u sortiranom nizu i broj uzastopnih elemenata, a kad nađeš veći, onda njegov index i broj uzastopnih zapišeš preko onoga šta si pamtio.
Upravo sam tako uradio.

Nemoze to tako, sta ako imas niz: 5 1 2 6 3 4, sortiran izgleda: 1 2 3 4 5 6, a najveci podniz je 1 2 3 4.

npr.
7 8 3 4 8 9 2 5 6 10 9 5 11
radis sa listom podnizova (vektora)
krenes u for do kraja niza, ako je broj sljedbenik nekome u listi onda tu povecas brojac.
Razlicitom oznakom su naznaceni razliciti vektori u listi.

7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11
7 8 3 4 8 9 10 9 5 11

Sve ti je lijepo obojano i podcrtano...
Ti rijesi algoritam.
[ vilyu @ 29.01.2006. 23:27 ] @
Citat:
Nemoze to tako, sta ako imas niz: 5 1 2 6 3 4, sortiran izgleda: 1 2 3 4 5 6, a najveci podniz je 1 2 3 4.


NrmMyth, hoćeš li mi, molim te, objasniti kako je to 1 2 3 4 najveći podniz niza koji sortiran izgleda 1 2 3 4 5 6, i kako to nije upravo ceo taj niz od 6 elemenata?
[ NrmMyth @ 30.01.2006. 08:12 ] @
Kad se kaze podniz misli se na podniz elemenata bez rezmjestaja istih, a ne na niz koji se moze sastaviti od svih elemenata prijasnjeg skupa.
5 1 2 3 6 4
[ vilyu @ 30.01.2006. 11:41 ] @
OK, a sad pogledaj prvi post u temi gde android~paranoid kaže:
Citat:
Zadatak mi je da od niza brojeva recimo
3,6,4,5,11,11,7

Nadjem maksmalni podniz uzastopnih brojeva. U ovom slucaju ce to biti :
3,4,5,6,7


Vodili smo se ovim primerom koji je on rekao da želi da postigne, pri čemu je automatski maksimalni podniz elemenata od 1 do 6 upravo sam taj niz, ma kako da su oni raspoređeni unutar zadatog niza.
[ android~paranoid @ 30.01.2006. 16:33 ] @
Citat:
Ukoliko nisi odustao od resavanja:
- recimo da je max dozvoljeni broj u ulaznom nizu Nmax
- napravis niz boolova "flags" duzine Nmax i postavis mu sve elemente na false.
- prodjes kroz listu unetih brojeva i postavis sve elemente flags na true sa indeksima koji postoje u ulaznom nizu. Ovako problem svodis na "nadji najduzi niz true elementa" u nizu flags.


Slabo sam te ja sta razumeo brate. Moraces na nizem nivou :)

[ NrmMyth @ 31.01.2006. 09:38 ] @
Citat:
vilyu: OK, a sad pogledaj prvi post u temi gde android~paranoid kaže:


Vodili smo se ovim primerom koji je on rekao da želi da postigne, pri čemu je automatski maksimalni podniz elemenata od 1 do 6 upravo sam taj niz, ma kako da su oni raspoređeni unutar zadatog niza.

Moj grijeh.
Svejedno podniz nije ono sta je on naveo, ali neka.

Vjerujem onda da si mu dao rijesenje.
[ android~paranoid @ 31.01.2006. 18:42 ] @
Mozda je bolji izraz podskup tog niza, ali to je to sto je vilyu dao kao resenje, jer se ovakav primer sto sam dao nalazi u objasnjenju zadatka.
[ android~paranoid @ 03.02.2006. 20:25 ] @
Citat:
Dakle, logika je ova:
nadjes max i min element
min, je prvi clan rezultata, a potom trazis prvi_veci, kao najmanji veci
od poslednjeg nadjenog elementa (njega pamti promenljiva min). Kad ga
nadjes, dodas ga u rezultujuci niz, i povecas min da pamti da ne trazi
mani od tog. Ako ga ne nadje, to znaci da je prvi_veci, koji je max,
poslednji i najveci element koji jos nije unet u rezultat, pa ga dodas i
izadjes iz petlje.

Citat:
Pardon, prevideo sam da se radi o uzastopnim brojevima. Rešenje koje sam dao govori samo o rastućim. Pošto je reč o uzastopnim, onda ipak moraš da sortiraš niz, i potom da prebrojavaš od kog index-a tražiš najveći podniz i koliko taj podniz ima elemenata.


Ovaj tvoj program mi daje sortiran niz razlicitih clanova. Da li si na to mislio ili treba nesto drugo da da?
[ c00l3D @ 04.02.2006. 22:27 ] @
Prijatelju nisi bas dobro objasnio ali evo koliko toliko pokusacu da pomognem, ako si mislio na sljedece:
ako imas niz od 2,1,3,4,5,6,1,1,10,2,3,4 onda ti je najveci uzastopni rastuci podniz 3,4,5,6 ako si na to mislio evo onda jedan mali kodic koji ces da testiras nemam ja bas sad vremena ali napati se malo :)

Code:

#include <stdio.h>
#include <conio.h>
#define MAX 10

int niz[MAX];
int tmp_niz[MAX][MAX];
int i=0,j=0,max,brojac[MAX],tmp;

void unos_inc()
{
     printf("Unesi clanove niza: \n");
     for (i=0;i<MAX;i++) 
       {
        scanf("%d",&niz[i]);
        brojac[i]=1;
       }
}

main()
{
int k=0;
unos_inc();
for (i=0;i<MAX-1;i++)
    {      
      if (niz[i]+1==niz[i+1]) 
          {
            tmp_niz[k][j]=niz[i];
            brojac[k]++;
            j++;
          }
        else 
          {
            k++;
            j=0;
          }
    } 
max=brojac[0];
for (i=0;i<k;i++)
 if (brojac[i]>brojac[i+1]) 
    {
    max=brojac[i];
    tmp=i;
    }
printf("\nMaximalan niz ima %d clanova",max);
printf("\nClanovi niza su: \n");
for (i=0;i<max;i++) printf("%d",tmp_niz[tmp][max]);
getch();
}


PS
Ako ima neka greska ispravite me :)
[ NrmMyth @ 04.02.2006. 22:47 ] @
Citat:
vilyu: OK, a sad pogledaj prvi post u temi gde android~paranoid kaže:


Vodili smo se ovim primerom koji je on rekao da želi da postigne, pri čemu je automatski maksimalni podniz elemenata od 1 do 6 upravo sam taj niz, ma kako da su oni raspoređeni unutar zadatog niza.

Jeli ovo to androide???
[ android~paranoid @ 05.02.2006. 13:28 ] @
Citat:
Jeli ovo to androide???


Da, rekao sam da sam ga uradio sa sortiranjem niza.
vilyu rece da kod koji je dao odredjuje rastuci niz, usvari to ce biti sortiran niz bez clanova koji se ponavljaju. c00l3D, ok, to nije ono sto sam na pocetku zeleo, ali radi i on nesto :) . Zanimljivo resenje tako sa matricom, posluzice :)