Блог

Вопрос:

Пусть S — стек размером n > = 1. Начиная с пустого стека, предположим, что мы последовательно вводим первые n натуральных чисел, а затем выполняем n операций pop.

Предположим, что операции Push и Pop занимают по X секунд каждая, а между окончанием одной такой операции стека и началом следующей операции проходит Y секунд.

Для m> = 1 определите срок службы стека m как время, прошедшее с конца Push (m) до начала операции pop, которая удаляет m из S. Средний срок службы элемента этого стека составляет

 (A) n(X  Y)
(B) 3Y   2X
(C) n(X   Y)-X
(D) Y   2X
  

Вопрос взят по этой ссылке

Мой подход:

 For n elements Push takes X time, hence for m elements Push takes m/n*X    
For n elements Pop takes X time, hence for m elements Push takes m/n*X    
Interval Time is m/n*Y
Stack Life = End of Push(m) to start of Pop(m) = Interval Time = m/n*Y
Average Stack Life = (m/n*Y) / m = Y/n
  

Ни один из ответов не совпадает.
Пожалуйста, укажи мне правильный путь к достижению моей цели.

Вот мой подход:

 Stack lifetime of nth element -> Y
For (n-1)th -> 2X 2Y   stack lifetime of nth element = 2X   3Y
For (n-2)th -> 2X 2Y   stack lifetime of (n-1)th element = 4X   5Y
..
..
For 1st -> 2(n-1)X   (2n-1)Y
  

Sum of all life spans= (Σ 2(n-1)X) (Σ (2n-1)Y) для n = от 1 до n

Вычислите сумму путем приведенного выше суммирования от 1 до n, вы получите:

 Sum = n(n(X Y)-X)
Therefore Average = Sum/n = n(X Y)-X .  Hence Option (c)
  

Этот вопрос был задан здесь: http://geeksquiz.com/data-structures-stack-question-7 /

 Here is mine: 
PUSH Operations:
1. After Push(m) i.e., from Push(m 1) till Push(n) --> there are (n-m) Push operations(ops) => (n-m)X ops

2. After Push(m) to the Push(m 1) --> there is one Y ops ==> till Push(n) ==> (n-m)Y ops

--> Time taken to finish Push(n) after Push(m) ==> (n-m)(X Y)

POP Operations:
1. After Push(n) to the Pop(n) --> there is one Y ops ==> till Pop(m) ==> (n-m 1)Y ops (this is one extra Y after Pop(m 1) and reach Pop(m))

2. From Push(n) till Push(m 1) --> there are (n-m) Push operations(ops) => (n-m)X ops

--> Time taken to finish Pop(m 1) from Push(n) ==> (n-m)(X Y) Y

Overall Time for any arbitrary m, T(m) ==> 2(n-m)(X Y)   Y

To obtain the average: Sum(T(m)), for all m: 1->n
==> Sum{ 2(n-m)(X Y)   Y } over m: 1->n
==> 2(X Y){(n-1)   (n-2)   ....   0 }  (Y   Y ... n-times)
==> 2(n(n-1)/2)(X Y)   nY = n(n-1)(X Y)   nY
Average: Above sum / n
==> (n-1)(X Y)   Y = n(X Y)-X