信息学奥赛问题求解选讲讲稿.ppt

《信息学奥赛问题求解选讲讲稿.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛问题求解选讲讲稿.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息学奥赛问题求解选讲第一页，讲稿共五十一页哦归纳推理Contents归纳推理归纳逻辑推理初等数论递推递归数据结构其他江凡问题求解选讲August 10, 201612345第二页，讲稿共五十一页哦归纳推理归纳 例例1，根据，根据Nocomachns定理，任何一个正整数定理，任何一个正整数n的立方一定的立方一定可以表示成可以表示成n个连续的奇数的和。个连续的奇数的和。 例如：例如： 13 1 23 3 5 33 7 9 11 43= 13+15+17+19 在这里，若将每一个式中的最小奇数称为在这里，若将每一个式中的最小奇数称为X，那么当给出，那么当给出n之后之后，请写出，请写出X与与n之间的

2、关系表达式。之间的关系表达式。江凡问题求解选讲August 10, 2016X=N2-N+1 第三页，讲稿共五十一页哦归纳推理归纳 例例2，将边长为，将边长为n的正三角形每边的正三角形每边n等分，过每个分点分别做另等分，过每个分点分别做另外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形外两边的平行线，得到若干个正三角形，我们称为小三角形。正三角形的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是的一条通路是一条连续的折线，起点是最上面的一个小三角形，终点是最下面一行位于中间的小三角形。在通路中，只允许由一个小三角形走最下面一行位于中间的小三角形。在通路中，只允许由一个

3、小三角形走到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个到另一个与其有公共边的且位于同一行或下一行的小三角形，并且每个小三角形不能经过两次或两次以上（图中是小三角形不能经过两次或两次以上（图中是n=5时一条通路的例子）时一条通路的例子）。设。设n=10，则该正三角形的不同的通路的总数为，则该正三角形的不同的通路的总数为 。江凡问题求解选讲August 10, 2016第四页，讲稿共五十一页哦归纳推理江凡问题求解选讲August 10, 2016n=5n=5时，方案有时，方案有1 12 23 34 44!4!n=10n=10时，方案有时，方案有1 12 29 99!9!n=2n=

4、2时，方案有时，方案有1 1种。种。n=3n=3时，方案有时，方案有2 2种。种。n=4n=4时，方案有时，方案有6 6种。种。归纳第五页，讲稿共五十一页哦逻辑推理 通常把只涉及一些相互关联（或依存）条件或关系，极少给出（不直接赋与）数量关系与几何图形的一类非标准（常规）数学问题叫逻辑推理问题，处理这类问题，要从一些关联的条件出发，应用某些数学知识，甚至日常生活常识，依据一定的思维规律（机智灵活、准确敏捷的思考），通过分析、推理、排除不可能情况（剔除不合理成分），然后作出正确的判断。逻辑推理问题中常用到以下三条逻辑基本规律：（1）同一律：是指同一东西（对象）。它是什么就是什么，不能模棱两可，亦

5、此亦彼；（2）矛盾律：是指互相对立（矛盾）的事不能都真，二者必有一假（即同一思想不能既真又假）；（3）排中律：是指两个不相容的判断不能都假，二者必有一真（即任何判断或同一思想不能既不真也不假）。归纳推理逻辑推理江凡问题求解选讲August 10, 2016第六页，讲稿共五十一页哦归纳推理逻辑推理利用表格辅助推理: 例3，某中学推理社招新题，答案是 _这道题的答案是AAB BC CD D第5题的答案是ACB DC AD B以下选项中哪一题的答案与其他三项不同A第3题B 第6题C 第2题D 第4题以下选项中哪两题的答案相同A第1，5题B 第2，7题C 第1，9题D 第6，10题以下选项中哪一题的答

6、案与本题相同A第8题B 第4题C 第9题D 第7题以下选项中哪两题的答案与第8题相同A第2，4题B 第1，6题C 第3，10题D 第5，9题在此十道题中，被选择次数最少的选项字母为ACB BC AD D以下选项中哪一题的答案与第1题的答案在字母表中的不相邻A第7题B 第5题C 第2题D 第10题已知“第1题与第6题的答案相同”与“第X题与第5题的答案相同”的真假性相反，那么X为A第6题B 第10题C 第2题D 第9题在此十道题中，ABCD四个字母中出现的次数最多者与最少者的差为A3B 2C 4D 1江凡问题求解选讲August 10, 2016BCACACDABA 第七页，讲稿共五十一页哦归纳

7、推理逻辑推理利用图形辅助推理美国数学家斯蒂恩说过:“如果一个特定的问题可以被转化成一个图形,那么,思想就整体地把握了问题,并且能创造性地思索问题解法。” 例4，A、B、C、D、E五支球队进行单循环比赛（每两支球队间都要进行一场比赛），当比赛进行到一定阶段时，统计A、B、C、D四个球队已经赛过的场数，依次为A队4场，B队3场，C队2场，D队1场，这时，E队已赛过的场数是（）A. 1B. 2C. 3D. 4 江凡问题求解选讲August 10, 2016B第八页，讲稿共五十一页哦数论基础Contents归纳推理数论基础同余素数排列组合递推递归数据结构其他江凡问题求解选讲August 10, 201

8、612345第九页，讲稿共五十一页哦数论基础同余如果a1a2 b1 b2(mod m)(mod m)那么b1a1 a2 b2b1 b2(mod m)(mod m)江凡问题求解选讲August 10, 2016a1a2同余的定义与性质如果 m 整除 a b，我们就说 a 与 b 模 m 同余并记为a b(mod m)简单来说，就是它们模 m 后的余数相同就可以记成这样。第十页，讲稿共五十一页哦数论基础同余江凡问题求解选讲August 10, 2016（a1 a2）mod b (a1 mod b)( a2 mod b) mod b分治思想与快速幂方法例5，输入b，p，k的值，求 bp mod k

9、的值。如，59 mod 7 = ？59 = 【（5 5） （5 5）】 【（5 5） （5 5）】 54422456第十一页，讲稿共五十一页哦 x a1 x a2.数论基础同余方程与中国剩余定理中国剩余定理 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？孙子算经 这个问题说的是：有一个整数，被 3 除余 2，被 5 除余 3，被 7 除余 2，问这个整数是多少？ 事实上，这个问题有无穷多个解，其中一个解是 23。中国剩余定理，又称为孙子定理，常常简写成 CRT（Chinese RemainderTheorem）。它给出了构造如下方程组解的方法：(mod m1 )(mod m

10、2 ).x an(mod mn )其中 m1 , m2 , . . . , mn 两两互素。江凡问题求解选讲August 10, 2016第十二页，讲稿共五十一页哦同余方程与中国剩余定理数论基础中国剩余定理首先来解只有两个方程的方程组。xx a1 a2(mod m1 )(mod m2 )我们可以把这个方程组改写成xx= a1 + k1 m1= a2 + k2 m2消去 x 之后就可以得到 a1 + k1 m1 = a2 + k2 m2 ，这刚好是关于 k1 , k2 的一个线性方程。 此外，中国剩余定理还告诉我们一个事实，在 m1 , m2 互素的条件下，假设 x0是该方程组的一个解，那么该方

11、程组的所有解都满足如下形式：江凡问题求解选讲August 10, 2016x x0(mod m1 m2 )这样我们相当于把刚刚的两个方程合并成为了一个方程。如果有多个方程，可以不断进行这样的合并，最后就可以解出结果了。第十三页，讲稿共五十一页哦x 2x 2数论基础同余方程与中国剩余定理中国剩余定理我们来拿刚刚开头的例子来试着算一算。那个方程组是：x 3(mod 3)(mod 5)(mod 7)江凡问题求解选讲August 10, 2016首先来合并前两个方程，联立后得到的线性方程是 2 + 3k1 = 3 + 5k2 ，整理后可以得到一组解是 k1 = 2, k2 = 1，这样可以得到满足前两

12、个方程的 x 都满足：x 8 (mod 15)第十四页，讲稿共五十一页哦数论基础同余方程与中国剩余定理中国剩余定理之后可以得到新的方程组：xx 8 2(mod 15)(mod 7)再合并两个方程，联立后得到的线性方程是 8 + 15k1 = 2 + 7k2 ，整理后可以得到一组解是 k1 = 1, k2 = 3，这样可以得到满足这两个方程的 x 都满足：x 23(mod 105)这便是最后的解了！江凡问题求解选讲August 10, 2016第十五页，讲稿共五十一页哦数论基础素数及基本知识江凡问题求解选讲August 10, 2016素数及基本知识素数是只含有 1 及其本身两个正因子的数，也称

13、为质数。如果还有其它正因子的话，那么这个数就被称为合数。注意 1 并非素数，亦非合数。我在这里介绍一个关于素数的定理，它们在算法复杂度分析中或许会用到：Theorem (素数定理)当 x 很大时，小于 x 的素数个数近似等于x/lnx第十六页，讲稿共五十一页哦数论基础江凡问题求解选讲August 10, 2016素数的判定 如何判定一个数 m 是不是素数，我们可以直接从定义出发，从 2 开始到m-1 为止，检测是否有一个数整除 m，如果没有，那么这个数就是素数。 例6，求105内的所有素数。 Eratosthenes 筛法筛法是一种用来求素数的方法，它的思路比较简单。 由于每个合数都可以被分解

14、成几个素数的乘积，如果我们将所有素数的倍数都删去，那么剩下的就是素数了。 因此，我们可以从 2 开始，先将 2 的所有倍数都删去。然后往下找到第一个没有被删去的数，这个数一定是素数，再将这个数的所有倍数都删去，不断进行这个操作。素数及基本知识 线性筛法线性筛法，又称欧拉筛法。 避免冗余的运算。每个合数必有一个最大因子（不包括它本身） ，用这个因子把合数筛掉。 对于每一个数i，乘上小于等于i的最小素因数的素数，就得到以i为最大因数的合数。设有一个数t，只要将所有以比t小的数为最大因数的合数筛去，那么比t小的数里剩下的就只有素数了。第十七页，讲稿共五十一页哦组合数学基础排列组合 组合数学基础 例7

15、，在1与106之间，有多少个整数的各位数字之和等于9？江凡问题求解选讲August 10, 2016第十八页，讲稿共五十一页哦组合数学基础排列组合 排列 现在来考虑一个问题：你需要在 n 个不同的人里面选出 m 个人排成一行，问有多少种排列方案？ n(n 1)(n 2) (n m + 1)这个数通常被成为排列，记成 ，或者 。 如果我们定义一种名为阶乘的运算：n!= 1 2 3 n特别地，当 n = 0 时，0! = 1。那么这个数就可以简单地写成：Anm=n!(n m)!江凡问题求解选讲August 10, 2016AnmP nm第十九页，讲稿共五十一页哦组合数学基础排列组合 排列 圆排列圆

16、排列 （1）由 的个元素中，每次取出r个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）。 （2）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列。 （3）定理：在的个元素中，每次取出个不同的元素进行圆排列，圆排列数为 。 不尽相异元素的全排列不尽相异元素的全排列 如果n个元素中，有p1个元素相同，又有p2个元素相同，又有ps个元素相同（ ），这个n元素全部取的排列叫做不尽相异的n个元素的全排列，它的排列数是 。江凡问题求解选讲August 10, 2016rPrn!21spp

17、pn,321naaaaAnppps21第二十页，讲稿共五十一页哦组合数学基础排列组合组合研究无次序的选取问题。把前述排列问题改成：你只需要在 n 个不同的人里面选出 m 个人，问有多少种方案？ 如果我们选出来 m 个人后，再将他们排成一队，那么方案数就是先前的排列数 。 但是这样的计数会出现很多的重复，也就是每次我们都多算了将 m 个人排成一队的方案数，那么这个数是什么呢？ 它就是 ，或者说 m!。 那么由于每种方案都被重复计算了 m! 次，我们只要将 除以 m! 就可以得到组合数的公式了！江凡问题求解选讲August 10, 2016AnmAmmAnmCnm=nAm!=n!m!(n m)!m

18、第二十一页，讲稿共五十一页哦排列组合组合数学基础组合数的基本性质首先第一个性质就是先前的递推关系(1)此外，直接根据通项可以得到一个对称的性质：(2)江凡问题求解选讲August 10, 2016Cnm= Cn1 + Cn1mm-1Cnm= Cnn-m第二十二页，讲稿共五十一页哦排列组合组合数学基础排列组合分析原理江凡问题求解选讲August 10, 2016 加法原理 如果完成一件事情有n种方式A1，An，每种方式中又有mi种方法（1in），且Ai Aj= ，则要完成此事共有 ，即n1iimN12nNmmm 乘法原理 如果完成一件事情要分几个步骤B1 ，B2 ， ，Bn ，而每个步骤Bi有m

19、i种方法(1in) ，那么完成这事共有 ，即n1iimN12nNmmm第二十三页，讲稿共五十一页哦7名学生站成一排，甲、乙必须站在一起有多少不同排法？（ ）7名学生站成一排，甲乙互不相邻有多少不同排法？ （ ） 我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种? （ ）某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（ ）（ ） A42 B30 C20 D12 从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（ ）（ ）

20、 A24种 B18种 C12种 D6种 7 在1与106之间，有多少个整数的各位数字之和等于9？（ ）排列组合组合数学基础例题分析江凡问题求解选讲August 10, 2016200251491 -69CC14402266 AA36002655 AA540543CC262216AAA222313ACA第二十四页，讲稿共五十一页哦排列组合组合数学基础例题分析江凡问题求解选讲August 10, 2016 小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1-a2-a3，B=b1-b2-b3-b4-b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务

21、的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如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

22、、b3、b4、b5 有 种。14C25C36C47C第二十五页，讲稿共五十一页哦排列组合组合数学基础 例题分析 我们在讨论重排列时，如将问题化为：设盒子是有区别的，每个盒子的容量不限，而且球数k盒数n，现计算无空盒出现的情况数目。 假设要用n-1块隔板，将排成一行的k个球隔成n段，但任意两块隔板不能相邻，否则就要出现空盒，同理隔板也不能出现在两端。所以相当于要自k个球之间的k-1个间隔中选出n-1个来放置隔板，如图 O|OO|O|OOO|O|O|OOO|OO|O 所以是一个组合问题，知有 种不同情况。x + y + z + w = 23，有多少正整数解？解：与前面例子相似，但x、y、z、w不能

23、等0。即知 有 个正整数解。江凡问题求解选讲August 10, 20161n1kC154032214123CC第二十六页，讲稿共五十一页哦递推递归Contents归纳推理数论基础递推递归递推递归数据结构其他江凡问题求解选讲August 10, 201612345第二十七页，讲稿共五十一页哦递推递推递归江凡问题求解选讲August 10, 2016 给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0i0n0），求出铺法总数的递推公式。），求出铺法总数的递推公式。 对给出的任意一个对给出的任意一个n（n0），用），用F（n

24、）表示其铺法）表示其铺法的总数的递推公式为的总数的递推公式为: F（1）=1 F（2）=2 F（n）=F（n-2）+F（n-1）（）（n3）递推江凡问题求解选讲August 10, 2016递推递归第二十九页，讲稿共五十一页哦设有一个共有设有一个共有n n级的楼梯，某人每步可走级的楼梯，某人每步可走1 1级，也可走级，也可走2 2级，也可走级，也可走3 3级，级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3n=3时，共有时，共有4 4种走法，即种走法，即1+1+1,1+2,2+1,31+1+1,1+2,2+1,3。 F（

25、1）1 F（2）2 F（3）4F（N）F（N3）F（N2）F（N1）（）（N4）递推江凡问题求解选讲August 10, 2016递推递归第三十页，讲稿共五十一页哦递推江凡问题求解选讲August 10, 2016递推递归Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？ a b c 图1第三十一页，讲稿共五十一页哦递推江凡问题求解选讲Aug

26、ust 10, 2016递推递归设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。12132412346578图21234567108911121314n=1n=2n=3n=4第三十二页，讲稿共五十一页哦递推江凡问题求解选讲August 10, 2016递推递归在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案(图3)，故h5=5。求对于一个任意的凸n边形相应的hn。 图3112inniiCC第三十三页，讲

27、稿共五十一页哦递推江凡问题求解选讲August 10, 2016递推递归错排问题（经典问题）。 n个数，分别为1n，排成一个长度为n的排列。若每一个数的位置都与数的本身不相等，则称这个排列是一个错排。例如，n=3，则错排有2 3 1、3 1 2。求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

28、)(2,3,4,1)它们有什么规律呢？第三十四页，讲稿共五十一页哦递归江凡问题求解选讲August 10, 2016递推递归通过反复的试验，我们发现事实上有两种方式产生错位排列：A.将k与(1，2，k1)的某一个数互换，其他k2个数进行错排，这样可以得到(k1)W(k-2)个错位排列。B.另一部分是将前k1个元素的每一个错位排列（有W(k-1)个）中的每一个数与k互换，这样可以得到剩下的(k1)W(k-1) 个错位排列。根据加法原理，我们得到求错位排列的递推公式W(k):第三十五页，讲稿共五十一页哦传球问题江凡问题求解选讲August 10, 2016其他4个人进行篮球训练，互相传球接球，要求

29、每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？第三十六页，讲稿共五十一页哦传球问题江凡问题求解选讲August 10, 2016其他第三十七页，讲稿共五十一页哦传球问题江凡问题求解选讲August 10, 2016其他设有棱长为1米的正四面体ABCD，一只蚂蚁从顶点A 出发，遵循下列规则爬行：在每个顶点相交的3条棱中选一条，然后沿这条棱到另一个顶点。求蚂蚁爬行了7米路之后，又回到顶点A的方法总数。解：设从点解：设从点A出发走过出发走过n米回到点米回到点A的走法为的走法为an种。由于从种。由于从A出发走出发走n-1米的走法共有米的走法

30、共有3n-1种种,其中有其中有an-1种是走到种是走到A的，下一步一定离开的，下一步一定离开A，除去这，除去这an-1种，其它的每一种都可以再种，其它的每一种都可以再走走1米到达米到达A点。因此，点。因此， an= 3n-1 - an-1。第三十八页，讲稿共五十一页哦传球问题江凡问题求解选讲August 10, 2016其他 一个学生暑假在A、B、C三个城市游览。他今天在这个城市，明天就到另一个城市。假设他第一天在A市，第五天又回到A市，问他有几种不同的游览方案？ 第三十九页，讲稿共五十一页哦递归江凡问题求解选讲August 10, 2016递推递归 一个函数、过程、概念或数学结构，如果在其定

31、义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。 递归过程是借助于一个递归工作栈来实现的 问题向一极推进，这一过程叫做递推； 而问题逐一解决，最后回到原问题，这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。例，用递归算法求n的阶乘，记n!定义：函数 fact( n ) = n! fact( n-1 ) = ( n-1 )! 则有 fact( n ) = n * fact( n-1 ) 已知 fact( 1 ) = 1第四十页，讲稿共五十一页哦递归江凡问题求解选讲August 10, 2016下面画出了调用和返回的递归示意图 Bfact(2)fact(

32、2)=2*fact(1)=2*fact(1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1调用调用调用调用递推递归第四十一页，讲稿共五十一页哦 某城市的街道是一个很规整的矩形网络（见下图），有7条南北向的纵街，5条东西向的横街。现要从西南角的A走到东北角的B，最短的走法共有多少种？_ 210 11111 1 1 1 1 12 3 4 5 6 7 3 6 10 15 21 28 4 10 20 35 56 84 5 15 35 70 126 210递归江凡问题求解选讲Augus

33、t 10, 2016递推递归第四十二页，讲稿共五十一页哦递归江凡问题求解选讲August 10, 2016递推递归 将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)=_。 9090第四十三页，讲稿共五十一页哦递归江凡问题求解选讲August 10, 2016递推递归对任一元

34、素an ，必然出现以下两种情况：an是r个子集合中的一个，于是我们只要把a1,a2,an-1划分为r-1个子集，便解决了本题，这种情况下的划分数共有s(n-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 r* *s(n-1,r)s(n-1,r)。第四十四页，讲稿共五十一页哦递归江凡问题求解选讲Augu

35、st 10, 2016递推递归 首先不能把n个元素不放进任何一个集合中去，即r=0时，s(n,r)=0； 也不可能在不允许空集的情况下把n个元素放进多于n的r个集合中去，即rn时, s(n,r)=0 ； 再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是，即r=1或r=n时, s(n,r)=1。第四十五页，讲稿共五十一页哦数据结构Contents归纳推理数论基础递推递归数据结构其他江凡问题求解选讲August 10, 201612345第四十六页，讲稿共五十一页哦栈江凡问题求解选讲August 10, 2016数据结构先进后出（FILO）结构34521 34215 32145

36、 32451 34251 32415 32154 35421 32541如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列方案。3214 53 4 5 3 5 4第四十七页，讲稿共五十一页哦树江凡问题求解选讲August 10, 2016数据结构 以进制编码方式对一个英文字串中的字符进行编码，每个不同的字符其编码不同使得由新的编码替代原串后总码长最小，且输入，构成的数字串后，依照该编码方式可以正确的对译出唯一的英文原串如：英文原串为其对应的一种

37、编码方式为：原串对译后的编码为其码长为若输入编码串则对应的英文原串为第四十八页，讲稿共五十一页哦 城市1城 市2城 市3城 市4城 市5城 市6城市102311215城市22025312城市3320365城市4153079城市51236702城市615125920图数据结构江凡问题求解选讲August 10, 2016有有6 6个城市，任何两个城市之间有一条道路连接，个城市，任何两个城市之间有一条道路连接，6 6个城市之间两两之间的个城市之间两两之间的距离如下表表示，则城市距离如下表表示，则城市1 1到城市到城市6 6的最短距离为的最短距离为_。第四十九页，讲稿共五十一页哦设置两个顶点的集合S

38、和T=V-S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。图数据结构江凡问题求解选讲August 10, 2016第五十页，讲稿共五十一页哦1383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432032856230137179第五十一页，讲稿共五十一页哦