infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Andrei din Martie 04, 2009, 17:50:47



Titlul: help :)
Scris de: Andrei din Martie 04, 2009, 17:50:47
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


Titlul: Răspuns: help :)
Scris de: alexandru din Martie 04, 2009, 17:56:09
Salut si eu is a 10 :). Back e o metoda  destul de greu de inteles, la inceput :D. 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?


Titlul: Răspuns: help :)
Scris de: Andrei Misarca din Martie 04, 2009, 18:13:43
In arhiva educationala se gasesc problemele Generare de permutari (http://infoarena.ro/problema/permutari) si Combinari (http://infoarena.ro/problema/combinari).
Acolo gasesti sursele oficiale si linkuri catre alte site-uri unde gasesti informatii foarte utile :)


Titlul: Răspuns: help :)
Scris de: Pripoae Teodor Anton din Martie 04, 2009, 18:14:32
Pai presupun ca problema de la judeteana,  pluricex  (http://infoarena.ro/problema/pluricex). Era singura care se facea cu back.


Titlul: Răspuns: help :)
Scris de: alexandru din Martie 04, 2009, 18:18:33
Citat
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 ;)


Titlul: Răspuns: help :)
Scris de: Andrei Misarca din Martie 04, 2009, 18:20:23
Cu back se face... generarea combinarilor ;)


Titlul: Răspuns: help :)
Scris de: Gabriel Bitis din Martie 04, 2009, 19:05:26
Salut si eu is a 10 :). Back e o metoda  destul de greu de inteles, la inceput :D. 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. :)


Titlul: Răspuns: help :)
Scris de: alexandru din Martie 04, 2009, 19:26:35
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 :D, sa nu se confunde cu cel de pe sit :).


Titlul: Răspuns: help :)
Scris de: Pripoae Teodor Anton din Martie 04, 2009, 21:07:32
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.


Titlul: Răspuns: help :)
Scris de: alexandru din Martie 05, 2009, 08:05:53
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 :P ..in clasa  a IX nici eu nu stiam back.....si mi se  pare o prostie ce au facut, dar asta e offtopic :)


Titlul: Răspuns: help :)
Scris de: Pripoae Teodor Anton din Martie 05, 2009, 13:08:47
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.


Titlul: Răspuns: help :)
Scris de: Andrei din Martie 05, 2009, 19:00:03
ms mult..

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


Titlul: Răspuns: help :)
Scris de: alexandru din Martie 05, 2009, 19:51:51
daca l-ai inteles  80%......ce  neclaritati  ai?... poti sa intrebi  :D


Titlul: Răspuns: help :)
Scris de: Andrei din Martie 06, 2009, 18:29:48
cand am zis 80 % ma refeream la faptu ca am inteles cum functioneaza metodele.. insa nu le stapanesc pe deplin..

ms inca odata :)


Titlul: Răspuns: help :)
Scris de: Andrei din Martie 09, 2009, 10:35:44
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 ..


Titlul: Răspuns: help :)
Scris de: Andrei-Bogdan Antonescu din Martie 09, 2009, 10:51:30
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.  :)


Titlul: Răspuns: help :)
Scris de: Andrei din Martie 09, 2009, 11:38:19
ms de sugestie.. dar intre timp am reusit sa fac o functie care calculeaza ce doream :D ... 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; }



Titlul: Răspuns: help :)
Scris de: Pripoae Teodor Anton din Martie 09, 2009, 12:15:41
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.


Titlul: Răspuns: help :)
Scris de: Savin Tiberiu din Martie 09, 2009, 12:28:37
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)


Titlul: Răspuns: help :)
Scris de: Andrei din Martie 10, 2009, 12:30:01
ms la amundoi pt idei..

formula aceea o cautam eu :)


Titlul: Răspuns: help :)
Scris de: Andrei din Martie 13, 2009, 19:37:44
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



Titlul: Răspuns: help :)
Scris de: alexandru din Martie 13, 2009, 20:23:06
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 ;)


Titlul: Răspuns: help :)
Scris de: CHERA Laurentiu din Martie 13, 2009, 23:31:32
Citat
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! :D