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

递推 江凡 问题求解选讲 August 10, 2016 递推递归 递推——平面分割问题 例17．设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。 1 2 1 3 2 4 1 2 3 4 6 5 7 8 图2 1 2 3 4 5 6 7 10 8 9 11 12 13 14 n=1 n=2 n=3 n=4 递推关系：an=an-1+2(n-1) 边界条件：a1=2 递推 江凡 问题求解选讲 August 10, 2016 递推递归 递推——Catalan数 例18．在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用hn表之，hn即为Catalan数。例如五边形有如下五种拆分方案(图3)，故h5=5。求对于一个任意的凸n边形相应的hn。 图3 边界条件：C2=1 递推 江凡 问题求解选讲 August 10, 2016 递推递归 递推的应用——组合计数 例19．错排问题（经典问题）。 n个数，分别为1~n，排成一个长度为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) (2,3,4,1) 它们有什么规律呢？ 递归 江凡 问题求解选讲 August 10, 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)] 传球问题 江凡 问题求解选讲 August 10, 2016 其他 传球问题 例20．4个人进行篮球训练，互相传球接球，要求每个人接球后马上传给别人，开始由甲发球，并作为第一次传球，第五次传球后，球又回到甲手中，问有多少种传球方式？ 传球问题 江凡 问题求解选讲 August 10, 2016 其他 传球问题 传球问题 江凡 问题求解选讲 August 10, 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。 传球问题 江凡 问题求解选讲 August 10, 2016 其他 传球问题应用 练习：一个学生暑假在A、B、C三个城市游览。他今天在这个城市，明天就到另一个城市。假设他第一天在A市，第五天又回到A市，问他有几种不同的游览方案？ 递归 江凡 问题求解选讲 August 10, 2016 递推递归 递归的概念与基本思想 一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。 递归过程是借助于一个递归工作栈来实现的 问题向一极推进，这一过程叫做递推； 而问题逐一解决，最后回到原问题，这一过程叫做回归。 递归的过程正是由递推和回归两个过程组成。 例，用递归算法求n的阶乘，记n! 定义：函数 fact( n ) = n! fact( n-1 ) = ( n-1 )! 则有 fact( n ) = n * fact( n-1 ) 已知 fact( 1 ) = 1 递归 江凡 问题求解选讲 August 10, 2016 下面画出了调用和返回的递归示意图 递推递归 递归的概念与基本