大门|大门-CS-2003 |问题64

让我们做一个n大小的堆栈≥ 1.从空堆栈开始，假设我们按顺序推送前n个自然数，然后执行n个pop操作。假设Push和pop操作各花费X秒，在一个这样的堆栈操作结束和下一个操作开始之间花费Y秒。为了我≥ 1.将堆栈寿命m定义为从推送结束（m）到从S中移除m的pop操作开始所经过的时间。此堆栈元素的平均堆栈寿命为 （A） n（X+Y） （B） 3Y+2X （C） n（X+Y）–X （D） Y+2X 答复: （C） 说明： 所需背景- 堆栈 还有基础数学

允许 Tn 是堆栈第n个元素的时间跨度。让我们先求出n=1到n的Tn之和

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）以a为第一项，l为最后一项的AP系列之和，用于第二次求和

以上是，

=（2X（n-1）n）/2+Y（n/2）*（1+2n-1）

=n（n（X+Y）-X）

因此，平均值=Sum/n=n（X+Y）-X。因此，选择（c）

这一解释是由 Pranjul Ahuja。 这个问题的小测验