信息学奥赛问题求解选讲

信息学奥赛问题求解选讲第一页，共五十一页，2022年，8月28日

归纳推理Contents归纳推理

归纳

逻辑推理初等数论递推递归数据结构其他江凡问题求解选讲August10,201612345第二页，共五十一页，2022年，8月28日归纳推理归纳

例1，根据Nocomachns定理，任何一个正整数n的立方一定可以表示成n个连续的奇数的和。例如：

13＝123＝3＋533＝7＋9＋1143=13+15+17+19

在这里，若将每一个式中的最小奇数称为X，那么当给出n之后，请写出X与n之间的关系表达式。江凡问题求解选讲August10,2016X=N2-N+1第三页，共五十一页，2022年，8月28日归纳推理归纳

例2，将边长为n的正三角形每边n等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）。设n=10，则该正三角形的不同的通路的总数为

。

江凡问题求解选讲August10,2016362880第四页，共五十一页，2022年，8月28日归纳推理江凡问题求解选讲August10,2016n=5时，方案有1×2×3×4＝4!n=10时，方案有1×2×…×9＝9!n=2时，方案有1种。n=3时，方案有2种。n=4时，方案有6种。归纳第五页，共五十一页，2022年，8月28日逻辑推理

通常把只涉及一些相互关联（或依存）条件或关系，极少给出（不直接赋与）数量关系与几何图形的一类非标准（常规）数学问题叫逻辑推理问题，处理这类问题，要从一些关联的条件出发，应用某些数学知识，甚至日常生活常识，依据一定的思维规律（机智灵活、准确敏捷的思考），通过分析、推理、排除不可能情况（剔除不合理成分），然后作出正确的判断。逻辑推理问题中常用到以下三条逻辑基本规律：（1）同一律：是指同一东西（对象）。它是什么就是什么，不能模棱两可，亦此亦彼；（2）矛盾律：是指互相对立（矛盾）的事不能都真，二者必有一假（即同一思想不能既真又假）；（3）排中律：是指两个不相容的判断不能都假，二者必有一真（即任何判断或同一思想不能既不真也不假）。归纳推理逻辑推理江凡问题求解选讲August10,2016第六页，共五十一页，2022年，8月28日归纳推理逻辑推理利用表格辅助推理:

例3，某中学推理社招新题，答案是_____________⒈这道题的答案是A．A B．B C．C D．D⒉第5题的答案是A．C B．D C．A D．B⒊以下选项中哪一题的答案与其他三项不同A．第3题 B．第6题 C．第2题 D．第4题⒋以下选项中哪两题的答案相同A．第1，5题 B．第2，7题 C．第1，9题 D．第6，10题⒌以下选项中哪一题的答案与本题相同A．第8题 B．第4题 C．第9题 D．第7题⒍以下选项中哪两题的答案与第8题相同A．第2，4题 B．第1，6题 C．第3，10题 D．第5，9题⒎在此十道题中，被选择次数最少的选项字母为A．C B．B C．A D．D⒏以下选项中哪一题的答案与第1题的答案在字母表中的不相邻A．第7题 B．第5题 C．第2题 D．第10题⒐已知“第1题与第6题的答案相同”与“第X题与第5题的答案相同”的真假性相反，那么X为A．第6题 B．第10题 C．第2题 D．第9题⒑在此十道题中，ABCD四个字母中出现的次数最多者与最少者的差为A．3 B．2 C．4 D．1江凡问题求解选讲August10,2016BCACACDABA

第七页，共五十一页，2022年，8月28日归纳推理逻辑推理利用图形辅助推理美国数学家斯蒂恩说过:“如果一个特定的问题可以被转化成一个图形,那么,思想就整体地把握了问题,并且能创造性地思索问题解法。”例4，A、B、C、D、E五支球队进行单循环比赛（每两支球队间都要进行一场比赛），当比赛进行到一定阶段时，统计A、B、C、D四个球队已经赛过的场数，依次为A队4场，B队3场，C队2场，D队1场，这时，E队已赛过的场数是（ ）A.1 B.2 C.3 D.4江凡问题求解选讲August10,2016B第八页，共五十一页，2022年，8月28日

数论基础Contents归纳推理数论基础同余素数排列组合递推递归数据结构其他江凡问题求解选讲August10,201612345第九页，共五十一页，2022年，8月28日数论基础同余如果a1a2≡b1≡b2(modm)(modm)那么b1a1

±a2≡±b2b1

b2(modm)(modm)江凡问题求解选讲August10,2016a1a2≡同余的定义与性质

如果m整除a−b，我们就说a与b模m同余并记为a≡b(modm)简单来说，就是它们模m后的余数相同就可以记成这样。第十页，共五十一页，2022年，8月28日数论基础同余江凡问题求解选讲August10,2016（a1×a2）modb＝(a1modb)×(a2modb)modb分治思想与快速幂方法例5，输入b，p，k的值，求bpmodk的值。如，59mod7=？59=【（5×5）×（5×5）】×【（5×5）×（5×5）】×54422456第十一页，共五十一页，2022年，8月28日x≡a1x≡a2..数论基础同余方程与中国剩余定理

中国剩余定理有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

——《孙子算经》

这个问题说的是：有一个整数，被3除余2，被5除余3，被7除余2，问这个整数是多少？事实上，这个问题有无穷多个解，其中一个解是23。

中国剩余定理，又称为孙子定理，常常简写成CRT（ChineseRemainderTheorem）。它给出了构造如下方程组解的方法：(modm1)(modm2).x≡an(modmn)其中m1,m2,...,mn

两两互素。江凡问题求解选讲August10,2016第十二页，共五十一页，2022年，8月28日同余方程与中国剩余定理

数论基础中国剩余定理

首先来解只有两个方程的方程组。xx≡a1≡a2(modm1)(modm2)我们可以把这个方程组改写成xx=a1+k1m1=a2+k2m2

消去x之后就可以得到a1+k1m1=a2+k2m2

，这刚好是关于k1,k2的一个线性方程。此外，中国剩余定理还告诉我们一个事实，在m1,m2互素的条件下，假设x0是该方程组的一个解，那么该方程组的所有解都满足如下形式：江凡问题求解选讲August10,2016x≡x0(modm1m2)

这样我们相当于把刚刚的两个方程合并成为了一个方程。如果有多个方程，可以不断进行这样的合并，最后就可以解出结果了。第十三页，共五十一页，2022年，8月28日x≡2x≡2数论基础同余方程与中国剩余定理中国剩余定理

我们来拿刚刚开头的例子来试着算一算。那个方程组是：x≡3(mod3)(mod5)(mod7)江凡问题求解选讲August10,2016

首先来合并前两个方程，联立后得到的线性方程是2+3k1=3+5k2

，整理后可以得到一组解是k1=2,k2=1，这样可以得到满足前两个方程的x都满足：x≡8(mod15)第十四页，共五十一页，2022年，8月28日数论基础同余方程与中国剩余定理中国剩余定理

之后可以得到新的方程组：xx≡8≡2(mod15)(mod7)

再合并两个方程，联立后得到的线性方程是8+15k1=2+7k2

，整理后可以得到一组解是k1=1,k2=3，这样可以得到满足这两个方程的x都满足：x≡23(mod105)这便是最后的解了！江凡问题求解选讲August10,2016第十五页，共五十一页，2022年，8月28日数论基础素数及基本知识江凡问题求解选讲August10,2016

素数及基本知识

素数是只含有1及其本身两个正因子的数，也称为质数。如果还有其它正因子的话，那么这个数就被称为合数。注意1并非素数，亦非合数。 我在这里介绍一个关于素数的定理，它们在算法复杂度分析中或许会用到：Theorem(素数定理)当x很大时，小于x的素数个数近似等于x/lnx第十六页，共五十一页，2022年，8月28日数论基础江凡问题求解选讲August10,2016

素数的判定

如何判定一个数m是不是素数，我们可以直接从定义出发，从2开始到m-1为止，检测是否有一个数整除m，如果没有，那么这个数就是素数。

例6，求105内的所有素数。

⒈Eratosthenes筛法是一种用来求素数的方法，它的思路比较简单。由于每个合数都可以被分解成几个素数的乘积，如果我们将所有素数的倍数都删去，那么剩下的就是素数了。因此，我们可以从2开始，先将2的所有倍数都删去。然后往下找到第一个没有被删去的数，这个数一定是素数，再将这个数的所有倍数都删去，不断进行这个操作。素数及基本知识

⒉线性筛法，又称欧拉筛法。避免冗余的运算。每个合数必有一个最大因子（不包括它本身），用这个因子把合数筛掉。对于每一个数i，乘上小于等于i的最小素因数的素数，就得到以i为最大因数的合数。设有一个数t，只要将所有以比t小的数为最大因数的合数筛去，那么比t小的数里剩下的就只有素数了。第十七页，共五十一页，2022年，8月28日组合数学基础排列组合

组合数学基础例7，在1与106之间，有多少个整数的各位数字之和等于9？江凡问题求解选讲August10,2016第十八页，共五十一页，2022年，8月28日组合数学基础排列组合

排列现在来考虑一个问题：你需要在n个不同的人里面选出m个人排成一行，问有多少种排列方案？

n(n−1)(n−2)···(n−m+1)

这个数通常被成为排列，记成，或者。如果我们定义一种名为阶乘的运算：n!=1×2×3×···×n特别地，当n=0时，0!=1。那么这个数就可以简单地写成：Anm=

n!(n−m)!江凡问题求解选讲August10,2016AnmPnm第十九页，共五十一页，2022年，8月28日组合数学基础排列组合

排列圆排列（1）由的个元素中，每次取出r个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）。（2）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列。（3）定理：在的个元素中，每次取出个不同的元素进行圆排列，圆排列数为。不尽相异元素的全排列如果n个元素中，有p1个元素相同，又有p2个元素相同，…，又有ps个元素相同（），这个n元素全部取的排列叫做不尽相异的n个元素的全排列，它的排列数是。江凡问题求解选讲August10,2016第二十页，共五十一页，2022年，8月28日组合数学基础排列组合

组合

研究无次序的选取问题。把前述排列问题改成：你只需要在n个不同的人里面选出m个人，问有多少种方案？如果我们选出来m个人后，再将他们排成一队，那么方案数就是先前的排列数

。但是这样的计数会出现很多的重复，也就是每次我们都多算了将m个人排成一队的方案数，那么这个数是什么呢？它就是

，或者说m!。那么由于每种方案都被重复计算了m!次，我们只要将

除以m!就可以得到组合数的公式了！江凡问题求解选讲August10,2016AnmAmmAnmCnm=nAm!=

n!m!(n−m)!m第二十一页，共五十一页，2022年，8月28日排列组合

组合数学基础组合数的基本性质

首先第一个性质就是先前的递推关系(1)此外，直接根据通项可以得到一个对称的性质：(2)江凡问题求解选讲August10,2016Cnm=Cn−1+Cn−1mm-1Cnm=Cnn-m第二十二页，共五十一页，2022年，8月28日排列组合

组合数学基础排列组合分析原理全部组合分析公式的推导基于以下两原理：江凡问题求解选讲August10,2016

⒈加法原理如果完成一件事情有n种方式A1，∙∙∙，An，每种方式中又有mi种方法（1≤i≤n），且AiAj=Ø，则要完成此事共有，即

⒉乘法原理如果完成一件事情要分几个步骤B1

，B2

，…，Bn

，而每个步骤Bi有mi种方法(1≤i≤n)，那么完成这事共有，即第二十三页，共五十一页，2022年，8月28日例8．7名学生站成一排，甲、乙必须站在一起有多少不同排法？（相临问题——整体捆绑法）例9．7名学生站成一排，甲乙互不相邻有多少不同排法？（不相临问题——选空插入法）例10．我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种?（复杂问题——总体排除法或排异法）例11．某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（）（多元问题——分类讨论法）

A．42B．30C．20D．12例12．从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（）（混合问题——先选后排法）

A．24种

B．18种

C．12种

D．6种例7．在1与106之间，有多少个整数的各位数字之和等于9？（相同元素分配——转化与档板分隔法）排列组合

组合数学基础例题分析江凡问题求解选讲August10,2016第二十四页，共五十一页，2022年，8月28日排列组合

组合数学基础例题分析江凡问题求解选讲August10,2016

例13

．小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有

种。排列组合+加法原理:B任务中的b1一定做，而且肯定是第一个做的。除了b1外，第一类：完成A任务只有1种。第二类：完成A任务和b2有种。第三类：完成A任务和b2、b3有种。第四类：完成A任务和b2、b3、b4有种。第五类：完成A任务和b2、b3、b4、b5有种。1+4+10+20+35=70第二十五页，共五十一页，2022年，8月28日排列组合

组合数学基础例题分析鸽巢原理（又称抽屉原理）（简介）我们在讨论重排列时，如将问题化为：设盒子是有区别的，每个盒子的容量不限，而且球数k≥盒数n，现计算无空盒出现的情况数目。

假设要用n-1块隔板，将排成一行的k个球隔成n段，但任意两块隔板不能相邻，否则就要出现空盒，同理隔板也不能出现在两端。所以相当于要自k个球之间的k-1个间隔中选出n-1个来放置隔板，如图O|OO|O|OOO|O|O|OOO|OO|O

所以是一个组合问题，知有种不同情况。例14．x+y+z+w=23，有多少正整数解？解：与前面例子相似，但x、y、z、w不能等0。即知有个正整数解。江凡问题求解选讲August10,2016第二十六页，共五十一页，2022年，8月28日

递推递归Contents归纳推理数论基础递推递归递推递归数据结构其他江凡问题求解选讲August10,201612345第二十七页，共五十一页，2022年，8月28日递推

递推递归递推江凡问题求解选讲August10,2016

给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。几种典型递推关系

Fibonacci数列

Hanoi塔问题平面分割问题

Catalan数解决递推问题的一般步骤：建立递推关系式确定边界条件递推求解第二十八页，共五十一页，2022年，8月28日

例15．有2×n的一个长方形方格，用一个1×2的骨牌铺满方格。例如n=3时，为2×3方格。此时用一个1×2的骨牌铺满方格，共有3种铺法：试对给出的任意一个n（n>0），求出铺法总数的递推公式。对给出的任意一个n（n>0），用F（n）表示其铺法的总数的递推公式为:F（1）=1F（2）=2F（n）=F（n-2）+F（n-1）（n≥3）递推江凡问题求解选讲August10,2016

递推递归递推——斐波那契数列第二十九页，共五十一页，2022年，8月28日练习，设有一个共有n级的楼梯，某人每步可走1级，也可走2级，也可走3级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有4种走法，即1+1+1,1+2,2+1,3。F（1）＝1

F（2）＝2

F（3）＝4

F（N）＝F（N－3）＋F（N－2）＋F（N－1）（N≥4）递推江凡问题求解选讲August10,2016

递推递归递推——斐波那契数列第三十页，共五十一页，2022年，8月28日递推江凡问题求解选讲August10,2016

递推递归递推——Hanoi塔问题例16．Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。

要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？abc

图1递推关系：hn=2hn-1+1边界条件：h1=1第三十一页，共五十一页，2022年，8月28日递推江凡问题求解选讲August10,2016

递推递归递推——平面分割问题例17．设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。12132412346578图21234567108911121314n=1n=2n=3n=4递推关系：an=an-1+2(n-1)边界条件：a1=2第三十二页，共五十一页，2022年，8月28日递推江凡问题求解选讲August10,2016

递推递归递推——Catalan数例18．在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案(图3)，故h5=5。求对于一个任意的凸n边形相应的hn。图3边界条件：C2=1第三十三页，共五十一页，2022年，8月28日递推江凡问题求解选讲August10,2016

递推递归递推的应用——组合计数例19．错排问题（经典问题）。

n个数，分别为1~n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个排列是一个错排。例如，n=3，则错排有231、312。求n的错排个数。分析:我们设k个元素的错位全排列的个数记做：W(k)。四个元素的错位排列W(4)用穷举法可以找到如下9个：(4,3,2,1) (3,4,1,2) (2,1,4,3)

(4,1,2,3) (3,4,2,1) (3,1,4,2)

(4,3,1,2) (2,4,1,3) (2,3,4,1)它们有什么规律呢？第三十四页，共五十一页，2022年，8月28日递归江凡问题求解选讲August10,2016

递推递归递推的应用——组合计数通过反复的试验，我们发现事实上有两种方式产生错位排列：

A.将k与(1，2，…，k－1)的某一个数互换，其他k－2个数进行错排，这样可以得到(k－1)×W(k-2)个错位排列。

B.另一部分是将前k－1个元素的每一个错位排列（有W(k-1)个）中的每一个数与k互换，这样可以得到剩下的(k－1)×W(k-1)个错位排列。根据加法原理，我们得到求错位排列的递推公式W(k):W(k)=(k–1)×[W(k–1)+W(k–2)]第三十五页，共五十一页，2022年，8月28日传球问题江凡问题求解选讲August10,2016

其他传球问题

例20．4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？第三十六页，共五十一页，2022年，8月28日传球问题江凡问题求解选讲August10,2016

其他传球问题第三十七页，共五十一页，2022年，8月28日传球问题江凡问题求解选讲August10,2016

其他传球问题应用

练习：设有棱长为1米的正四面体ABCD，一只蚂蚁从顶点A出发，遵循下列规则爬行：在每个顶点相交的3条棱中选一条，然后沿这条棱到另一个顶点。求蚂蚁爬行了7米路之后，又回到顶点A的方法总数。解：设从点A出发走过n米回到点A的走法为an种。由于从A出发走n-1米的走法共有3n-1种,其中有an-1种是走到A的，下一步一定离开A，除去这an-1种，其它的每一种都可以再走1米到达A点。因此，an=3n-1-an-1。第三十八页，共五十一页，2022年，8月28日传球问题江凡问题求解选讲August10,2016

其他传球问题应用

练习：一个学生暑假在A、B、C三个城市游览。他今天在这个城市，明天就到另一个城市。假设他第一天在A市，第五天又回到A市，问他有几种不同的游览方案？

第三十九页，共五十一页，2022年，8月28日递归江凡问题求解选讲August10,2016

递推递归递归的概念与基本思想

一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。递归过程是借助于一个递归工作栈来实现的问题向一极推进，这一过程叫做递推；而问题逐一解决，最后回到原问题，这一过程叫做回归。递归的过程正是由递推和回归两个过程组成。例，用递归算法求n的阶乘，记n!定义：函数fact(n)=n! fact(n-1)=(n-1)!

则有fact(n)=n*fact(n-1)

已知fact(1)=1第四十页，共五十一页，2022年，8月28日递归江凡问题求解选讲August10,2016下面画出了调用和返回的递归示意图

递推递归递归的概念与基本思想第四十一页，共五十一页，2022年，8月28日

例21．某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？_____21011111111112345673610152128410203556845153570126210递归江凡问题求解选讲August10,2016

递推递归递归的应用递归关系：F(x,y)=F(x-1,y)+F(x,y-1)边界条件：F(1,y)=1F(x,1)=1第四十二页，共五十一页，2022年，8月28日递归江凡问题求解选讲August10,2016

递推递归递归的应用——子集划分

例22．将n个数（1，2，…，n）划分成r个子集。每个数都恰好属于一个子集，任何两个不同的子集没有共同的数，也没有空集。将不同划分方法的总数记为S(n,r)。例如，S(4,2)=7，这7种不同的划分方法依次为{(1),(234)}，{(2),(134)}，{(3),(124)}，{(4),(123)}，{(12),(34)}，{(13),(24)}，{(14),(23)}。当n=6，r=3时，S(6,3)=______。90第四十三页，共五十一页，2022年，8月28日递归江凡问题求解选讲August10,2016

递推递归递归的应用——子集划分对任一元素an

，必然出现以下两种情况：⑴｛an｝是r个子集合中的一个，于是我们只要把a1,a2,…,an-1划分为r-1个子集，便解决了本题，这种情况下的划分数共有s(n-1,r-1)。⑵｛an｝不是r个子集合中的一个，则an必与其它的元素构成一个子集。则问题相当于先把a1,a2,…,an-1划分为r个子集，这种情况下的划分数共有s(n-1,r)。然后再把元素an加入到r个子集合中的任一个中去，共有r种加入方式，这样对于an的每一种加入方式，都可以使集合划分为r个子集。因此根据乘法原理，划分数共有r*s(n-1,r)。S(n,r)=S(n-1,r-1)+r×S(n-1,r)第四十四页，共五十一页，2022年，8月28日递归江凡问题求解选讲August10,2016

递推递归递归的应用——子集划分确定边界：首先不能把n个元素不放进任何一个集合中去，即r=0时，s(n,r)=0；也不可能在不允许空集的情况下把n个元素放进多于n的r个集合中去，即r>n时,s(n,r)=0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是１，即r=1或r=n时,s(n,r)=1。S(6,3)=S(5,2)+3×S(5,3)=S(4,1)+2×S(4,2)+3×(S(4,2)+3×S(4,3))=……=90第四十五页，共五十一页，2022年，8月28日

数据结构Contents归纳推理数论基础递推递归数据结构其他江凡问题求解选讲August10,201612345第四十六页，共五十一页，2022年，8月28日栈江凡问题求解选讲August10,2016

数据结构栈——先进后出（FILO）结构34521342153214532451

34251

32415321543542132541

例23．如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列方案。3214