Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Răspuns: 017 Combinari  (Citit de 9023 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
chavez
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« : Mai 25, 2008, 09:33:04 »

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 Very Happy. 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
Memorat
chera_lary
De-al casei
***

Karma: -2
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #1 : August 19, 2008, 12:16:13 »

Uita-te putin peste exemplul meu:
Cod:
#include <iostream.h>
#include <conio.h>
int comb[100][100];
int combinare[100];
int n,k;

int factorial(int nr){
if(nr>1)
  return nr*factorial(nr-1);
}

void main(){
    clrscr();
    int nrComb;
    nrComb=factorial(n)/factorial(k)*factorial(n-k);
    int ok=1;
    for(int i=1;i<=nrComb;++i)
       for(int j=1;j<=k;++j)
          for(int l=1;l<=k;++l){
             if(comb[i][j]!=combinare[l])
                ok=0;
             cout<<"Nr de ordine al combinarii este:"<<i<<endl;
             break;
          }
    getch();
}

Succes! Very Happy
Memorat
chavez
Strain


Karma: 2
Deconectat Deconectat

Mesaje: 2



Vezi Profilul
« Răspunde #2 : Septembrie 21, 2008, 11:46:16 »

Uita-te putin peste exemplul meu:
Cod:
#include <iostream.h>
#include <conio.h>
int comb[100][100];
int combinare[100];
int n,k;

int factorial(int nr){
if(nr>1)
  return nr*factorial(nr-1);
}

void main(){
    clrscr();
    int nrComb;
    nrComb=factorial(n)/factorial(k)*factorial(n-k);
    int ok=1;
    for(int i=1;i<=nrComb;++i)
       for(int j=1;j<=k;++j)
          for(int l=1;l<=k;++l){
             if(comb[i][j]!=combinare[l])
                ok=0;
             cout<<"Nr de ordine al combinarii este:"<<i<<endl;
             break;
          }
    getch();
}

Succes! Very Happy

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 Smile
Memorat
pauldb
Echipa infoarena
Nu mai tace
*****

Karma: 819
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #3 : Septembrie 21, 2008, 12:44:47 »

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.
« Ultima modificare: Septembrie 21, 2008, 13:35:27 de către Paul-Dan Baltescu » Memorat

Am zis Mr. Green
filipb
Echipa infoarena
Vorbaret
*****

Karma: 231
Deconectat Deconectat

Mesaje: 929



Vezi Profilul
« Răspunde #4 : Septembrie 22, 2008, 12:13:50 »

Te gandesti cate combinari sunt inainte de combinarea ta.

Uite o sursa edificatoare:

Cod:
#include <stdio.h>

int N, K, v[128];
long long Comb[128][128], cnt;

int main(void)
{
    int i, j;
   
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    scanf("%d %d", &N, &K);
    for (i = 1; i <= K; ++i)
        scanf("%d", &v[i]);

    for (Comb[1][1] = Comb[1][0] = 1, i = 2; i <= N; ++i)
        for (j = 1, Comb[i][0] = 1; j <= i && j <= K; ++j)
            Comb[i][j] = Comb[i-1][j-1] + Comb[i-1][j];

    for (i = 1; i <= K; ++i)
        for (j = v[i-1]+1; j < v[i]; ++j)
            cnt += Comb[N-j][K-i];

    printf("%lld\n", cnt+1);

    return 0;
}

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.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines