help :)

[•INSiDe123]

Sal...
Ma cheama andrei .. braila /17 ani /cls 10

Acum ma pregatesc pt oji .. si vreau sa invat backtraking ( nusht daca am scris corect ) si generare de sublultimi .
Anu' trecut am ratat calificarea pt ca nu stiam astea..

Am cautat prob rezolvate dar nu am inteles prea bn limbaju..
Plz .. daca aveti vreo aplicatie cu ce am eu nev , in C++ ( de preferat in care sa folositi iostream sau fstream ) .. sau un link ceva ..

MS

[•alexandru92]

Salut si eu is a 10 . Back e o metoda  destul de greu de inteles, la inceput . Acuma trebuie sa intelegi se foloseste cand alta metoda de rezolvare nu exista.
Uite pt generare de multimii sper sa inetlegi

Cod:

#include<iostream.h>
#include<conio.h>
int  n,v[10000];
void  subm(int);  //programul pt backtraking, l-am facut recursiv 
int main()
  {clrscr();
     cout<<"n="; cin>>n;
     subm(1);  //apelez  ca sa pun primul elemnt in vector ;)
     getche();
  } 
void  out(int k)  //program de afisare
     {
         for(int i=1;i<=k;++i)  cout<<v[i]<<" ";
         cout<<endl;
      }
void subm(int k)  //acum incepe  "problema" 
    {
         for(int i=v[k-1]+1;i<=n;++i)  //cum toate elementele intr-o submultime trebuie sa fie in ordine crescatoare, logic ca urmatorul element
//este de la anterior +1 , nu?
            { v[k]=i;  //il pun in vector
               out(k);  //afisez submultimea astfel creata 
               subm(k+1);  //si urc o pozitie
            }
//Acest lucru se repeta pana cand conditia de oprire, evidenta i<=n, nu mai poate fi indeplinita, atunci se revine cu un pas inapoi, datorita  
//recursivitatii, si daca se poate se  pune un alt element pe pozitia respectiva si se urca iaras. Acest lucru se intampla pana cand stiva e goala :)

   }

C-am asta e programul
Ca sa intelegi mai bine fa  un debug   pt n=3, sau  un numar. Intelegi mai bine asa
Poti descrie problema de anul trecut la care ai picat din  cauza back-ului?

[•Mishu91]

In arhiva educationala se gasesc problemele Generare de permutari si Combinari.
Acolo gasesti sursele oficiale si linkuri catre alte site-uri unde gasesti informatii foarte utile

[•toni2007]

Pai presupun ca problema de la judeteana, pluricex . Era singura care se facea cu back.

[•alexandru92]

Pai presupun ca problema de la judeteana, pluricex . Era singura care se facea cu back.

Nu, nu se face cu back. Am incercat eu.... si pt multe teste depaseste timpul de executie.  In rezolvarea oficial propuneau un fel de algoritm succesor

[•Mishu91]

Cu back se face... generarea combinarilor

[•gabitzish1]

Salut si eu is a 10 . Back e o metoda  destul de greu de inteles, la inceput . Acuma trebuie sa intelegi se foloseste cand alta metoda de rezolvare nu exista.

Se mai foloseste si pentru a testa corectitudinea unei alte solutii, sau pentru a prinde cateva puncte cand nu reusesti sa rezolvi problema altfel, mai eficient.

[•alexandru92]

ok.problema pluricex am testat-o ieri  cu back si mi-a dat 40pct.din cauza....ca  TIME LIMIT EXCEEDED, acuma acelasi program .........am luat 100, mi se pare doar mie ciudat.........?..plus daca pun if(!a) return 0;  i-au 50 pct daca pun if(a==0) return 0;       ... i-au 100pct expresiile nu sunt echivalente ?
a.......am uitat   am folosit evaluatorul de la oji 2008 , sa nu se confunde cu cel de pe sit .

[•toni2007]

Nu stii sa implementezi . S-a luat 100 cu back anul trecut, toate persoanele care le-am intrebat cum au facut de 100 au raspuns ca au facut cu back. Vezi sa nu bagi int in loc de long si sa-ti cicleze pe unele teste.

[•alexandru92]

Daca nu stiu sa implementez  atunci de ce am luta  100pct la a doua evaluare?........si pe infoarena, desi aici trebuia sa mai optimizez putin ..in clasa  a IX nici eu nu stiam back.....si mi se  pare o prostie ce au facut, dar asta e offtopic

[•toni2007]

Eu ziceam de borland, desi si pe infoarena, cand am scris postul nu luasei 100 daca nu ma insel. Mare atentie la "long" in loc de "int", nu tot ce merge pe infoarena va merge si in borland sau invers.

[•INSiDe123]

ms mult..

back l-am inteles cam 80% ... si generare submultimi cam la fel...

[•alexandru92]

daca l-ai inteles  80%......ce  neclaritati  ai?... poti sa intrebi 

[•INSiDe123]

cand am zis 80 % ma refeream la faptu ca am inteles cum functioneaza metodele.. insa nu le stapanesc pe deplin..

ms inca odata

[•INSiDe123]

mai am o intrebare.. o postez tot aici

trebuie sa aflu cate combinatii de x pe y pozitii exista ..
exemplu : x=2 y=5 avem :

x x _ _ _
x _ x _ _
x _ _ x _
x _ _ _ x
_ x x _ _
_ x _ x _
_ x _ _ x
_ _ x x _
_ _ x _ x
_ _ _ x x  .. deci in total 10 posibilitati... si am nevoie de o formula.. sau ceva..

am facut cateva exemple si am obs o anumita regula (ceva cu simetrie fata de y/2 ) .. insa nu am putut sa generalizez ..

[•andrei-alpha]

Adica in cate moduri poti alege (x+1) numere care dau suma y-x.
Asta poti sa faci tot cu back.
Faci backul ca si la combinari numai ca la fiecare moment alegi un numarr intre 0 si suma ramasa.

De exemplu daca ai x=2 si y=5
si numerele : 2,1,0 asta insemana ca va fi _ _ x _ x.

Sper ca ai inteles. 

[•INSiDe123]

ms de sugestie.. dar intre timp am reusit sa fac o functie care calculeaza ce doream ... cred ca e mai rapida decat backul

Cod:

int comb (int a,int b)
{if(b==1) return a;
 if(b==a) return 1;
 if(b>a)  return 0;
 int x=comb(a-1,b)+comb(a-1,b-1);
 return x; }

[•toni2007]

Ce faci tu acolo e triunghiul lui pascal . Poti face mai rapid, cu programare dinamica:

Cod:

for (i = 1; i <= N; ++ i)
   for (j = 1; j <= i; ++ j)   C[i][j] = C[i - 1][j] + C[i - 1][j - 1];

(Initializezi la fel ca la functie matricea).

Cand vei avea nevoie de Combinari de N luate cate K, iei C[N][K] din matrice.

Tot asa poti face cu memoizare:

Cod:

int memo(int N, int K) {
   if (cache[N][K] != -1)
       return cache[N][K];
   return cache[N][K] = memo(N - 1, K) + memo(N - 1, K - 1);
}

Aici trebuie initializata matricea cu -1 peste tot, in afara de acele initializari de la prima.

[•devilkind]

asta faci daca ai nevoie de mai multe combinari. Dar daca te intereseaza doar combinari de N luate cate K exista formula:

C = N! / (K! * (N - K)!)

(N! = N factorial = 1 * 2 * 3 ... * N)

[•INSiDe123]

ms la amundoi pt idei..

formula aceea o cautam eu

[•INSiDe123]

inca o intrebare

cum fac un back.. care genereaza combinatii de numere de la x la n ..  luate cate k , unde n<k

ex:
pt x=0,n=1,k=5

00000
10110
11100
etc

[•alexandru92]

Cod:

void back(int c)
    {
    if(c==k+1) out(c);
      else for(int i=x;i<=n;++i)
                {v[c]=i;
                  back(c+1);
                }
    }

[later]  nu l-am incercat  pe pc .....deci de siguranta mai bine ii dai cateva teste

[•chera_lary]

Nu, nu se face cu back. Am incercat eu.... si pt multe teste depaseste timpul de executie.

Ba da! Merge cu back! Am rezolvat-o cu back si am luat 100 de puncte pe ea! Bine asta dupa ce am ajuns acasa!