Suma de parells i senars en una pila X39544

Implementeu una funció RECURSIVA que, donada una pila d’enters

P $= [a_1,\;a_2,\;a_3,\;a_4,\;\ldots,\;a_{n-2},\;a_{n-1},\;a_n]$

a on es representen els elements de la pila començant per l’esquerra amb el fons de la pila ($a_1$ és l’element del fons, $a_2$ és el següent des del fons, i així successivament), retorna una pila P' tal que si l’element $a_i$ de la pila P és senar, llavors a la posició $a_i$ de la pila P' hi haurà la suma de tots els senars que hi hagi a P a les posicions $[a_1, a_2, \dots, a_i]$. Si la posició és parell, serà igual però amb la suma dels parells.

El número zero s’assumeix que és parell, i els nombres negatius tenen la paritat del número positiu (és a dir, el $-5$ és senar, i el $-24$ és parell).

• P és una pila d’enters.

• Torna P' tal que si $a_i$ a la pila P és parell, a $a_i$ de la pila P' hi haurà la suma de tots els parells que hi ha a P a les posicions $[a_1, a_2, \dots, a_i]$. Si és senar, la suma dels senars.

stack<int> SumParellSenar(stack<int> s);

Aquí tenim un exemple d’entrada i sortida de la funció, a on es mostren els elements de les piles des del fons de la pila a l’esquerra fins al top de la pila a la dreta:

SumParellSenar([5, 4, 1, 8, 9, 7]) = [5, 4, 6, 12, 15, 22]

Observació

Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

La vostra funció i subfuncions que creeu han de treballar només amb piles. Heu de trobar una solució RECURSIVA i eficient del problema. Si fos el cas, podeu crear funcions auxiliars per tal de millorar l’eficiència.

A les crides recursives, incloeu la hipòtesi d’inducció, és a dir una explicació del que es cumpleix després de la crida, i també la funció de fita/decreixement.

Una implementació no eficient que superi honestament els jocs de proves públics us permetrà obtenir una nota raonable, però per a superar tots els jocs de proves i obtenir la màxima nota haureu de pensar en una manera de fer-ho eficient.

Avaluació sobre 10 punts:

• Solució lenta: 6 punts.

• Solució lenta + H.I. + fita: 8 punts.

• solució ràpida: 8 punts.

• solució ràpida + H.I. + fita: 10 punts.

Una solució iterativa a aquest problema tindrà un zero, independentment de si passa o no el jocs de proves.