Titlul: Combinari cu o proprietate Scris de: Plesa Mihail Iulian din Octombrie 03, 2013, 18:03:11 Salut!
Am o multime data M cu cardinalul n iar in vectorul C generez pe rand combinarile de n luate cate t. Vreau sa calculez NUMARUL tuturor combinarilor care au urmatoarele proprietati: 1.C[1]-2<=2*k 2.C-C[i-1]<=2*k 3.2*n-C[t]<=2*k unde k este dat. Intrebarea mea este daca ppot calcula NUMARUL combinarilor FARA a le genera? Si in general, daca imi cere intr-o problema sa calculez numarul combinarilor cu o anumita proprietate pot sa "scap" de generarea lor? Multumesc :) Titlul: Răspuns: Combinari cu o proprietate Scris de: George Marcus din Octombrie 03, 2013, 20:58:07 E cam vaga intrebarea. Uneori da, alteori nu.
Uneori poti deduce o formula, alteori merge cu programare dinamica. In cazul asta, din cauza conditiei 2, suspectez ca exista o solutie cu programare dinamica. Titlul: Răspuns: Combinari cu o proprietate Scris de: Mihai Calancea din Octombrie 03, 2013, 21:33:14 Editeaza-ti indicii aia un pic ca nu inteleg nimic.
Titlul: Răspuns: Combinari cu o proprietate Scris de: Plesa Mihail Iulian din Octombrie 04, 2013, 08:53:43 Acesta este exemplul concret: am multimea {2, 4, 6, 8, 10, 12 ,14, 16, 18, 20}. Cardinalul multimii este de 10. In vectorul C generez pe rand toate combinarile de 10 luate cate 2 cu urmatoarele proprietati:
1. Cod: C[1]-2<=2*k Cod: C-C[i-1]<=2*k 3. Cod: 2*n-C[t]<=2*k Una dintre posibilitati este:4 12 alta este 6 12 etc. Intrebarea mea este daca pot gasi NUMARUL combninarilor fara sa le generez? :) |