infoarena

Salutare. Avand in vedere ca azi am cautat si gasit siteu asta pentru ca n-am timp sa gasesc solutia la urmatoarea problema va cer voua ajutorul. Oricum deja am "pierdut" 2 ore pe site amintindu-mi de old times. Am avut onoarea sa ii cunosc Costan Victor si Ghinea Dan prin clasa XI, pe Victor la Grigore Moisil cand ne pregateam sambata pt Olimp.

Pbma mea nerezolvata din lipsa de timp si ideei(rog moderatorii sa nu ma sanctioneze daca incalc vreo regula a forumului fiind primul post):

Spre exemplu daca avem combinari de 8 luate cate 6 generate sub forma de mai jos as vrea in functie de numere care alcatuiesc respectiva solutie sa se obtina un numar de ordine al solutiei

     1     2     3     4     5     6  numar de ordine   1
     1     2     3     4     5     7  numar de ordine   2
     1     2     3     4     5     8  numar de ordine   3
     1     2     3     4     6     7  numar de ordine   4
     1     2     3     4     6     8  numar de ordine   5
     1     2     3     4     7     8  numar de ordine   6
     1     2     3     5     6     7  numar de ordine   7
     1     2     3     5     6     8  numar de ordine   8
     1     2     3     5     7     8  numar de ordine   9
     1     2     3     6     7     8  numar de ordine  10
     1     2     4     5     6     7  numar de ordine  11
     1     2     4     5     6     8  numar de ordine  12
     1     2     4     5     7     8  numar de ordine  13
     1     2     4     6     7     8  numar de ordine  14
     1     2     5     6     7     8  numar de ordine  15
     1     3     4     5     6     7  numar de ordine  16
     1     3     4     5     6     8  numar de ordine  17
     1     3     4     5     7     8  numar de ordine  18
     1     3     4     6     7     8  numar de ordine  19
     1     3     5     6     7     8  numar de ordine  20
     1     4     5     6     7     8  numar de ordine  21
     2     3     4     5     6     7  numar de ordine  22
     2     3     4     5     6     8  numar de ordine  23
     2     3     4     5     7     8  numar de ordine  24
     2     3     4     6     7     8  numar de ordine  25
     2     3     5     6     7     8  numar de ordine  26
     2     4     5     6     7     8  numar de ordine  27
     3     4     5     6     7     8  numar de ordine  28

apoi dandu-se o combinatie oarecare in functie de numerele ce o compun sa pot afla unde se afla in lista de combinari. Poate parea usor pentru unii dintre voi dar aseara cam intr-o ora nu i-am dat de cap si nu prea am timp, prea multe proiecte pe cap :D. Daca cineva stie/gaseste o metoda il rog sa mi-o comunice si mie si ii raman recunoscator. Deasemenea daca poate fi ceva general spre exemplu daca am ceva de genu combinari de 20 luate cate 10 etc. Ms mult

Uita-te putin peste exemplul meu:

Succes! :D

hmm nu merge. in primul rand nici combinarile nu le-ai generat corect ai uitat niste ( ) la
nrComb=factorial(n)/factorial(k)*factorial(n-k); apoi unde initializezi
int comb[100][100];
int combinare[100]; ?
ms pt incercare.

acum daca cineva ma poate ajuta, vad ca a trecut destul de mult de cand am postat, nu am nevoie de programul propriu-zis, desi e binevenit ca sa pot verifica repede, am nevoie de o functie matematica pe exemplu de mai sus daca ii dau spre exemplu: 1     3     5     6     7     8  sa imi returneze 20. Nu stiu daca are foarte mare legatura cu info, e mai mult matematic, dar m-am gandit ca pe aici ar tb sa fie destui oameni destepti care poate stiu deja raspunsul sau pot sa gaseasca repede o solutie. Ms :)

Problema ta poate fi rezolvata in complexitate O(N^2) cu ajutorul programarii dinamice.

Initial calculezi c[ i ][ j ] = cate combinari exista de lungime k-i+1 cu ultimul element j (combinarile le numeri dinspre coada spre cap). Recurenta este c[ i ][ j ] = suma din (c[ i+1 ][ x ], j < x <= n) = c[ i ][ j+1] + c[i + 1][j + 1].
Acum, pentru a afla ordinul combinarii date, iei fiecare pozitie i si numeri cate combinari cu prefixul i-1 identic exista mai mici decat combinarea data. Adica, pentru un i, aduni la solutia c[ i ][ k ], 1 <= k < a[ i ], unde in vectorul a se afla combinarea data.

Te gandesti cate combinari sunt inainte de combinarea ta.

Uite o sursa edificatoare:


Programul iti afiseaza din toate combinarile de N luate cate K nr. de ordine al vectorului cu K elemente care il dai tu.
Sper ca se intelege din sursa, daca nu posteaza ce nelamuriri ai.