Cua màxima X67211

Implementeu una funció ITERATIVA que, donades dues cues d’enters positius, obté una nova cua que conté, per a cada posició, el màxim dels valors de les cues de partida en les mateixes corresponents posicions. En cas que una de les cues no tingui un valor definit en una posició, s’agafa el valor de l’altra cua. Aquesta és la capcelera:

// Pre: Rep dues cues d'enters positius q1 i q2.
// Post: Retorna una cua, on al seu front hi ha el màxim dels fronts de q1,q2, després,
// en segon lloc el màxim dels segons llocs de q1,q2, i així successivament.
// Quan una de les dues cues no té valors definits en alguna posició, la cua resultant hi té
// el valor de l'altra cua en aquella posició.

queue<int> maximumQueue(queue<int> q1,queue<int> q2);

Aquí tenim un exemple de comportament de la funció, a on es mostren els elements de les cues des del primer afegit a l’esquerra de tot, a l’últim afegit a la dreta de tot:

1 4 6 4 2
5 8 7 1 1 3 6 5 6
=>
5 8 7 4 2 3 6 5 6

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 cues. Heu de trobar una solució ITERATIVA i eficient del problema. Si creeu funcions auxiliars, afegiu-hi les seves PRE/POST. En els bucles, incloeu l’invariant o una explicació del que s’aconsegueix després de l’i-èssim pas, i també la funció de fita/decreixement o una justificació de perquè el bucle acaba.

Avaluació sobre 10 punts:

• Solució lenta: 7 punts.
• Solució lenta + justificació: 8 punts.
• solució ràpida: 9 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 1 punt i consisteix en definir correctament les PRE/POST de les funcions auxiliars que afegiu i en definir correctament els invariants i funcions de fita dels bucles que implementeu.