Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 64

Пусть S будет стеком размером n ≥ 1. Начиная с пустого стека, предположим, что мы последовательно помещаем первые n натуральных чисел, а затем выполняем n всплывающих операций. Предположим, что операции 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

Ответ: (с)
Пояснение: Требуется фон — Математика стека и основы

Пусть Tn будет отрезком времени n-го элемента стека. Давайте сначала выясним сумму Tn при n = 1 к 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))

Используя 2 тождества

  • Сумма из n натуральных чисел = (n * (n + 1)) / 2 для первого суммирования
  • Sn = (n / 2) (a + l) Сумма рядов AP с первым термином a и последним для второго суммирования l

Выше сумма есть,

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

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

Следовательно, Среднее = Сумма / n = n (X + Y) -X. Следовательно, вариант (с)

Это объяснение было внесено Пранджулом Ахуджей.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 64

0.00 (0%) 0 votes