PUERTA | PUERTA-CS-2003 | Pregunta 64

Sea S una pila de tamaño n ≥ 1. Comenzando con la pila vacía, supongamos que empujamos los primeros n números naturales en secuencia y luego realizamos n operaciones pop. Suponga que las operaciones Push y pop toman X segundos cada una, y que transcurren Y segundos entre el final de una de esas operaciones de pila y el comienzo de la siguiente operación. Para m ≥ 1, defina la vida útil de la pila de m como el tiempo transcurrido desde el final de Push(m) hasta el inicio de la operación pop que elimina m de S. La vida útil promedio de la pila de un elemento de esta pila es
( A) n (X + Y)
(B) 3Y + 2X
(C) n (X + Y) – X
(D) Y + 2X

Respuesta: (C)
Explicación: se requiere experiencia: pila y matemáticas básicas

Sea Tn el lapso de tiempo del n-ésimo elemento de la pila. Primero averigüemos la suma de Tn para n = 1 a n

Stack Lifetime of last element, Tn = Y (Since it is popped as soon 
                                        as it is pushed on the stack)

Stack Lifetime of last element, Tn-1 = Tn  + 2X + 2Y 
                                       (The time needed to push and then
                                        pop nth element plus two pauses Y each).
                        = 2X + 3Y 

Stack Lifetime of last element, Tn-2 = Tn-1  + 2X + 2Y (Using the Same reasoning above)
                        = 4X + 5Y
.
.
.
Stack Lifetime of 1st element = 2(n-1)X + (2n-1)Y    (Generalizing the pattern)

Sum of all the time spans of all the elements = (Σ 2(n-1)X) + (Σ (2n-1)Y) 
                                                                   for n = 1 to n

= 2X(1 + 2 + . . . + n-1) + Y(1 + 3 + 5 + . . . + (2n-1))

Usando 2 identidades

• Suma de n números naturales = (n*(n+1))/2 para la primera suma
• Sn = (n/2)(a+l) Suma de la serie AP con a como primer término y siendo l el último para la segunda suma

La suma anterior es,

= (2X(n-1)n)/2 + Y(n/2)*(1 + 2n-1)

= n(n(X+Y)-X)

Por lo tanto Promedio = Suma/n = n(X+Y)-X . Por lo tanto Opción (c)

Esta explicación ha sido aportada por Pranjul Ahuja.

Cuestionario de esta pregunta