Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Algoritam za ispis k članih podskupova n-članog skupa
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
Gost






PostPostano: 14:50 sri, 14. 12. 2005    Naslov: Algoritam za ispis k članih podskupova n-članog skupa Citirajte i odgovorite

Da li netko zna "brz" algoritam za ispis svih k članih podskupova n-članog skupa; Nije bitan kod, već samo ideja. Imao sam ideju sa n petlji koje idu od 0 do 1, pa ovisno da li je 0 ili 1 da ispise ili ne element, ali to mi djeluje komplicirano i jako je sporo (probao sam u matlabu za n=20). Pa ako netko zna molio bih da nesto napise. Hvala
Da li netko zna "brz" algoritam za ispis svih k članih podskupova n-članog skupa; Nije bitan kod, već samo ideja. Imao sam ideju sa n petlji koje idu od 0 do 1, pa ovisno da li je 0 ili 1 da ispise ili ne element, ali to mi djeluje komplicirano i jako je sporo (probao sam u matlabu za n=20). Pa ako netko zna molio bih da nesto napise. Hvala


[Vrh]
Tonci
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 31. 10. 2002. (13:46:40)
Postovi: (61)16
Spol: muško
Sarma = la pohva - posuda
= 9 - 3
Lokacija: Split

PostPostano: 15:14 sri, 14. 12. 2005    Naslov: Citirajte i odgovorite

Najjednostavnije (sto se programiranja tice) rjesenje je rekurzija. Uzmes prvi element i pozoves rekurziju na ostalih n-1 dva puta: prvi put tako da trazis jos k elemenata, drugi put da trazis k-1 elemenata pa im jos dodas taj prvi.

Ono rjesenje sto si ti napisao se moze malo pojednostavniti tako da imas for petlju od 0 do 2^n, pa pretvoris brojac u binarni broj i ispises elemente koji se nalaze na mjestima na kojima su jedinice u binarnom zapisu, ako tih jedinica ima tocno k. Ovo je eksponencijalne slozenosti, dakle, nije dobro.

Vjerojatno postoji neko rjesenje bitno manje slozenosti, ali meni ovako na prvu ruku ne pada na pamet.
Najjednostavnije (sto se programiranja tice) rjesenje je rekurzija. Uzmes prvi element i pozoves rekurziju na ostalih n-1 dva puta: prvi put tako da trazis jos k elemenata, drugi put da trazis k-1 elemenata pa im jos dodas taj prvi.

Ono rjesenje sto si ti napisao se moze malo pojednostavniti tako da imas for petlju od 0 do 2^n, pa pretvoris brojac u binarni broj i ispises elemente koji se nalaze na mjestima na kojima su jedinice u binarnom zapisu, ako tih jedinica ima tocno k. Ovo je eksponencijalne slozenosti, dakle, nije dobro.

Vjerojatno postoji neko rjesenje bitno manje slozenosti, ali meni ovako na prvu ruku ne pada na pamet.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 15:31 sri, 14. 12. 2005    Naslov: Citirajte i odgovorite

Rekurzija je dobra ideja, uz mali dodatak. :-s Treba u rekurziji pratiti koliko si "potrosio" jedinica i koliko nula. 8)

Na pocetku rekurzije provjeravas da li si potrosio sve jedinice. :) Ako jesi, gotovo (as in ne ides dalje s rekurzijom). :D

Zatim provjeris jesi li "potrosio" sve nule; ako jesi, svi preostali brojevi idu u podskup, pa si opet gotov. :D

Nemam ideju za brži algoritam... :?
Rekurzija je dobra ideja, uz mali dodatak. Eh? Treba u rekurziji pratiti koliko si "potrosio" jedinica i koliko nula. Cool

Na pocetku rekurzije provjeravas da li si potrosio sve jedinice. Smile Ako jesi, gotovo (as in ne ides dalje s rekurzijom). Very Happy

Zatim provjeris jesi li "potrosio" sve nule; ako jesi, svi preostali brojevi idu u podskup, pa si opet gotov. Very Happy

Nemam ideju za brži algoritam... Confused



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 0:11 čet, 15. 12. 2005    Naslov: Citirajte i odgovorite

vsego: tocno :). sad cu to elegantno iskodirati, pa cu ga stavit ovdje, ako nekome treba...
vsego: tocno :). sad cu to elegantno iskodirati, pa cu ga stavit ovdje, ako nekome treba...



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 0:29 čet, 15. 12. 2005    Naslov: Citirajte i odgovorite

[code:1]#include <stdio.h>

int a[50]={0};

void rek (int trenutni, int x, int k) {
int i;
if (x<1) { /* ispis, zato moramo imati dodatnu varijablu k */
for (i=0;i<k;i++)
printf("%d ", a[i]);
printf("\n");
return;
}

if (trenutni < x) return; /* ako je ostalo manje brojeva nego sto nam treba, prekinimo */

for (i=trenutni;i>0;i--) { /* za sve brojeve manje od trenutnog, tako da uvijek budu sortirani i ne gledmao istu kombinaciju vise puta */
a[x-1]=i;
rek(i-1, x-1, k);
}
}



int main() {

int n, k;
scanf("%d %d", &n, &k);

rek(n, k, k);

return 0;
}


[/code:1]

Kod se, dakako, moze jos optimirati, ali nisam htio da ne zbunjujem ljude ;). Dakle, ideja je u iducem koraku rekurzije smanjiti broj elemenata koje trebamo iskoristiti, i ujedno uzimati elemente koji su PRIJE trenutnog, tako da ne gledamo isti podskup vise puta.

Naravno, moglo se raditi tako da se gledaju brojevi POSLIJE trenutnog ili da se broj elemenata povecava. Osim toga, u rekurziji nije trebao biti ispis, nego je to mogla biti zasebna funkcija. I, naravno, nije moralo biti globalno polje (nego pointer, bla bla), ali ovako je dosta jednostavnije i brze;).
Kod:
#include <stdio.h>

int a[50]={0};

void rek (int trenutni, int x, int k) {
   int i;
   if (x<1) { /* ispis, zato moramo imati dodatnu varijablu k */
      for (i=0;i<k;i++)
         printf("%d ", a[i]);
      printf("\n");
      return;
   }

   if (trenutni < x) return; /* ako je ostalo manje brojeva nego sto nam treba, prekinimo */

   for (i=trenutni;i>0;i--) { /* za sve brojeve manje od trenutnog, tako da uvijek budu sortirani i ne gledmao istu kombinaciju vise puta */
      a[x-1]=i;
      rek(i-1, x-1, k);
   }
}



int main() {

   int n, k;
   scanf("%d %d", &n, &k);

   rek(n, k, k);

   return 0;
}




Kod se, dakako, moze jos optimirati, ali nisam htio da ne zbunjujem ljude ;). Dakle, ideja je u iducem koraku rekurzije smanjiti broj elemenata koje trebamo iskoristiti, i ujedno uzimati elemente koji su PRIJE trenutnog, tako da ne gledamo isti podskup vise puta.

Naravno, moglo se raditi tako da se gledaju brojevi POSLIJE trenutnog ili da se broj elemenata povecava. Osim toga, u rekurziji nije trebao biti ispis, nego je to mogla biti zasebna funkcija. I, naravno, nije moralo biti globalno polje (nego pointer, bla bla), ali ovako je dosta jednostavnije i brze;).



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Gost






PostPostano: 1:24 čet, 15. 12. 2005    Naslov: Citirajte i odgovorite

Hvala puno na svim uputa, a posebno na gornjem kodu. Ideja sa petljom od 1 do 2^n, pa onda u binarni je odlična iako je složenost velika, tim više što onih mojih n petlji je teško(nemoguće) isprogramirati ako ne znam koliki je n, dok ovdje to mogu. Zahvaljujem još jednom svima
Hvala puno na svim uputa, a posebno na gornjem kodu. Ideja sa petljom od 1 do 2^n, pa onda u binarni je odlična iako je složenost velika, tim više što onih mojih n petlji je teško(nemoguće) isprogramirati ako ne znam koliki je n, dok ovdje to mogu. Zahvaljujem još jednom svima


[Vrh]
ahri
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
Sarma = la pohva - posuda
= 7 - 0

PostPostano: 1:45 čet, 15. 12. 2005    Naslov: Citirajte i odgovorite

2^N je jako sporo, jer doslovno za sve moguce skupove ispitujes imaju li tocno K elemenata. A bit algoritma (opcenito) nije da radi najsporije moguce;).

btw, "n" for petlji se napravi rekurzivno...

Pseudo:
[code:1]
void rek(int n, parametri) {
int i;
if(n==0) {/* sad smo upotrijebili N petlji */
/* ovdje ide sto trebamo raditi u tim petljama */
}
else { /*generiramo jos jednu petlju */
for(i=....)
rek(n-1, parametri);
}
}
[/code:1]
2^N je jako sporo, jer doslovno za sve moguce skupove ispitujes imaju li tocno K elemenata. A bit algoritma (opcenito) nije da radi najsporije moguce;).

btw, "n" for petlji se napravi rekurzivno...

Pseudo:
Kod:

void rek(int n, parametri) {
  int i;
  if(n==0) {/* sad smo upotrijebili N petlji */
     /* ovdje ide sto trebamo raditi u tim petljama */
  }
  else { /*generiramo jos jednu petlju */
    for(i=....)
      rek(n-1, parametri);
  }
}



_________________
[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji 1. godine, preddiplomski studij Matematika -> Programiranje 1 i 2 Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You cannot attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan