当前课程知识点：Data Structures and Algorithm Design Part I >  04.Stack+Queue >  C3.stack-App-permutation >  04C3-2

返回《Data Structures and Algorithm Design Part I》慕课在线视频课程列表

04C3-2在线视频

下一节:04C3-3

返回《Data Structures and Algorithm Design Part I》慕课在线视频列表

04C3-2课程教案、知识点、字幕

那么对于长度为n的输入序列

可能得到的栈混洗总共有多少种呢？

假定输入栈A中共有n个元素

而且它们自顶向下

依次编号为1 2 3一直到n

这里我们需要将注意力放在第一个元素上

不难理解 它将首先被推入中转栈S中

那么接下来 我们要问的问题是

这个元素是在什么时候

被转入到最终的栈B中呢？

请注意 1号元素

既然作为第1个元素被推入S中

那么当它被弹出并进而推入栈B之后

栈S应该成为一个空栈

此时在栈B中

如果包括刚推入的1号元素

累计共有k个元素

那么相应地 在栈A中

就应该还留存有最靠后的n-k个元素

由此可见 此时B中最靠底的k-1个元素

和A中最靠底的n-k个元素

它们的栈混洗实际上是相互独立的

因此对应于1号元素 作为第k个元素

被推入B中的情况

累计而言 对应的栈混洗总数

就应该是这两个相互独立的子序列

所各自对应的栈混洗总数的乘积

而对于1号元素来说

k所有的可能取值

所对应的混洗数的总和

就应该恰好是我们最初

要计算的栈混洗总数

那么这里的k可以在什么范围内取值呢？

首先 k可以从1开始

也就是说 1号元素

直接作为第1个元素被转入栈B中

另一个极端 k也可能取值为n

也就是说 1号元素

作为最后一个元素被推入栈B中

至此 我们就得到了一个

非常典型的递推式

如果再考虑到它的平凡情况

也就是当只有1个元素的时候

对应的栈混洗数自然是1

那么就可以知道这个递推式的解

恰好是著名的catalan数

其数值等于2n的阶乘

除以n+1的阶乘 再除以n的阶乘

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--（a）计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-（xd）：LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

04C3-2笔记与讨论

也许你还感兴趣的课程:


  1. 火工品设计原理(2021秋)

  2. Inorganic Chemistry(2021秋)

  3. English Course on Chinese Culture(Round 2)

  4. 税务会计实务(2021秋)

  5. Advance of Infection and Immunity(Round 2)

  6. 学术写作(2021秋)

  7. 核电厂系统与设备(2021秋)

  8. 创新创业基础(2021秋)

  9. 理论力学(2021秋)

  10. Traditional Chinese Medicine(2021秋)

  11. Data Structures and Algorithm Design Part I(Self-Paced)

  12. 清华大学计算机科学与技术系六十周年系庆学术报告（四）大数据(自主模式)

  13. Mechanical Manufacturing Technology(Round 1)

  14. Surgery(Spring 2021)

  15. 临床研究方法学导论(2021春)

  16. 2019年研究生学术与职业素养讲座(自主模式)

  17. 工业互联网大讲堂(自主模式)

  18. Chinese History From Warring States to the Tang Dynasty(Self-Paced)

  19. History of Chinese Architecture Part I(Self-Paced)

  20. Database Technology and Programming(Round 1)
© 柠檬大学-慕课导航 课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。