Intercalar dues piles X51909

Implementeu una funció RECURSIVA que, donades dues piles com a paràmetre, retorna una pila que s’obté intercalant els valors de les dues piles rebudes. Més concretament, siguin [a₁,a₂,…,a_n] i [b₁,b₂,…,b_m] els elements de les dues piles escrits des del fons fins al top. La pila resultant es calcula així:

• En el cas en que n≥m, la pila resultant serà [a₁,b₁,a₂,b₂,…,a_m,b_m,a_m+1,a_m+2,…,a_n].
• En el cas en que n<m, la pila resultant serà [b₁,a₁,b₂,a₂,…,b_n,a_n,b_n+1,b_n+2,…,b_m].

// Pre:  Siguin [a1,a2,...,an] i [b1,b2,...,bm] els valors inicials de s1 i s2, respectivament.
// Post: En el cas n>=m, la pila retornada és [a1,b1,a2,b2,...,am,bm,a{m+1},a{m+2},...,an].
//       En el cas n<m, la pila retornada és [b1,a1,b2,a2,...,bn,an,b{n+1},b{n+2},...,bm].
stack<int> intercal(stack<int> s1, stack<int> s2);

Aquí tenim un exemple de comportament de la funció:

intercal([1 3 2 5],[2 7 6 1 3 9]) = [2 1 7 3 6 2 1 5 3 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.