Suma de parells i senars en una pila X39544

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

P = [a₁, a₂, a₃, a₄, …, 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₁ és l’element del fons, a₂ é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₁, a₂, …, 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).

• PRE P és una pila d’enters.
• POST 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₁, a₂, …, 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.