Agafar elements del cim d'un altre Stack mantenint l'ordre X71502


Statement
 

pdf   zip   tar

thehtml

En aquest exercici estendrem la classe Stack afegint un nou mètode anomenat take. Aquest mètode té, com a paràmetres, un altre Stack, i un natural k, i la seva crida té com a efecte que movem els k elements del top de l’altre Stack al top del paràmetre implícit, i en el mateix ordre.

Més específicament, suposem que un Stack t té contingut [a1,a2,…,an] (on els elements els representem en ordre des del fons fins el top, i en particular an és l’element del top), i que un altre Stack s té contingut [b1,b2,…,bm]. Llavors, una crida t.take(s, k) té com a efecte que t passi a contenir [a1,…,an,bm−k+1,…,bm] i s passi a contenir [b1,…,bm−k].

En el cas particular que k sigui més gran que m, llavors es mouen tots els elements de s a t. És a dir, t passa a contenir [a1,…,an,b1,…,bm], i s passa a contenir [].

D’entre els fitxers que s’adjunten en aquest exercici, trobareu stack.hh, a on hi ha una implementació de la classe genèrica Stack. Haureu de buscar dins stack.hh les següents línies:

  // Pre:  Sigui [a1,...,an] el contingut del paràmetre implícit (des del fons fins al cim).
  //       Sigui [b1,...,bm] el contingut de s.
  //       k>=0
  // Post: En el cas en que k>=m, aquest és el resultat:
  //          [a1,...,an,b1,...,bm] és el contingut del paràmetre implícit.
  //          [] és el contingut de s.
  //       En canvi, en el cas k<m, aquest és el resultat:
  //          [a1,...,an,b{m-k+1},...,bm] és el contingut del paràmetre implícit.
  //          [b1,...,b{m-k}] és el contingut de s.
  // Descomenteu les següents dues linies i implementeu el mètode:
  // void take(Stack<T> &s, int k) {
  // ...
  // }

Descomenteu les linies que s’indiquen i implementeu el mètode.

D’entre els fitxers que s’adjunten a l’exercici també hi ha main.cc (programa principal), i el podeu compilar directament, doncs inclou stack.hh. Només cal que pugeu stack.hh al jutge.

Observació: En aquest exercici es prefereix una solució basada en manegar punters abans que una solució basada en cridar a mètodes primitius de la pròpia classe. De fet, manegar punters serà més ràpid, i fer-ho d’una altra forma possiblement provocarà que no supereu els jocs de proves privats.

Entrada

L’entrada del programa comença amb una declaració d’unes quantes piles d’strings (s0, s1, ...), i després té una seqüència de comandes sobre les piles declarades. Com que ja us oferim el main.cc, no cal que us preocupeu d’implementar la lectura d’aquestes entrades. Només cal que implementeu la extensió de la classe pila abans esmentada.

Se suposa que la seqüència d’entrada serà correcta (sense pop ni top sobre pila buida), ni farà coses extranyes com cridar a take de la pròpia pila (així que no cal que tracteu aquest cas).

El programa principal que us oferim ja s’encarrega de llegir aquestes entrades i fer les crides als corresponents mètodes de la classe pila. Només cal que feu els canvis abans esmentats.

Sortida

Per a cada comanda d’escriptura sobre la sortida s’escriurà el resultat corresponent. El main.cc que us oferim ja fa això. Només cal que implementeu la extensió de la classe cua abans esmentada.

Observació

Avaluació sobre 10 punts: (Afegiu comentaris si el vostre codi no és prou clar)

  • Solució lenta: 5 punts.
  • solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics. Per exemple, una solució que superi tots els jocs de proves però que manegui incorrectament la memòria serà invalidada i tindrà nota 0.

Una solució basada en cridar a mètodes primitius de la pròpia classe possiblement serà lenta i, en cas que no ho sigui, pot tenir una certa penalització en la nota.

Public test cases

  • Input

    Stack<int> s0 , s1 ;
s0 .push( "a" );
s0 .push( "b" );
s0 .push( "c" );
s0 .push( "d" );
s1 .push( "e" );
s1 .push( "f" );
s1 .push( "g" );
s1 .push( "h" );
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 2 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s1 .take( s0 , 3 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 1 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s1 .take( s0 , 0 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 4 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;
s1 .take( s0 , 9 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s1 .top()<<endl;
s0 .take( s1 , 1000000000 )<<endl;
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s0 .size()<<endl;
cout<< s1 .size()<<endl;
cout<< s0 .top()<<endl;

    Output

    a b c d
e f g h
4
4
d
h
a b c d g h
e f
6
2
h
f
a b c
e f d g h
3
5
c
h
a b c h
e f d g
4
4
h
g
a b c h
e f d g
4
4
h
g
a b c h e f d g

8
0
g

a b c h e f d g
0
8
g
a b c h e f d g

8
0
g

  • Input

    Stack<int> s0 , s1 , s2 ;
cout<< s1 <<endl;
s1 .take( s0 , 1 );
s0 .take( s2 , 1 );
cout<< s1 <<endl;
s1 .take( s2 , 0 );
s1 .push( "adb" );
cout<< s1 .top()<<endl;
s1 .push( "ccc" );
s0 .push( "ad" );
s0 .take( s2 , 0 );
cout<< s2 .size()<<endl;
s2 .push( "dcb" );
s1 .take( s2 , 0 );
s2 .pop();
s1 .push( "bb" );
s0 .push( "bcb" );
s2 .take( s0 , 0 );
cout<< s0 <<endl;
s0 .pop();
s2 .push( "c" );
cout<< s0 .top()<<endl;
s2 .take( s0 , 0 );
s2 .push( "daa" );
s0 .pop();
s1 .push( "cc" );
cout<< s0 .size()<<endl;
s2 .push( "db" );
s2 .push( "a" );
s2 .push( "ac" );
s0 .push( "ada" );
s0 .push( "bd" );
s2 .take( s1 , 5 );
cout<< s1 <<endl;
cout<< s0 <<endl;
s2 .push( "dd" );
s1 .take( s0 , 2 );
s1 .push( "aba" );
cout<< s2 <<endl;
s2 .push( "b" );
s2 .push( "aa" );
s2 .push( "ac" );
cout<< s0 <<endl;
s2 .pop();
s2 .take( s1 , 3 );
s1 .push( "bad" );
s0 .push( "cd" );
s1 .push( "b" );
s2 .push( "d" );
s0 .take( s1 , 4 );
cout<< s1 .size()<<endl;
s2 .push( "aac" );
cout<< s0 .size()<<endl;
cout<< s0 <<endl;
s0 .push( "dcd" );
s2 .push( "ba" );
s2 .push( "ccb" );
s0 .push( "bdd" );
cout<< s2 .top()<<endl;
s2 .pop();
s2 .push( "c" );
cout<< s2 .size()<<endl;
cout<< s0 .size()<<endl;
s0 .push( "acc" );
cout<< s2 .top()<<endl;
cout<< s0 .size()<<endl;
s2 .take( s1 , 0 );
cout<< s0 <<endl;
s2 .push( "dca" );
s0 .push( "bcb" );
s1 .push( "d" );
s2 .push( "db" );
cout<< s0 <<endl;
cout<< s1 <<endl;
s2 .pop();
s0 .push( "aa" );
s0 .pop();
s0 .pop();
s1 .push( "d" );
cout<< s1 .size()<<endl;
s0 .take( s2 , 8 );
cout<< s0 <<endl;
cout<< s1 <<endl;
cout<< s2 <<endl;

    Output

    
adb
0
ad bcb
ad
0

ada bd
c daa db a ac adb ccc bb cc dd

0
3
cd bad b
ccb
19
5
c
6
cd bad b dcd bdd acc
cd bad b dcd bdd acc bcb
d
2
cd bad b dcd bdd acc ada bd aba d aac ba c dca
d d
c daa db a ac adb ccc bb cc dd b aa
    • Information
    Author
    PRO2
    Language
    Catalan
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++