Suma per sota de cada posició d'una pila saltant de dos en dos X17446


Statement
 

pdf   zip   main.cc

html

Implementeu una funció RECURSIVA que, donada una pila d’enters [a1, a2, a3, a4, …, an−2, an−1, an], a on es representen els elements de la pila començant per l’esquerra amb el fons de la pila (a1 és l’element del fons, a2 és el següent des del fons, i així successivament), retorna una pila de la mateixa mida amb aquest contingut: [a1, a2, a3+a1, a4+a2, a5+a3+a1, a6+a4+a2, …, an−1+an−3+⋯, an+an−2+⋯]. En altres paraules, la nova pila té, a cada posició, la suma dels elements en la pila original que es troben des d’aquella posició cap al fons, i saltant de dos en dos. Aquesta és la capcelera:

// Pre: Sigui [a1, a2, a3, a4, ... a{n-2}, a{n-1}, an] el valor inicial rebut en el paràmetre s.
// Post: Retorna la pila [a1, a2, a3+a1, a4+a2, a5+a3+a1, a6+a4+a2, ..., a{n-1}+a{n-3}+..., an+a{n-2}+...]
stack<int> SumBelowLeap2(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:

SumBelowLeap2([5,4,1,8,9,7]) = [5,4,6,12,15,19]

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. Podeu crear funcions auxiliars per tal de millorar l’eficiència. 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 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 + justificació: 8 punts.
  • solució ràpida: 8 punts.
  • solució ràpida + justificació: 10 punts.
Sample session 
SumBelowLeap2([10]) = [10]
SumBelowLeap2([]) = []
SumBelowLeap2([1,4,0,6,3,1,8]) = [1,4,1,10,4,11,12]
SumBelowLeap2([5,3,7,4]) = [5,3,12,7]
SumBelowLeap2([10,2,0,10,8,5]) = [10,2,10,12,18,17]
SumBelowLeap2([4,6,0,10,3,10]) = [4,6,4,16,7,26]
SumBelowLeap2([7,10,3,7,9]) = [7,10,10,17,19]
SumBelowLeap2([8]) = [8]
SumBelowLeap2([10,7,10,4]) = [10,7,20,11]
SumBelowLeap2([0,10]) = [0,10]
Information
Author
PRO1
Language
Catalan
Official solutions
Unknown. This problem is being checked.
User solutions
C++