(Stack) Reemplaça 0s per suma per sota a posició parell X88008

Implementeu una funció RECURSIVA que, donada una pila de naturals, retorna una nova pila que és idèntica a la inicial, excepte que cada 0 s’ha reemplaçat per la suma dels elements a posició parell que apareixen per sota d’aquest 0 (en la pila original).

Sobreentenem que l’element del fons de la pila està a posició 0, el següent des del fons a posició 1, el següent des del fons a posició 2, i així successivament. Aquesta és la capcelera:

// Pre:  Sigui S el valor inicial de la pila s que es rep com a paràmetre.
//       Els valors guardats a S son majors o iguals a 0.
// Post: Sigui S' la pila retornada. S i S' tenen el mateix nombre d'elements.
//       A més a més, per a cada posició p de S', si S té un valor x diferent de 0 a posició p,
//       llavors S' també té x a posició p.
//       En canvi, si S té valor 0 a posició p, llavors el valor de S' a posició p és
//       la suma de tots els valors de S a posició parell per sota de p.
stack<int> replace0sWithBelowSumPosEven(stack<int> s);

Aquí tenim un exemple de comportament de la funció, a on les piles es representen tenint l’element del fons a l’esquerra i l’element del top a la dreta:

replace0sWithBelowSumPosEven([1 3 0 0 1 3 2 0 5 0 9]) = [1 3 1 1 1 3 2 4 5 9 9]

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. En particular, no hi hauria d’haver cap bucle en cap de les funcions que implementeu. Si creeu funcions auxiliars, afegiu-hi les seves PRE/POST. En 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 o una justificació de perquè la funció recursiva acaba.

Una solució directa superarà els jocs de proves públics i us permetrà obtenir una nota raonable. Però molt possiblement serà lenta, i necessitareu crear alguna funció recursiva auxiliar per a produïr una solució més eficient capaç de superar tots els jocs de proves.

Avaluació sobre 10 punts:

• Solució lenta: 6 punts.
• Solució lenta + justificació: 8 punts.
• solució ràpida: 8 punts.
• solució ràpida + justificació: 10 punts.

Entenem com a solució lenta una que és correcta i capaç de superar els jocs de proves públics. Entenem com a solució ràpida una que és correcta i capaç de superar els jocs de proves públics i privats. La justificació val 2 punts i consisteix en definir correctament les PRE/POST de les funcions auxiliars que afegiu i en definir correctament les hipòtesis d’inducció i funcions de fita.