infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva educationala => Subiect creat de: Plesa Mihail Iulian din Octombrie 03, 2013, 18:03:11



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
2.
Cod:
C-C[i-1]<=2*k 

3.
Cod:
2*n-C[t]<=2*k
n este cardinalul multimii si k un numar dat...in cazul nostrum k=4 si n=10.

Una dintre posibilitati este:4 12 alta este 6 12 etc. Intrebarea mea este daca pot gasi NUMARUL combninarilor fara sa le generez? :)