Aprendre a programar 13 - L'examen de lab de PRO2

Ara ja hem fet les 3 primeres sessions, i se suposa que ja sabem més o menys modificar una classe. La sessió 4 és per practicar per l'examen de laboratori, que consistirà en modificar una classe que, en general, acostuma a ser Cjt_estudiants. Aquí, a diferència dels altres problemes, acostumen a donar-nos de manera que només haguem de fer dos o tres funcions. No té gaire diferència respecte les sessions anteriors, i, per tant, penso que no cal dedicar un article només a això. Així que he pensat que parlaré del meu examen de lab, que va ser completament diferent a la majoria. Si més tard veig necessari completar amb altres examens, els afegiré al final

Quan et canvien completament el format

Suposo que el lector, igual que jo, estudia els examens de la universitat com si fos l'autoescola. Es mira què entra, i es posa a fer examens per veure com ho porta. És molt típic, i conec molta gent que ho fa així. A algunes assignatures ja avisen que no és una bona manera, i que es pot patinar. I això és el que va passar el meu any (2015-2016 Q2). 

Sí, imagineu la sorpresa dels estudiants del torn 1, quan arriben i es troben que han d'implementar una cua. Sobretot pels que no tenen gaire clar què és una cua, ja que no entraven a aquest examen. 

Si algú vol l'examen, pot trobar-lo aquí, amb el PDF, els fitxers i una solució (que va treure un 10 a l'examen). Jo proposo que intenteu resoldre'l, després us podeu mirar les idees que dono per resoldre-ho, i finalment la meva solució

Primera idea:

Una primera idea seria la següent. 

Per fer el push, seria tan senzill com afegir l'element a v[t], i incrementar t i n.Evidentment, retoquem la suma i nest_amb_nota, si toca

Per fer el pop, simplement desplacem tots els elements al rang [1,t) una posició a l'esquerra. Decrementem t i n. De la mateixa manera, si cal, retoquem la suma i nest_amb_nota

Per escriure, simplement faríem un for i escriuríem cada estudiant

Aquesta solució és bastant intuïtiva. I, si no ens fixem gaire en l'invariant, doncs és el que se'ns passarà pel cap. 

El seu problema:

Aquesta solució té un problema, i és que cada pop que fem implica desplaçar tots els elements. A més, l'invariant ens diu que tenim un membre de la classe que es diu p, que indica l'inici de la cua, un que es diu t, que indica el final, i un que es diu n, que indica la mida. Amb la nostra solució, són inútils, ja que el primer sempre serà 0, i el final sempre serà n. 

Però la classe es torna més simple, podríeu dir. Sí, és cert, però es torna més lenta. Un pop implica desplaçar n-1 estudiants. Sí, en principi la mida màxima és 10, de manera que com a molt estarem desplaçant 9 estudiants. Però per què desplaçar 9, si ho podem fer bé i no desplaçar-ne cap? O, mirem d'una altra manera. Imaginem que necessitem una cua que pugui tenir fins a 1.000.000 d'estudiants. Seria divertit fer pop, no?

I tan malament està això?

Sí. Perquè us feu una idea, l'examen era 60% automàtica, i 40% manual. Hi va haver una quantitat desproporcionada de gent amb un 6, perquè tenien un 10 d'automàtica, i un 0 de manual. Semblava que només hi haguessin 3 notes (0, 6 i 10). Sobretot 6, després 0, i pocs 10. Però notes diferents, encara menys. 

Una bona solució?

Doncs una bona solució seria aprofitar tots els atributs de la classe. 

Fer un push és senzill, posem la variable a la posició t, incrementem n i recalculem t. Si l'estudiant té nota, ho retoquem una mica, i ja està

Fer el pop és similar. Si té nota, retoquem, i aleshores incrementem p i decrementem n. Si p ha arribat al màxim, ho posem a 0, i ale

Fer l'escriure és bastant trivial. Et recorres de p fins a t (no inclòs), i mostres els estudiants. Pots utilitzar la funció escriure, o fer-te el xulo com vaig fer jo, i fer-ho a mà (millor la primera)