Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

[Zadatak] Maksimalni podniz uzastopnih brojeva

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Maksimalni podniz uzastopnih brojeva

Strane: 1 2

[ Pregleda: 9764 | Odgovora: 29 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 13:42 - pre 207 meseci
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.
Mislim, šta reći !
 
Odgovor na temu

vilyu
Web Developer
Beograd, Srbija

Član broj: 1188
Poruke: 444



+2 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 14:12 - pre 207 meseci
Č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.
Pera električar 0637129710, BG, preporučujem.
 
Odgovor na temu

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 14:25 - pre 207 meseci
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 :).
Mislim, šta reći !
 
Odgovor na temu

kime1
Srbija

Član broj: 13275
Poruke: 939
*.151.EUnet.yu.



+2 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 19:59 - pre 207 meseci
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)...
 
Odgovor na temu

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 20:06 - pre 207 meseci
Razumeo! :)
Rekoh bez sortiranja, ali nije ni bitno sad, samo sam hteo da vidim moze li se to bez sortiranja.

Pozdrav!
Mislim, šta reći !
 
Odgovor na temu

vilyu
Web Developer
Beograd, Srbija

Član broj: 1188
Poruke: 444
Via: [es] mailing liste



+2 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 20:43 - pre 207 meseci
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.
Pera električar 0637129710, BG, preporučujem.
 
Odgovor na temu

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 20:49 - pre 207 meseci
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.
Mislim, šta reći !
 
Odgovor na temu

vilyu
Web Developer
Beograd, Srbija

Član broj: 1188
Poruke: 444
Via: [es] mailing liste



+2 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 21:24 - pre 207 meseci
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.
Pera električar 0637129710, BG, preporučujem.
 
Odgovor na temu

kime1
Srbija

Član broj: 13275
Poruke: 939
*.22.eunet.yu.



+2 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva24.01.2006. u 22:42 - pre 207 meseci
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 :)...
 
Odgovor na temu

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva27.01.2006. u 18:47 - pre 207 meseci
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 :)
Mislim, šta reći !
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva27.01.2006. u 19:32 - pre 207 meseci
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.
 
Odgovor na temu

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva27.01.2006. u 19:45 - pre 207 meseci
Moze, resi ti to da vidim kako izgleda. Nije mi hitno.
Mislim, šta reći !
 
Odgovor na temu

vilyu
Web Developer
Beograd, Srbija

Član broj: 1188
Poruke: 444



+2 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva27.01.2006. u 20:11 - pre 207 meseci
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]
Pera električar 0637129710, BG, preporučujem.
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4898
*.nat-pool.po.sbb.co.yu.

Jabber: xfiles@elitesecurity.org


+637 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva27.01.2006. u 20:18 - pre 207 meseci
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]
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva29.01.2006. u 10:53 - pre 207 meseci
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.
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4898
*.nat-pool.po.sbb.co.yu.

Jabber: xfiles@elitesecurity.org


+637 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva29.01.2006. u 11:19 - pre 207 meseci
Onda sam i ja zeznuo. Ja sam dao primer za NAJDUZI OPDADAJUCI niz (!!!) i to
ne UZASPOPNIH, nego samo da je opadajuci TRENUTNI > PRETHODNOG.

 
Odgovor na temu

android~paranoid

Član broj: 81947
Poruke: 211
*.zrlocal.net.



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva29.01.2006. u 12:50 - pre 207 meseci
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.
Mislim, šta reći !
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4898
*.nat-pool.po.sbb.co.yu.

Jabber: xfiles@elitesecurity.org


+637 Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva29.01.2006. u 13:03 - pre 207 meseci
Code:

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


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

 
Odgovor na temu

dragansm
Dragan Smiljanic

Član broj: 38170
Poruke: 191
195.252.85.*



Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva29.01.2006. u 14:31 - pre 207 meseci
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
 
Odgovor na temu

NrmMyth
Ivan Maček
Split

Član broj: 63456
Poruke: 849
*.cmu.carnet.hr.

Sajt: www.dump.hr


Profil

icon Re: [Zadatak] Maksimalni podniz uzastopnih brojeva29.01.2006. u 22:42 - pre 207 meseci
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.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Maksimalni podniz uzastopnih brojeva

Strane: 1 2

[ Pregleda: 9764 | Odgovora: 29 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.