信息学奥赛问题求解选讲

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

2、，请写出X与与n之间的关系表达式。之间的关系表达式。江凡问题求解选讲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=2时，方案有时，方案有1

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

5、都真，二者必有一假（即同一思想不能既真又假）；（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题以下选项中哪一题的答案与本题相同A第8题B 第4题C 第9题D 第7题以下选项中哪两题的答案与

6、第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, 201612345数论基础同余如果a1a2 b1 b2(mod m)(mod m)那么b1a1 a2 b2b1 b2(mod m

8、)(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 的值。如，59 mod 7 = ？59 = 【（5 5） （5 5）】 【（5 5） （5 5）】 54422456 x a1 x a2.数论基础同余方程与中国剩余定理中

9、国剩余定理 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？孙子算经 这个问题说的是：有一个整数，被 3 除余 2，被 5 除余 3，被 7 除余 2，问这个整数是多少？ 事实上，这个问题有无穷多个解，其中一个解是 23。中国剩余定理，又称为孙子定理，常常简写成 CRT（Chinese RemainderTheorem）。它给出了构造如下方程组解的方法：(mod m1 )(mod m2 ).x an(mod mn )其中 m1 , m2 , . . . , mn 两两互素。江凡问题求解选讲August 10, 2016同余方程与中国剩余定理数论基础中国剩余定理首先来解只有两个

10、方程的方程组。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是该方程组的一个解，那么该方程组的所有解都满足如下形式：江凡问题求解选讲August 10, 2016x x0(mod m1 m2 )这样我们相当于把刚刚的两个方程合并成为了一个方程。如果有多个方程，可以不断进行这样的合并，最后就可以解出结果了。x

11、2x 2数论基础同余方程与中国剩余定理中国剩余定理我们来拿刚刚开头的例子来试着算一算。那个方程组是：x 3(mod 3)(mod 5)(mod 7)江凡问题求解选讲August 10, 2016首先来合并前两个方程，联立后得到的线性方程是 2 + 3k1 = 3 + 5k2 ，整理后可以得到一组解是 k1 = 2, k2 = 1，这样可以得到满足前两个方程的 x 都满足：x 8 (mod 15)数论基础同余方程与中国剩余定理中国剩余定理之后可以得到新的方程组：xx 8 2(mod 15)(mod 7)再合并两个方程，联立后得到的线性方程是 8 + 15k1 = 2 + 7k2 ，整理后可以得到

12、一组解是 k1 = 1, k2 = 3，这样可以得到满足这两个方程的 x 都满足：x 23(mod 105)这便是最后的解了！江凡问题求解选讲August 10, 2016数论基础素数及基本知识江凡问题求解选讲August 10, 2016素数及基本知识素数是只含有 1 及其本身两个正因子的数，也称为质数。如果还有其它正因子的话，那么这个数就被称为合数。注意 1 并非素数，亦非合数。我在这里介绍一个关于素数的定理，它们在算法复杂度分析中或许会用到：Theorem (素数定理)当 x 很大时，小于 x 的素数个数近似等于x/lnx数论基础江凡问题求解选讲August 10, 2016素数的判定

13、如何判定一个数 m 是不是素数，我们可以直接从定义出发，从 2 开始到m-1 为止，检测是否有一个数整除 m，如果没有，那么这个数就是素数。 例6，求105内的所有素数。 Eratosthenes 筛法筛法是一种用来求素数的方法，它的思路比较简单。 由于每个合数都可以被分解成几个素数的乘积，如果我们将所有素数的倍数都删去，那么剩下的就是素数了。 因此，我们可以从 2 开始，先将 2 的所有倍数都删去。然后往下找到第一个没有被删去的数，这个数一定是素数，再将这个数的所有倍数都删去，不断进行这个操作。素数及基本知识 线性筛法线性筛法，又称欧拉筛法。 避免冗余的运算。每个合数必有一个最大因子（不包括

14、它本身） ，用这个因子把合数筛掉。 对于每一个数i，乘上小于等于i的最小素因数的素数，就得到以i为最大因数的合数。设有一个数t，只要将所有以比t小的数为最大因数的合数筛去，那么比t小的数里剩下的就只有素数了。组合数学基础排列组合 组合数学基础 例7，在1与106之间，有多少个整数的各位数字之和等于9？江凡问题求解选讲August 10, 2016组合数学基础排列组合 排列 现在来考虑一个问题：你需要在 n 个不同的人里面选出 m 个人排成一行，问有多少种排列方案？ n(n 1)(n 2) (n m + 1)这个数通常被成为排列，记成 ，或者 。 如果我们定义一种名为阶乘的运算：n!= 1 2

15、3 n特别地，当 n = 0 时，0! = 1。那么这个数就可以简单地写成：Anm=n!(n m)!江凡问题求解选讲August 10, 2016AnmP nm组合数学基础排列组合 排列 圆排列圆排列 （1）由 的个元素中，每次取出r个元素排在一个圆环上，叫做一个圆排列（或叫环状排列）。 （2）圆排列有三个特点：（i）无头无尾；（ii）按照同一方向转换后仍是同一排列；（iii）两个圆排列只有在元素不同或者元素虽然相同，但元素之间的顺序不同，才是不同的圆排列。 （3）定理：在的个元素中，每次取出个不同的元素进行圆排列，圆排列数为 。 不尽相异元素的全排列不尽相异元素的全排列 如果n个元素中，有p

16、1个元素相同，又有p2个元素相同，又有ps个元素相同（ ），这个n元素全部取的排列叫做不尽相异的n个元素的全排列，它的排列数是 。江凡问题求解选讲August 10, 2016rPrn!21spppn,321naaaaAnppps21组合数学基础排列组合组合研究无次序的选取问题。把前述排列问题改成：你只需要在 n 个不同的人里面选出 m 个人，问有多少种方案？ 如果我们选出来 m 个人后，再将他们排成一队，那么方案数就是先前的排列数 。 但是这样的计数会出现很多的重复，也就是每次我们都多算了将 m 个人排成一队的方案数，那么这个数是什么呢？ 它就是 ，或者说 m!。 那么由于每种方案都被重复计

17、算了 m! 次，我们只要将 除以 m! 就可以得到组合数的公式了！江凡问题求解选讲August 10, 2016AnmAmmAnmCnm=nAm!=n!m!(n m)!m排列组合组合数学基础组合数的基本性质首先第一个性质就是先前的递推关系(1)此外，直接根据通项可以得到一个对称的性质：(2)江凡问题求解选讲August 10, 2016Cnm= Cn1 + Cn1mm-1Cnm= Cnn-m排列组合组合数学基础排列组合分析原理江凡问题求解选讲August 10, 2016 加法原理 如果完成一件事情有n种方式A1，An，每种方式中又有mi种方法（1in），且Ai Aj= ，则要完成此事共有 ，

18、即n1iimN12nNmmm 乘法原理 如果完成一件事情要分几个步骤B1 ，B2 ， ，Bn ，而每个步骤Bi有mi种方法(1in) ，那么完成这事共有 ，即n1iimN12nNmmm7名学生站成一排，甲、乙必须站在一起有多少不同排法？（ ）7名学生站成一排，甲乙互不相邻有多少不同排法？ （ ） 我们班里有43位同学,从中任抽5人,正、副班长、团支部书记至少有一人在内的抽法有多少种? （ ）某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插法的种数为（ ）（ ） A42 B30 C20 D12 从黄瓜、白菜、油菜、扁豆4种蔬菜品种中选

19、出3种，分别种在不同土质的三块土地上，其中黄瓜必须种植，不同的种植方法共有（ ）（ ） 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。在任何时候，小陈只能专

20、心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如a2-b2-a3-b3是合法的，而a2-b3-a3-b2是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有 种。排列组合+加法原理:B任务中的b1一定做，而且肯定是第一个做的。除了b1外，第一类：完成A任务 只有1种。第二类：完成A任务和b2 有 种。第三类：完成A任务和b2、b3 有 种。第四类：完成

21、A任务和b2、b3、b4 有 种。第五类：完成A任务和b2、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，有多少正整数解？解：与前面

22、例子相似，但x、y、z、w不能等0。即知 有 个正整数解。江凡问题求解选讲August 10, 20161n1kC154032214123CC递推递归Contents归纳推理数论基础递推递归递推递归数据结构其他江凡问题求解选讲August 10, 201612345递推递推递归江凡问题求解选讲August 10, 2016 给定一个数的序列H0,H1,Hn,若存在整数n0，使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0i0n0），求出铺法总数的递推公式。），求出铺法总数的递推公式。 对给出的任意一个对给出的任意一个n（n0），用），用F（n）表示其铺）表示其铺法的总

23、数的递推公式为法的总数的递推公式为: 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（1）1 F（2）2 F（3）4F（N）F（N3）F（N

24、2）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递推江凡问题求解选讲August 10, 2016递推递归设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭

25、曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。12132412346578图21234567108911121314n=1n=2n=3n=4递推江凡问题求解选讲August 10, 2016递推递归在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案(图3)，故h5=5。求对于一个任意的凸n边形相应的hn。 图3112inniiCC递推江凡问题求解选讲August 10, 2016递推递归错排问题（经典问题）。 n个数，分别为1n，排成一个长度为n的排列。若每一个数的位置都与数的

26、本身不相等，则称这个排列是一个错排。例如，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)(2,3,4,1)它们有什么规律呢？递归江凡问题求解选讲August 10, 2016递推递归通过反复的试验，我们发现事实上有两种方式产生错位排列： A.将k与(

27、1，2，k1)的某一个数互换，其他k2个数进行错排，这样可以得到(k1)W(k-2)个错位排列。 B.另一部分是将前k1个元素的每一个错位排列（有W(k-1)个）中的每一个数与k互换，这样可以得到剩下的(k1)W(k-1) 个错位排列。根据加法原理，我们得到求错位排列的递推公式W(k):传球问题江凡问题求解选讲August 10, 2016其他4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？传球问题江凡问题求解选讲August 10, 2016其他传球问题江凡问题求解选讲August 10, 20

28、16其他设有棱长为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。传球问题江凡问题求解选讲Augu

29、st 10, 2016其他 一个学生暑假在A、B、C三个城市游览。他今天在这个城市，明天就到另一个城市。假设他第一天在A市，第五天又回到A市，问他有几种不同的游览方案？ 递归江凡问题求解选讲August 10, 2016递推递归 一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。 递归过程是借助于一个递归工作栈来实现的 问题向一极推进，这一过程叫做递推； 而问题逐一解决，最后回到原问题，这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。例，用递归算法求n的阶乘，记n!定义：函数 fact( n ) = n! fa

30、ct( n-1 ) = ( n-1 )! 则有 fact( n ) = n * fact( n-1 ) 已知 fact( 1 ) = 1递归江凡问题求解选讲August 10, 2016下面画出了调用和返回的递归示意图 Bfact(2)fact(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，最

31、短的走法共有多少种？_ 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递归江凡问题求解选讲August 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),(3

32、4)，(13),(24)，(14),(23)。 当n=6，r=3时，S(6,3)=_。 9090递归江凡问题求解选讲August 10, 2016递推递归对任一元素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的每一种加入方

33、式，都可以使集合划分为r个子集。因此根据乘法原理，划分数共有r r* *s(n-1,r)s(n-1,r)。递归江凡问题求解选讲August 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 32451 34251 32415 32154 35421 32541如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列