Longitud blocs d'una pila (recursiva) S23287

Donada una pila d’enters, volem obtenir la longitud de cada bloc de valors consecutius iguals.

Un bloc és una seqüència màxima d’elements consecutius amb el mateix valor, considerant la pila de dalt a baix.

Has d’implementar una acció RECURSIVA que, donada una pila d’enters, construeixi una llista amb la longitud de cada bloc.

La capçalera de l’acció és la següent:

void longituds_blocs(const stack<int>& p, list<int>& l) {

Per exemple, donada la pila (on el darrer element és el cim de la pila)

p = [1, 3, 5, 2, 2, 3, 3, 3, 5, 5, 5]

la llista resultant després d’aplicar aquesta acció seria:

l = [3, 3, 2, 1, 1, 1]

Observació

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

Observacions

• Els subprogrames (accions o funcions) que creïs han de treballar les classes stack i list de la biblioteca STL. També pots usar la classe set i la classe map en cas que ho creguis necessari.

• Has de trobar una solució RECURSIVA i eficient del problema. En particular, no hi hauria d’haver cap bucle en cap dels subprogrames que implementis.

• Si crees subprogrames auxiliars, afegeix-hi les corresponents Pre i Post.

• En les crides recursives, inclou tant la Hipòtesi d’inducció de cada crida recursiva com la funció de fita/decreixement.