数学知识和相关算法

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数学知识和相关算法,【 排列与组合】,一、加法原理和乘法原理,1.加法原理：,完成一件事，有n类办法，在第i(i=1,2,n)类办法中有m,i,种不同的方法，那么完成这件事共有 N=m,1,+m,2,+m,n,种不同的方法。,又称为分,类,计数原理,2.乘法原理：,完成一件事，需要分成n个步骤，做第i(i=1,2,n)步有m,i,种不同的方法，那么完成这件事有 N=m,1,*m,2,*.*m,n,种不同的方法。,又称为分,步,计数原理,3.两个原理的区别：,加法原理是“分类完成”，每一类办法中的任何一种方法都可以完成这件事；乘法原理是“分步完成”，只有完成各个步骤才可以做完这件事，这是必须要分清的。,【问题分析】,（1）从书架上任取一本书，有3类办法：,第一类办法：从第一层取1本数学书，有5种方法，即m,1,=5；,第二类办法：从第二层取1本语文书，有3种方法，即m,2,=3；,第三类办法：从第三层取1本英语书，有6种方法，即m,3,=6；,根据加法原理，共有不同取法：N= m,1,+m,2,+m,3,=14,（2）在书架的每一层各取1本书，就需要把完成取书任务分成三个步骤：,第一步：从第一层取1本数学书，m,1,=5；,第二步：从第二层取1本语文书，m,2,=3；,第三步：从第三层取1本英语书，m,3,=6；,当三个步骤全部做完时，即结束取书工作，不同取法：N= m,1,*m,2,*m,3,=90,例,1.,书架上第一层有,5,本不同的数学书，第二层上有,3,本不同的语文书，第三层上有,6,本不同的英语书。,（,1,）从书架上任取一本书，有多少种方法？,（,2,）从书架上的第一、二、三层各取一本书，有多少种不同的取法？,二、排列、组合的概念及计算公式,1. 排列：,从n个不同元素中任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个,排列,。,从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的,排列数,，用符号 或A(n,m)表示，,则,当m=n时为,全排列,公式：,假如元素可以重复选取，称为,可重复的排列,，种数为：,假如元素排成一个圆圈，称为,循环排列,，种数为：,（规定0!=1）,m个,n,nn=n,m,2. 组合：,从n个不同元素中任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个,组合,。,从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个元素中取出m个元素的,组合数,，用符号 或C(n,m)表示，,则,其中,排列与元素的顺序有关，而组合与顺序无关。,例,2.,从,1,，,2,，,3,这,3,个数字中，每次取出,2,个，有多少种排列方法？写出所有不同的排列。,【,问题分析,】,将这,3,个数字每次从中取出,2,个，可以分作两个步骤完成：,第一步：先确定十位数，在,1,，,2,，,3,中任取一个，有,3,种方法；,第二步：再确定个位数，当十位数确定后，只能从余下的,2,个数字中任取一个，有,2,种方法。,根据乘法原理，共有,32=6,种方法。,用排列数的计算方法，即从,3,个不同元素中取出,2,个元素的所有排列的个数，用 表示，即,例,3.,甲、乙、丙三个人见面，每两个人相互握手，求握手的总数。,【,问题分析,】,甲与乙握手和乙与甲握手计为,1,次握手，因此用组合数的计算方法，即从,3,个不同元素中取出,2,个元素合成一组，则,甲乙丙乙丙,练习一：,七（,1,）班共有学生,60,名，从中选出,2,人分别担任班长和副班长，共有多少种选法？,某项比赛一共有,14,队参加，每队都要与其余各队在主、客场分别比赛一次，共进行多少场比赛？,5,个人站成一排照相，共有多少种不同的排列方法？,5,个人站成一排照相，其中甲乙二人必须相邻，共有多少种不同的排法？,数字,0,1,2,3,4,5,共能组成多少个三位数（各位上的数字可重复）？,数字,0,1,2,3,4,5,共能组成多少个三位数（各位上的数字不可重复）？,在圆形花坛外侧摆放,8,盆菊花和,4,盆蝴蝶兰，要求蝴蝶兰不能相邻摆放，一共有多少种摆法？,一元、五元、十元、五十元人民币各一张，共可以组成多少种币值？,三、解决排列组合综合性问题的一般过程：,1. 认真审题，弄清要做什么事；,2. 怎样做才能完成所要做的事，即采取分步还是分类，还是分步和分类同时进行，确定分多少步和分多少类；,3. 确定每一步或每一类是排列（有序）问题，还是组合（无序）问题，元素总数是多少，取多少个元素；,4. 是否限定元素的选择，是否限定元素的位置。,例,4,从1,，,2,，,3,，,，,20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有,多少,个,。,【,问题,分析,】,首先要把复杂的生活背景或其它数学背景转化为一个明确的排列组合问题。,设,：,a,b,c成等差，,则,2b=a+c, 可知b由a,c决定,又 2b是偶数, a,c同奇或同偶,即分别从1，3，5，19或2，4，6，8，20这十个数中选出两个数进行排列,。,则：,C,(,2,10,),*2*,A(,2,2,)=,180。,2分析是分类还是分步，是排列还是组合,例,5,在一块并排的,10,垄田地中，选择二垄分别种植,A,，,B,两种作物，每种种植一垄，为有利于作物生长，要求,A,，,B,两种作物的间隔不少于,6,垄，不同的选法共有多少种。,【,问题分析,】,采取分类的方法。,第一类：,A,在第一垄，,B,有,3,种选择；,第二类：,A,在第二垄，,B,有,2,种选择；,第三类：,A,在第三垄，,B,有,1,种选择。,同理,A,、,B,位置互换 ，共,12,种。,例,6,从,6,双不同颜色的手套中任取,4,只，其中恰好有一双同色的取法有多少种？,【,问题分析,】,显然本题应分步解决。,从,6,双中选出一双同色的手套，有,6,种方法；,从剩下的十只手套中任选一只，有,10,种方法；,从除前所涉及的两双手套之外的八只手套中任选一只，有,8,种方法；,由于选取与顺序无关，因中的选法重复一次，因而共,240,种。,例,7,身高互不相同的,6,个人排成,2,横行,3,纵列，在第一行的每一个人都比他同列的身后的人个子矮，则所有不同的排法种数为多少种。,【,问题分析,】,每一纵列中的两人只要选定，则他们只有一种站位方法，因而每一纵列的排队方法只与人的选法有关系，共有三纵列。,因而共有,C(6,2)*C(4,2)*C(2,2)=90,种。,例,8,在,11,名工人中，有,5,人只能当钳工，,4,人只能当车工，另外,2,人能当钳工也能当车工。现从,11,人中选出,4,人当钳工，,4,人当车工，问共有多少种不同的选法,?,【,问题分析,】,采用加法原理首先要做到分类不重不漏，如何做到这一点？分类的标准必须前后统一。,以两个全能的工人为分类的对象，考虑以他们当中有几个去当钳工为分类标准。,第一类,:,这两个人都去当钳工，则从,5,名钳工中选,2,人，有,C(5,2)=10,种；,第二类,:,这两人有一个去当钳工，则从,5,名钳工中选,3,人，,4,名车工,+1,名全能工中选,4,人，有,C(5,3)*C(5,4)*2=100,种；,第三类,:,这两人都不去当钳工，有,C(5,4)*(C(6,4)+C(5,4)*2)=75,种。,因而共有,185,种。,例,9,现有印着,0,，,1,，,3,，,5,，,7,，,9,的六张卡片，如果允许,9,可以当作,6,用，那么从中任意抽出三张可以组成多少个不同的三位数？,【,问题分析,】,有同学认为只要把,0,，,1,，,3,，,5,，,7,，,9,的排法数乘以,2,即为所求，但实际上抽出的三个数中有,9,的话才可能用,6,替换，因而必须分类。,抽出的三数含,0,，含,9,，有,C(4,1)*(A(3,3)-2)*2=32,种方法；,抽出的三数含,0,不含,9,，有,C(4,2)*(A(3,3)-2)=24,种方法；,抽出的三数含,9,不含,0,，有,C(4,2)*2*A(3,3)=72,种方法；,抽出的三数不含,9,也不含,0,，有,C(4,3)*A(3,3)=24,种方法。,因此共有,32+24+72+24=152,种方法。,例,10,停车场划一排,12,个停车位置，今有,8,辆车需要停放，要求空车位连在一起，不同的停车方法是多少种？,【,问题分析,】,可以把空车位看成一个元素，和,8,辆车共九个元素排列，,因而共有,A(9,8)=362880,种停车方法。,3特殊优先：特殊元素，优先处理；特殊位置，优先考虑,例,11,六人站成一排，求：,（,1,）甲不在排头，乙不在排尾的排列数。,（,2,）甲不在排头，乙不在排尾，且甲乙不相邻的排法数。,【,问题分析,】,（,1,）先考虑排头，排尾，但这两个要求相互有影响，因而考虑分类。,第一类：乙在排头，有,A(5,5),种站法；,第二类：乙不在排头，当然他也不能在排尾，有,4X4XA(4,4),种站法。,共,A(5,5)+4X4XA(4,4),种站法。,（,2,）,第一类：甲在排尾，乙在排头，有,A(4,4),种方法；,第二类：甲在排尾，乙不在排头，有,3XA(4,4),种方法；,第三类：乙在排头，甲不在排头，有,4XA(4,4),种方法,第四类：甲不在排尾，乙不在排头，有,A(3,3)XA(4,4),种方法。,共,A(4,4)+3XA(4,4)+4XA(4,4)+A(3,3)XA(4,4)=312,种。,例,12,对某件产品的,6,件不同正品和,4,件不同次品进行一一测试，直到区分出所有次品为止。若所有次品恰好在第五次测试时被全部发现，则这样的测试方法有多少种可能,?,【,问题分析,】,本题指第五次测试的产品一定是次品，并且是最后一个次品，因而第五次测试应算是特殊位置了，分步完成。,第一步：第五次测试的有,C(4,1),种可能；,第二步：前四次有一件正品有,C(6,1),中可能；,第三步：前四次有,A(4,4),种可能。,共有,C(4,1)*C(6,1)*A(4,4)=576,种可能。,4捆绑与插空,例,13. 8,人排成一队：,（,1,）甲乙必须相邻,（,2,）甲乙不相邻,（,3,）甲乙必须相邻且与丙不相邻,（,4,）甲乙必须相邻，丙丁必须相邻,（,5,）甲乙不相邻，丙丁不相邻,【,问题分析,】,（,1,）甲乙必须相邻，就是把甲乙捆绑（甲乙可交换）和,7,人排列，则,A(7,7)*2,；,（,2,）甲乙不相邻，,A(8,8)-A(7,7)*2,；,（,3,）甲乙必须相邻且与丙不相邻，先求甲乙必须相邻且与丙相邻,A(6,6)*2*2,；,甲乙必须相邻且与丙不相邻,A(7,7)*2-A(6,6)*2*2,；,（,4,）甲乙必须相邻，丙丁必须相邻,A(6,6)*2*2,；,（,5,）甲乙不相邻，丙丁不相邻，,A(8,8)-(A(7,7)*2*2+A(6,6)*2*2),。,例,14.,某人射击,8,枪，命中,4,枪，恰好有三枪连续命中，有多少种不同的情况？,【,问题分析,】,连续命中的三枪与单独命中的一枪不能相邻，因而这是一个插空问题。另外没有命中的之间没有区别，不必计数。即在四发空枪之间形成的,5,个空中选出,2,个的排列，即,A(5,2),。,例,15.,马路上有编号为,1,，,2,，,3,，,，,10,十个路灯，为节约用电又看清路面，可以把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，在两端的灯也不能关掉的情况下，求满足条件的关灯方法共有多少种？,【,问题分析,】,即关掉的灯不能相邻，也不能在两端。又因为灯与灯之间没有区别，因而问题简化为在,7,盏亮着的灯形成的不包含两端的,6,个空中选出,3,个空放置熄灭的灯。 共,C(6,3)=20,种方法。,5间接计数法（1）排除法,例,16.,三行三列共九个点，以这些点为顶点可组成多少个三角形？,【,问题分析,】,有些问题正面求解有一定困难，可以采用间接法。,所求问题的方法数,=,任意三个点的组合数,-,共线三点的方法数，,共,C(9,3)-8,种。,例,17,正方体,8,个顶点中取出,4,个，可组成多少个四面体？,【,问题分析,】,所求问题的方法数,=,任意选四点的组合数,-,共面四点的方法数，,共,C(8,4)-12=70-12=58,个。,例,18.,三个相同的红球和两个不同的白球排成一行，共有多少种不同的方法？,【,问题分析,】,先认为三个红球互不相同，共种,A(5,5)=120,方法。,而由于三个红球所占位置相同的情况下，共有,A(3,3)=6,变化，,因而共,A(5,5)/A(3,3)=20,种。,例,19. 6,人排成一排，要求甲在乙的前面（不一定相邻），共有多少种不同的方法,?,如果要求甲乙丙按从左到右依次排列呢？,【,问题分析,】,方法一：实际上，甲在乙的前面和甲在乙的后面两种情况对称，具有相同的排法数。因而有,2*A(6,2)=360,种。,方法二：先考虑六人全排列，其次甲乙丙三人实际上只能按照一种顺序站位，因而前面的排法数重复了,3,种，,共,=120,种。,例,20,5,男,4,女排成一排，要求男生必须按从高到矮的顺序，共有多少种不同的方法？,【,问题分析,】,首先不考虑男生的站位要求，共,A(9,9),种；,男生从左至右按从高到矮的顺序，只有一种站法，因而上述站法重复了次。因而有,=9876=3024,种；,男生从右至左按从高到矮的顺序，只有一种站法，同理也有,3024,种；,综上，有,6048,种。,6挡板的使用,例,21,10,个名额分配到八个班，每班至少一个名额，问有多少种不同的分配方法？,【,问题分析,】,把,10,个名额看成十个元素，在这十个元素之间形成的九个空中，选出七个位置放置档板，则每一种放置方式就相当于一种分配方式。因而共,36,种。,7注意排列组合的区别与联系：所有的排列都可以看作是先取组合，再做全排列；同样，组合如补充一个阶段(排序)可转化为排列问题。,例,22.,从,0,，,1,，,2,，,，,9,中取出,2,个偶数数字，,3,个奇数数字，可组成多少个无重复数字的五位数？,【,问题分析,】,先选后排。另外还要考虑特殊元素,0,的选取。,两个选出的偶数含,0,，则有,C(4,1)*C(5,3)*(A(5,5)-A(4,4),种。,两个选出的偶数字不含,0,，则有,C(4,2)*C(5,3)*A(5,5),种。,例,23.,电梯有,7,位乘客，在,10,层楼房的每一层停留，如果三位乘客从同一层出去，另外两位在同一层出去，最后两人各从不同的楼层出去，有多少种不同的下楼方法？,【,问题分析,】,先把,7,位乘客分成,3,人,2,人,1,人,1,人四组，有,C(7,3)*C(4,2)*C(2,1),种。,选择,10,层中的四层下楼有,C(10,4),种。,共有,C(7,3)*C(4,2)*C(2,1)*C(10,4)*A(4,4),种。,例,24.,用数字,0,，,1,，,2,，,3,，,4,，,5,组成没有重复数字的四位数：,（,1,）可组成多少个不同的四位数？,（,2,）可组成多少个不同的四位偶数？,（,3,）可组成多少个能被,3,整除的四位数？,（,4,）将（,1,）中的四位数按从小到大顺序排列，第,85,项是什么？,【,问题分析,】,（,1,）有,A(6,4)-A(5,3),个,（,2,）分为两类：,0,在末位，则有,C(5,3)*A(3,3)=60,种；,0,不在末位，则,C(2,1)*C(4,1)*C(4,2)*A(2,2)=96,种，共,156,种。,（,3,）先把四个相加能被,3,整除的四个数从小到大列举出来，即先选,0,1,2,3,；,0,1,3,5,；,0,2,3,4,；,0,3,4,5,；,1,2,4,5,；它们排列出来的数一定可以被,3,整除，再排列，有,4(A(4,4)-A(3,3)+A(4,4)=96,种。,（,4,）首位为,1,的有,=60,个；前两位为,20,的有,=12,个；前两位为,21,的有,=12,个；因而第,85,项是前两位为,23,的最小数，即为,2301,。,8分组问题,例,25. 6,本不同的书：,（,1,）分给甲乙丙三人，每人两本，有多少种不同的分法？,（,2,）分成三堆，每堆两本，有多少种不同的分法？,（,3,）分成三堆，一堆一本，一堆两本，一堆三本，有多少种不同的分法？,（,4,）甲一本，乙两本，丙三本，有多少种不同的分法？,（,5,）分给甲乙丙三人，其中一人一本，一人两本，第三人三本，有多少种不同的分法？,【,问题分析,】,（,1,）甲拿书的可能性,6*5/2=15,；乙,4*3/2=6,；丙,2*1/2=1,，则得,15*6*1=90,种。,（,2,）即在（,1,）的基础上除去顺序,A(3,3),，有,15,种。,（,3,）有,C(6.1)*C(5.2)*C(3.3)=60,种。由于这是不平均分组，因而不包含顺序。,（,4,）甲,6,；乙,5*4/2=10,；丙,3*2*1/2=3,；则,6*10*3=180,种。,（,5,）有,180*A(3,3)=1080,种。,例,26. 5,名学生分配到,4,个不同的科技小组参加活动，每个科技小组至少有一名学生参加，则分配方法共有多少种？,【,问题分析,】,先把,5,个学生分成二人，一人，一人，一人各一组，其中涉及到平均分成四组，有,C(5,3),种分组方法。可以看成,5,个元素三个板不空的隔板法；,再考虑分配到四个不同的科技小组，有,A(4,4),种；,由 可知，共,=240,种。,小结：,互斥分类分类法,先后有序位置法,反面明了排除法,相邻排列捆绑法,分隔排列插空法,四、排列与组合的算法,1. 排列的算法：,当元素数目n较小时，可采用穷举法计算排列总数，并输出所有不同的排列；当元素数目n较大时，用穷举法需要占用较大的空间甚至内存无法完成。,为了求出元素1，2，3，n的所有不同的排列，制定如下算法：,（1）,写出从小到大的初始排列，在每个数上方加上向左的箭头，,即1 2 n，,若某元素在箭头所指的方向上存在数值比它小的数，则认定该元素为活动元素，找出,当前最大的活动元素d,；,（2）令最大活动元素d沿箭头方向前进一步，即交换一次数据得到一个新排列；,（3）改变比最大活动元素d大的所有元素的箭头方向；,（4）反复执行（2）、（3）步，直到数列中没有活动元素为止,。,用数组p1.n表示排列p1,p2,pn；d1.n表示最大活动元素在排列中的位置变化；e1.n表示箭头方向数据，用“-1”表示左箭头，“1”表示右箭头。,例如n=4的前5组数据为：,p1.4,d1.4,e1.4,1 2 3 4,1 2 3 4,-1 -1 -1 -1,1 2 4 3,1 2 3 3,-1 -1 -1 -1,1 4 2 3,1 2 3 2,-1 -1 -1 -1,4 1 2 3,1 2 3 1,-1 -1 -1 -1,4 1 3 2,1 2 2 0,-1 -1 -1 1,从数组d1.n中d4的变化，可以看出最大活动元素4从p4(d4=4)的位置连续变换到p1(d4=1)位置，然后成为不活动元素(d4=0)。这时3成为最大活动元素，d3由3变为2表示向左交换一次，同时e4由-1变为1，表示元素4上面的箭头由向左变成向右。,【排列算法程序清单】,方法：递归，深度优先产生。,const m=4;var a:array1.m of integer ; b:array1.m of boolean;procedure print;var i:integer;begin for i:=1 to m do write(ai);writeln;end;,procedure tr(dep:integer);var i:integer;begin for i:=1 to m do if bi then begin adep:=i; bi:=false; if dep=m then print else tr(dep+1); bi:=true; end;end;beginfillchar(b,sizeof(b),true);tr(1);end.,beginfor i:=1 to m do ai:=i;repeat print; i:=m-1; while (i0) and (aiai+1) do i:=i-1; if i0 then begin j:=m; while ajai do j:=j-1; temp:=ai;ai:=aj;aj:=temp; k:=i+1;l:=m; while k0) and (ai=n-(m-i) do dec(i); if i0 then begin ai:=ai+1; for j:=i+1 to m do aj:=aj-1+1; end; until i=0;end.,【数列及递推】,1.算术序列：,每一项比前一项大一个,常数d,。,若初始项为h,0,，递推关系式为,h,n,=h,n-1,+d=h,0,+nd,对应的各项为：h,0,h,0,+d,h,0,+2d,.,h,0,+nd,前n项的和为(n+1)h,0,+dn(n+1)/2,如：1,2,3,.和1,3,5,7.等都是算术序列。,：每一项是前面一项的,常数q倍,。,若初始项为h,0,，递推关系为,h,n,=h,0,q,n-1,q=h,0,q,n,对应的各项为：h,0,h,0,q,1,h,0,q,2,.,h,0,q,n,前n项的和为(q,n+1,-1)/(q-1)h,0,如：1,2,4,8,16,. 和5,15,45,135,.等都是几何序列。,序列：,除第一、二项外每一项是它前两项的和。,若首项为f,0,为0，递推关系为,f,n,=f,n-1,+f,n-2,(n=2),对应的序列为：0,1,1,2,3,5,8.,前n项的和,S,n,=f,0,+f,1,+f,2,+.+f,n,=f,n+2,-1,例：,（1）楼梯有n阶台阶，上楼可以一步上1阶，也可以一步上2阶，编一程序计算共有多少种不同的走法?,（2）有一对雌雄兔，每两个月就繁殖雌雄各一对兔子。问n个月后共有多少对兔子?,（3）有n*2的一个长方形方格，用一个1*2的骨牌铺满方格。求铺法总数？,递推公式是：d,n,=(n-1)(d,n-2,+d,n-1,)=nd,n-1,+(-1),n-2,例：在书架上放有编号为1,2,.n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。,如：n=3时，原来位置为123，放回去时只能为312或231这两种。,求当n=5时满足以上条件的放法共有多少种？,1,2,3,.,n的错位排列为i,1,i,2,.i,n,使得i,1,1,i,2,2,i,3,3,.i,n,n,错位排列种数为0,1,2,9,44,265,.(n=1,2,3,),直线分平面的最大区域数的序列为：2,4,7,11,.,递推公式是：,f,n,=f,n-1,+n=n(n+1)/2+1,折线分平面的最大区域数的序列为： 2,7,16,29, .,递推公式是：,f,n,=(n-1)(2n-1)+2n,封闭曲线（如一般位置上的圆）分平面的最大区域数的序列为：2,4,8,14,.,递推公式是：,f,n,=f,n-1,+2(n-1)=n,2,-n+2,6.Catalan 数列：,n个+1和n个-1构成2n项a,1,a,2,.,a,2n,，其部分和满足a,1,+a,2,+.+a,k,=0(k=1,2,3,.,2n),该数列为,Cn=C(2k,k)/(k+1)(k=0),对应的序列为,1,1,2,5,14,42,132,例：将一个凸多边形区域分成三角形区域的方法数?,令h,n,表示具有n+1条边的凸多边形区域分成三角形的方法数。同时令h,1,=1，则h,n,满足递推关系h,n,=h,1,h,n-1,+h,2,h,n-2,+.+h,n-1,h,1,(n=2)（想一想为什么？）,该递推关系的解为h,n,=C(2n-2,n-1)/n(n=1,2,3,.)，其对应的序列为1,1,2,5,14,42,132,.从第二项开始分别是三边形,四边形,.的分法数。,即k边形分成三角形的方法数为h,k,=C(2k-4,k-2)/(k-1)(k=3)。,练习题：,（1）有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？,（2）一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。若她从不穿越（但可以碰到）从家到办公室的对角线，则有多少条可能的道路？,（3）在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?,（4）n个结点可够造多少个不同的二叉树?,（5）一个栈(无穷大)的进栈序列为1,2,3,.n,有多少个不同的出栈序列?,【计算几何】,一、关于平面上点和直线的若干公式：,1.两点间的距离公式：,已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则P1和P2两点间的距离为,d=sqrt(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),2.线段的中点坐标公式：,已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2)，则线段P1P2的中点坐标为,x=(x1+x2)/2,y=(y1+y2)/2,3.直线的斜率公式：,已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2),则线段P1P2所在的直线的斜率为,k=(y2-y1)/(x2-x1),4.直线的点斜式方程:,已知：直线过点P0(x0,y0)，斜率为k,则该直线所在的方程为,y=,k(x-x0)+y0=kx+y0-kx0=,kx+b,(与y轴交点的纵坐标:纵截距),二、线段的相交判断,1.叉积,已知：平面上的两点的直角坐标分别为p1(x1,y1),p2(x2,y2)，则,（1）该两点相对坐标原点(0,0)的叉积为,m=x1*y2-x2*y1,若m0 则相对坐标原点,点p1在点p2的顺时针方向；,若m0 则相对p0点,点p1在点p2的顺时针方向；,若m0 则p1点向左拐；,若mb then max:=a else max:=b;,end;,function min(a,b:real):real;,begin,if a=min(p3.x,p4.x) and,(max(p3.x,p4.x)=min(p1.x,p2.x) and,(max(p1.y,p2.y)=min(p3.y,p4.y) and,(max(p3.y, p4.y)=min(p1.y,p2.y) and,(m(p2,p3,p1)*m(p2,p4,p1)0) and,(m(p4,p1,p3)*m(p4,p2,p3)0),then across:=true,else across:=false;,end;,begin,readln(p1.x,p1.y,p2.x,p2.y);,readln(p3.x,p3.y,p4.x,p4.y);,if across(p1,p2,p3,p4),then writeln(yes),else writeln(no);,end.,