网站设计作业平台,家具展示网站源码,做1688网站到哪里找图片,爬虫网站开发定义#xff1a;给定一个数的序列H0,H1,…,Hn,…若存在整数n0#xff0c;使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0in)联系起来#xff0c;这样的式子就叫做递推关系。 递推关系中存在着三大基本问题#xff1a;如何建立递推关系#xff0c;已…定义给定一个数的序列H0,H1,…,Hn,…若存在整数n0使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hn(0in)联系起来这样的式子就叫做递推关系。 递推关系中存在着三大基本问题如何建立递推关系已给的递推关系有何性质以及如何求解递推关系。 五种基本的递推关系 Ⅰ.Fibonacci数列 在所有的递推关系中Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中Fibonacci数列类的题目因为解法相对容易一些逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值恰恰相反一些此类的题目还是能给我们一定的启发的。 Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。 问题的提出有雌雄一对兔子假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子 解设满x个月共有兔子Fx对其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Ox对。则 FxNxOx 而 OxFx-1 NxOx-1Fx-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力了) ∴ FxFx-1Fx-2 边界条件 F00F11 由上面的递推关系可依次得到 F2F1F01F3F2F12F4F3F23F5F4F35……。 Fabonacci数列常出现在比较简单的组合计数问题中例如以前的竞赛中出现的“骨牌覆盖”[1]问题、下文中的『例题1』等都可以用这种方法来解决。在优选法[2]中Fibonacci数列的用处也得到了较好的体现。 Ⅱ.Hanoi塔问题 问题的提出Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时这n个圆盘由大到小依次套在a柱上如图1所示。 要求把a柱上n个圆盘按下述规则移到c柱上 (1)一次只能移一个圆盘 (2)圆盘只能在三个柱上存放 (3)在移动过程中不允许大盘压小盘。 问将这n个盘子从a柱移动到c柱上总计需要移动多少个盘次 解设hn为n 个盘子从a柱移到c柱所需移动的盘次。显然当n1时只需把a 柱上的盘子直接移动到c柱就可以了故h11。当n2时先将a柱上面的小盘子移动到b柱上去然后将大盘子从a柱移到c 柱最后将b柱上的小盘子移到c柱上共记3个盘次故h23。以此类推当a柱上有n(n2)个盘子时总是先借助c柱把上面的n-1个盘子移动到b柱上然后把a柱最下面的盘子移动到c柱上再借助a柱把b柱上的n-1个盘子移动到c柱上总共移动hn-11hn-1个盘次。 ∴hn2hn-11 边界条件hn-11 Ⅲ.平面分割问题 问题的提出 设有n条封闭曲线画在平面上而任何两条封闭曲线恰好相交于两点且任何三条封闭曲线不相交于同一点问这些封闭曲线把平面分割成的区域个数。 解设an为n条封闭曲线把平面分割成的区域个数。 由图2可以看出a2-a12a3-a24a4-a36。从这些式子中可以看出an-an-12(n-1)。当然上面的式子只是我们通过观察4幅图后得出的结论它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成an-1个区域后第n-1条曲线每与曲线相交一次就会增加一个区域因为平面上已有了n-1条封闭曲线且第n条曲线与已有的每一条闭曲线恰好相交于两点且不会与任两条曲线交于同一点故平面上一共增加2(n-1)个区域加上已有的an-1个区域一共有an-12(n-1)个区域。所以本题的递推关系是anan-12(n-1)边界条件是a11。 平面分割问题是竞赛中经常触及到的一类问题由于其灵活多变常常让选手感到棘手下文中的『例题2』是另一种平面分割问题有兴趣的读者不妨自己先试着求一下其中的递推关系。 Ⅳ.Catalan数 Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的它经常出现在组合计数问题中。 问题的提出在一个凸n边形中通过不相交于n边形内部的对角线把n边形拆分成若干三角形不同的拆分数目用hn表之hn即为Catalan数。例如五边形有如下五种拆分方案(图6-4)故h55。求对于一个任意的凸n边形相应的hn。 解设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一条边都必然是一个三角形的一条边边P1 Pn也不例外再根据“不在同一直线上的三点可以确定一个三角形”只要在P2P3……Pn-1点中找一个点Pk(1kn)与P1、Pn 共同构成一个三角形的三个顶点就将n边形分成了三个不相交的部分(如图3所示)我们分别称之为区域①、区域②、区域③其中区域③必定是一个三角形区域①是一个凸k边形区域②是一个凸n-k1边形区域①的拆分方案总数是Ck区域②的拆分方案数为Cn-k1故包含△P1PkPn的n 边形的拆分方案数为CkCn-k1种而Pk可以是P2P3……Pn-1种任一点根据加法原理凸n边形的三角拆分方案总数为同时考虑到计算的方便约定边界条件C21。 Catalan数是比较复杂的递推关系尤其在竞赛的时候选手很难在较短的时间里建立起正确的递推关系。当然Catalan数类的问题也可以用搜索的方法来完成但是搜索的方法与利用递推关系的方法比较起来不仅效率低编程复杂度也陡然提高。 Ⅴ.第二类Stirling数 在五类典型的递推关系中第二类Stirling是最不为大家所熟悉的。也正因为如此我们有必要先解释一下什么是第二类Strling数。 【定义2】n个有区别的球放到m个相同的盒子中要求无一空盒其不同的方案数用S(n,m)表示称为第二类Stirling数。 下面就让我们根据定义3来推导带两个参数的递推关系——第二类Stirling数。 解设有n个不同的球分别用b1,b2,……bn表示。从中取出一个球bnbn的放法有以下两种 bn独自占一个盒子那么剩下的球只能放在m-1个盒子中方案数为S2(n-1,m-1) bn与别的球共占一个盒子那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中然后再将球bn可以放入其中一个盒子中方案数为mS2(n-1,m)。 综合以上两种情况可以得出第二类Stirling数定理 【定理】S2(n,m)mS2(n-1,m)S2(n-1,m-1) (n1,m1) 边界条件可以由定义2推导出 S2(n,0)0S2(n,1)1S2(n,n)1S2(n,k)0(kn)。 第二类Stirling数在竞赛中较少出现但在竞赛中也有一些题目与其类似甚至更为复杂。读者不妨自己来试着建立其中的递推关系。 『例1』(1998蚌埠市竞赛复试第一题)有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房不能反向爬行。试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。 解这是一道很典型的Fibonacci数列类题目其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房不能反向爬行”的限制决定了蜜蜂到b点的路径只能是从b-1点或b-2点到达的故fnfn-1fn-2 (a2nb)边界条件fa1fa11。(附有程序Pro_1.Pas) 『例2』(1998合肥市竞赛复试第二题)同一平面内的n(n500)条直线已知有p(p2)条直线相交于同一点则这n条直线最多能将平面分割成多少个不同的区域 解这道题目与第一部分中的平面分割问题十分相似不同之处就在于线条的曲直以及是否存在共点线条。由于共点直线的特殊性我们决定先考虑p条相交于一点的直线然后再考虑剩下的n-p条直线。首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2p个然后在平面上已经有k(kp)条直线的基础上加上一条直线最多可以与k条直线相交而每次相交都会增加一个区域与最后一条直线相交后由于直线可以无限延伸还会再增加一个区域。所以fmfm-1m (mp)边界条件在前面已经计算过了是fp2p。虽然这题看上去有两个参数但是在实际做题中会发现本题还是属于带一个参数的递推关系。(附有程序Pro_2.Pas) 上面的两道例题之中的递推关系比较明显说它们属于的递推关系类的试题相信没有人会质疑。 下面再让我们来看另一道题目。 『例3』(1999江苏省组队选拔赛试题第二题)在一个n×m的方格中m为奇数放置有n×m个数如图7 方格中间的下方有一人此人可按照五个方向前进但不能越出方格。如图8所示 人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径使其数相加之和为最大。输出和的最大值。 解这题在本质上类似于第一题都是从一个点可以到达的点计算出可以到达一个点的所有可能点然后从中发掘它们的关系。我们用坐标(x,y)唯一确定一个点其中(m,n)表示图的右上角而人的出发点是受人前进方向的限制能直接到达点(x,y)的点只有(x2,y-1)(x1,y-1)(x,y-1)(x-1,y-1)(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从到(x2,y-1)(x1,y-1)(x,y-1)(x-1,y-1)(x-2,y-1)的几条路径中产生既然要求最优方案当然要挑一条和最大的路径关系式如下Fx,y Max{Fx2,y-1 ,Fx1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1}Numx,y其中Numx,y表示(x,y) 点上的数字。边界条件为。(附有程序Pro_3.Pas) 看到上面的题目肯定有人会说这不是递推关系的应用这是动态规划上面的关系式也不是递推关系而是动态转移方程。为什么呢因为关系式中有取最大值运算(Max)所以它属于动态规划。是吗递推关系的定义中只要求“用等号(或大于号、小于号)将H(n)与其前面的某些项H(i)(0in)联系起来”联系的含义很广当然也包括用取最大(小)值运算符联系起来。所以我们认为上面的题目仍可属于递推关系当然同时它也属于动态规划。那么递推关系与动态规划之间到底是什么关系呢我们不妨画个Venn图(见图9)。如果用数学式子表示就是A{递推关系}B{动态规划}BA。通常人们理解的递推关系就是一般递推关系故认为动态规划与递推关系是两个各自独立的个体。下面让我们通过列表来分析一般递推关系与动态规划之间的异同(见表1)。 尽管一般递推关系与动态规划之间存在着这样和那样的区别但是在实际运用中人们还是经常把它们混为一谈而且总是把一般递推关系误认为是动态规划。这是因为从上个世纪五六十年代开始被人们发现的动态规划曾在信息学竞赛中掀起了一阵巨浪直到今天它仍是信息学竞赛中的重头戏。但是递推关系的历史源远流长虽然一般递推关系在今天不如动态规划那么炙手可热但是它对人的影响是不可忽视的。在IOI’99的选拔赛中就出现过一道《01统计》[4]很多人只是先利用公式求组合数再对组合数求和来求A类数的个数导致程序效率不高其实这是一道非常典型的递推关系类题目[5]由于选手平时对一般递推关系的忽视导致赛场失利。 还有一类博弈问题也利用了递推关系让我们来看一道关于这方面的例题。 『例4』(1995《学生计算机世界》)写一个计算机程序让计算机和人玩纸牌游戏争取计算机获胜并显示整个游戏过程。该游戏是两个选手(计算机一方人为另一方)比赛有n张(3n10000)纸牌两个选手交替地拿取(计算机先拿)谁取走最后一张即谁胜。拿取规则为第一个选手拿走1到n-1张牌(可拿任意张但不能拿完)以后每个人可取1张或1张以上但不得取走大于对方刚取数目的2倍(设对方刚取走b张则可取1到2b张)。 解这到题目看上去是一道很明显的动态规划试题以剩余牌数划分阶段状态Fp,k表示剩余p张牌且第一人最多可以取k张牌的情况是必败点还是必赢点。 状态转移方程是Fp,k(pk) or Fp,k-1 or not Fp-k,2k (1pn1kn) 然后我们可以根据求出的各个状态的情况设计一种取牌方案使计算机稳赢当然如果初始牌数是必败点那么计算机只能认输。 在牌数不太多的情况下这种方法效率比较高但是一旦牌数很大(假设n达到极限)那么需要的空间是O(105105)必然会导致空间不够的问题这种方法就不可行。 我们不妨把牌数较小的状态画成表来观察(见表2)看其中是否存在什么规律。 通过表2可以很明显的看出如果剩余牌数为2、3、5、8张的话无论先取牌的选手取多少张牌(假定不能够一次取完所有的牌)都必然会输(除非另一个选手不想赢)像2、3、5、8这类数字我们称之为“必败牌数”。在初始牌数不是必败牌数的情况下我们要设计一种方案使每次计算机取过x张牌后剩余的纸牌数大于2x张且为必败牌数。那么究竟那些数字是必败牌数呢从表中的数字2、3、5、8我们猜测Fibonacci数列中从2开始的数字都是必败牌数并通过数学证明得证[6]。那么我们就可以根据求出的必败牌数设计方案了。如果想让计算机在每一次取走x张牌后剩下的牌数是必败牌数且大于2x张看来是办不到。例如初始牌数20张如果一次取走7张使剩余13张的话对手可以一次性将13张牌全部取走。那么我们只有再对7张牌设计一种方案保证计算机能取到第7张牌并且计算机最后一次取的牌数小于13/2张就可以了而实现这一步这只需嵌套利用次Fibonacci数列就可以了(附有程序Pro_4.Pas)。 小结从上面的例题中可以看出利用一般递推关系解题有时会比动态规划更简单在动态规划实现起来比较困难的情况下一般递推关系可能会产生重要作用这种作用往往表现在直接求解或简化动态规划过程两方面。 总结 通过上文对递推关系的建立和在信息学竞赛中的应用的具体阐述可知递推关系不是一种抽象的概念它是具体的是需要针对具体题目而言的因此我们无法找出一种方法建立出所有的递推关系只能根据需要解决的题目的具体条件来分析。虽然递推关系的建立没有一个固定的模式可循但是从总体上来说都要先找出题目中的重要条件在这基础上分析某一项与其前面的若干项的关系然后找出边界条件。递推关系在竞赛中的应用相当的广泛它包含了几乎每赛必考的动态规划所以学好递推关系的建立无论是对提高我们的数学素质还是今后的竞赛都大有裨益。因为动态规划更为大家所熟悉所以本文着重说明了递推关系中的一般递推关系希望能给选手一定的启发。 【附 录】 骨牌覆盖2×n的棋盘用1×2的骨牌作完全覆盖求不同的覆盖方式数Cn 优选法设函数yfx在区间(a,b)上有一单峰极值点假定为极大点。所谓单峰极值即只有一个极点ξ而且当x与ξ偏离越大偏差|f(x)-f(ξ)|也越大。要求用若干次试验找到ξ点准确到一定的程度。较优的是实验方法有0.618优选法和Fibonacci优选法。 组合公式的证明 ∵ ∴ 证毕。 01序列近来IOI的专家们在进行一项有关二进制数的研究研究设计的一个统计问题令他们大伤脑筋。问题是这样的对于一个自然数n可以把他转换成对应的二进制数其中nak2kak-12k-1……a121a0而且ai0或1(0ik)ak1。如1010105101。我们统计一下a0~ak这k1个数中0的个数和1的个数。如果在这k1个数中0的个数比1的个数多就称为A类数。现在的任务是对于一个给定的m求1~m中a类数的个数。 有关于《01统计》的解法可参见徐静同学的解题报告。 证明用数学归纳法证明 由表2 可以得知Fibonacci数2、3、5、是必败牌数且在(1,5)之间的其他牌数都是必赢牌数 假设Fibonacci数列F1,F2……Fi,Fi1满足在(F1,Fi1]区间只有Fibonacci数才是必败牌数且其他牌数都是必赢牌数。则我们可证明在(F1,Fi2]区间的牌数也满足上面的性质。证明如下 设剩下Fi2张牌设这一次计算机取了x张牌则剩下牌数为pFi2-x张 若xFi则pFi1 ∵FiFiFi-1且Fi-1Fi ∴Fi12Fi ∴p2x ∴人可以一次将剩下的p张牌全部取完 ∴计算机一定会输 若1xFi则pFi1 ∵Fi2-FiFi1且Fi1是Fibonacci数 ∴计算机无法通过一种取牌方案使计算机在某一次取过少于Fi1/2张牌后剩下Fi1张牌 ∴当剩下Fi1张牌的时候必然轮到计算机取且计算机这时不能一次将所有牌取完 ∵Fi1是Fibonacci数 ∴计算机一定会输 又∵p(Fi1,Fi2),即剩下p张牌轮到人取的时候人一定获胜 ∴p是必赢牌数 由1、2可得结论成立。 证毕。转载于:https://www.cnblogs.com/PegasusWang/archive/2013/01/20/2868776.html
