| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
Gost
|
|
| [Vrh] |
|
Tonci
Forumaš(ica)
Pridružen/a: 31. 10. 2002. (13:46:40)
Postovi: (61)16
Spol: 
Lokacija: Split
|
 Postano: 15:14 sri, 14. 12. 2005 Naslov: |
    |
|
|
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] |
|
vsego
Site Admin
Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (3562)16
Spol: 
Lokacija: /sbin/init
|
| Postano: 15:31 sri, 14. 12. 2005 Naslov: |
|
|
|
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.  Treba u rekurziji pratiti koliko si "potrosio" jedinica i koliko nula. 
Na pocetku rekurzije provjeravas da li si potrosio sve jedinice.  Ako jesi, gotovo (as in ne ides dalje s rekurzijom). 
Zatim provjeris jesi li "potrosio" sve nule; ako jesi, svi preostali brojevi idu u podskup, pa si opet gotov.
Nemam ideju za brži algoritam... 
_________________ 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.  |
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
| Postano: 0:29 čet, 15. 12. 2005 Naslov: |
|
|
|
[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] |
|
Gost
|
|
| [Vrh] |
|
ahri
Forumaš(ica)
Pridružen/a: 19. 11. 2003. (23:16:07)
Postovi: (193)16
|
|
| [Vrh] |
|
|
