n个元素被压入堆栈。有几种爆炸方法

更新时间:2019-10-05 10:58点击数:
全部展开
将n个元素的堆栈数计算为f(n),如果得到1,2,3,则可以轻松获得:f(1)= 1 //即1f(2)= 2 // 12,21f(3)= 5 //这是123、132、213、321、231。然后考虑f(4),给出编号为a,b,c,d的四个元素,然后考虑。仅元素和位置4(很容易理解,位置1中总共有4个位置,例如abcd,元素a)。
分析:1)如果元素a在第一个位置,则可以将其推入堆栈并立即删除。此时,其余元素b,c和d正在等待操作。这是子问题f(3)。2)如果元素a位于位置2,则必须比a首先堆叠一个元素。也就是说,根据乘法原理,f(1)个可能的序列(仅b)以及c,d,f(2),总阶为f(1)* f(2)。3)如果元素a在位置3,则堆栈外部必须有两个元素。即,f(2)(仅b和c)和d的阶数保持不变,即f(1)。根据乘法原理,阶数之和为f(2)* f(1)。4)如果元素a位于第4位,则它必须是高级堆栈,并且最后出现的元素b,c,d的堆栈顺序是这个小问题,即f(3);所有结合情况,即f(4)= f(3)+ f(2)* f(1)+ f(1)* f(2)+ f(3);对于归一化,f(0)= 1已定义。f(4)可以重写为:f(4)= f(0)* f(3)+ f(1)* f(2)+ f(2)* f(1)+f(3)* f(0)然后当an = 4时推广a,推广思想,并完全得到:f(n??)= f(0)* f(n-1)+ f(1)* f(n-2)+。
+ f(n-1)* f(0)