递推关系的建立及在信息学竞赛中的应用
安徽高寒蕊
(芜湖一中，安徽，241000)
【关键字】递推关系建立应用
【摘要】
世界上的一切事物都在不经意之中变化着，在这纷繁的变幻中，许多现象的变化是有规律可循的。这种规律往往呈现出前因和后果的关系，故我们可以运用递推的思想去研究这些变化。本文着重说明了递推关系的建立，并在此基础上简略介绍求解递推关系的方法。接着，阐明递推关系与动态规划之间的关系，并比较了一般递推关系与动态规划之间的异同，同时举例说明递推关系在竞赛中的应用。在文章的最后，总结出学好递推关系，不仅可以提高我们的数学素质，对信息学竞赛更是大有帮助
目录
【正文】第02页
一、引论第02页
二、递推关系的定义第02页
三、递推关系的建立第02页
⒈五种典型的递推关系第03页
⒉递推关系的求解方法第06页
四、递推关系的应用第06页
五、总结第10页
【附录】第10页
【参考书目】第12页
【程序描述】第12页
【正文】
一、引论
瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。所谓“三岁看老”，说的就是这个道理。这一道理也正体现了递推的思想。递推关系几乎在所有的数学分支中都有重要作用，在一切向“更快、更高、更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。在递推关系发挥重要作用的今天，深入研究其性质、特点便成为一件十分必要的事情。本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。
二、递推关系的定义
相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。为了更好地研究递推关系，首先让我们明确什么是递推关系。
【定义1】给定一个数的序列H0,H1,…,H n,…若存在整数n0，使当n≥n0时,可以用等号(或大于号、小于号)将H n与其前面的某些项H n(0≤i 三、递推关系的建立 递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。如果能弄清楚这三个方面的问题，相信我们对递推关系的认识又会推进一步。由于篇幅所限，本文着重论述三大基本问题之一的如何建立递推关系。 建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一种抽象的概念，是需要针对某一具体题目或一类题目而言的。在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。 1．五种典型的递推关系 Ⅰ.Fibonacci数列 在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。 Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。 问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？ 解：设满x个月共有兔子F x对，其中当月新生的兔子数目为N x对。第x-1个月留下的兔子数目设为O x对。则： F x=N x+O x 而O x=F x-1， N x=O x-1=F x-2 (即第x-2个月的所有兔子到第x个月都有繁殖能力了) ∴F x=F x-1+F x-2 边界条件： F0=0，F1=1 由上面的递推关系可依次得到 F2=F1+F0=1，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，……。 Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”[1]问题、下文中的『例题1』等都可以用这种方法来解决。在优选法[2]中，Fibonacci数列的用处也得到了较好的体现。 Ⅱ.Hanoi塔问题 问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图1所示。 a b c 图1 要求把a柱上n个圆盘按下述规则移到c柱上： (1)一次只能移一个圆盘； (2)圆盘只能在三个柱上存放； (3)在移动过程中，不允许大盘压小盘。 问将这n 个盘子从a 柱移动到c 柱上，总计需要移动多少个盘次？ 解：设h n 为n 个盘子从a 柱移到c 柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c 柱就可以了，故h 1=1。当n=2时，先将a 柱上面的小盘子移动到b 柱上去；然后将大盘子从a 柱移到c 柱；最后，将b 柱上的小盘子移到c 柱上，共记3个盘次，故h 2=3。以此类推，当a 柱上有n(n 2)个盘子时，总是先借助c 柱把上面的n-1个盘子移动到b 柱上，然后把a 柱最下面的盘子移动到c 柱上；再借助a 柱把b 柱上的n-1个盘子移动到c 柱上；总共移动h n-1+1+h n-1个盘次。 ∴h n =2h n-1+1 边界条件：h n-1=1 Ⅲ.平面分割问题 问题的提出：设有n 条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。 解：设a n 为n 条封闭曲线把平面分割成的区域个数。 由图2可以看出：a 2-a 1=2；a 3-a 2=4；a 4-a 3=6。从这些式子中可以看出a n -a n-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成a n-1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n 条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的a n-1个区域，一共有a n-1+2(n-1)个区域。所以本题的递推关系是a n =a n-1+2(n-1)，边界条件是a 1=1。 平面分割问题是竞赛中经常触及到的一类问题，由于其灵活多变，常常让选手感到棘手，下文中的『例题2』是另一种平面分割问题，有兴趣的读者不妨自己先试着求一下其中的递推关系。 Ⅳ.Catalan 数 Catalan 数首先是由Euler 在精确计算对凸n 边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。 问题的提出：在一个凸n 边形中，通过不相交于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 n 边形拆分成若干三角形，不同的拆分数目用h n 表之，h n 即为Catalan 数。例如五边形有如下五种拆分方案(图6-4)，故h 5=5。求对于一个任意的凸n 边形相应的h n 。 解：设C n 表示凸n 边形的拆分方案总数。由题目中的要求可知一个凸n 边形的任意一条边都必然是一个三角形的一条边，边P 1 P n 也不例外，再根据“不在同一直线上的三点可以确定一个三角形”，只要在P 2，P 3，……，P n-1点中找一个点P k (1 ③，其中区域③必定是一个三角形，区域①是一个凸k 边形，区域②是一个凸n-k+1边形，区域①的拆分方案 总数是C k ，区域②的拆分方案数为C n-k+1，故包含△ P 1P k P n 的n 边形的拆分方案数为C k C n-k+1种，而P k 可 以是P 2，P 3，……，P n-1种任一点，根据加法原理，凸n 边形的三角拆分方案总数为11 2 +--=∑i n n i i C C ，同时考虑到 计算的方便，约定边界条件C 2=1。 Catalan 数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan 数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。 Ⅴ.第二类Stirling 数 在五类典型的递推关系中，第二类Stirling 是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling 数。 【定义2】n 个有区别的球放到m 个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling 数。 下面就让我们根据定义3来推导带两个参数的递推关系——第二类Stirling 数。 解：设有n 个不同的球，分别用b 1,b 2,……b n 表示。从中取出一个球b n ，b n 的放法有以下两种： ①b n 独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S 2(n-1,m-1)； ②b n 与别的球共占一个盒子；那么可以事先将b 1,b 2,……b n-1这n-1个球放入m 个盒子中，然后再将球b n 可以放入其中一个盒子中，方案数为mS 2(n-1,m)。 图 3 P 1 P n ① ② ③ 图4 P 2 P 3 P k P n--1 综合以上两种情况，可以得出第二类Stirling 数定理： 【定理】S 2(n,m)=mS 2(n-1,m)+S 2(n-1,m-1) (n>1,m ≥1) 边界条件可以由定义2推导出： S 2(n,0)=0；S 2(n,1)=1；S 2(n,n)=1；S 2(n,k)=0(k>n)。 第二类Stirling 数在竞赛中较少出现，但在竞赛中也有一些题目与其类似，甚至更为复杂。读者不妨自己来试着建立其中的递推关系。 小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。 2． 递推关系的求解方法 求解递推关系最简单易行的方法是递推，递推是迭代算法中一种用若干步可重复的简单运算来描述复杂数学问题的方法，以便于计算机进行处理。它与递推关系的思想完全一致，由边界条件开始往后逐个推算，在一般情况下，效率较高，编程也非常的方便。但是，我们一般只需要求递推关系的第n 项，而边界条件与第n 项前面之间的若干项的信息是我们不需要的，如果采用递推的方法来求解的话，第n 项之前的每一项都必须计算出来，最后才能得到所需要的第n 项的值。这是递推无法避免的，从而在一定程度上影响了程序的效率。当然在大多数情况下，采用递推的方法还是可行的，在竞赛中，使用递推的方法编程，通常会在时限内出解。 当然，更好的求解方法还有母函数法、迭代归纳法等等，这里就不再一一展开论述了。 例如同样是对于Fibonacci 数列问题：递推的方法要从F 1，F 2开始逐个推算出F 3，F 4……F n ，而利用母函数的方法，则可以得出公式 5 )251()251(n n n F --+=，则可直接求出所需要的任意一项。 四、 递推关系的应用 递推关系的应用十分的广泛，其中一个非常重要的应用就是著名的杨辉三角(又称“Pascal 三角”，见图5)。杨辉三角是根据组合公式C C C r n r n r n 1 11---+=[3]画出来的。很显然，组合公式、杨辉三角都属于递推关系的范围。 在今天的信息学竞赛中，递推关系的应用也日趋广泛，下面就让我们从近年来的两道竞赛题中体会递推关系的应用。 『例1』(1998蚌埠市竞赛复试第一题)有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。试求出蜜蜂从蜂房a 爬到蜂房b 的可能路线数。 解：这是一道很典型的Fibonacci 数列类题目，其中的递推关系很明显。由于“蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b 点的路径只能是从b-1点或b-2点到达的，故f n =f n-1+f n-2 (a+2≤n ≤b)，边界条件f a =1，f a+1=1。(附有程序Pro_1.Pas ) 『例2』(1998合肥市竞赛复试第二题)同一平面内的n(n ≤500)条直线，已知有p(p ≥2)条直线相交于同一点，则这n 条直线最多能将平面分割成多少个不同的区域？ 解：这道题目与第一部分中的平面分割问题十分相似，不同之处就在于线条的曲直以及是否存在共点线条。由于共点直线的特殊性，我们决定先考虑p 条相交于一点的直线，然后再考虑剩下的n-p 条直线。首先可以直接求出p 条相交于一点的直线将平面划分成的区域数为2p 个，然后在平面上已经有k(k ≥p)条直线的基础上，加上一条直线，最多可以与k 条直线相交，而每次相交都会增加一个区域，与最后一条直线相交后，由于直线可以无限延伸，还会再增加一个区域。所以f m =f m-1+m (m>p)，边界条件在前面已经计算过了，是f p =2p 。虽然这题看上去有两个参数，但是在实际做题中会发现，本题还是属于带一个参数的递推关系。(附有程序Pro_2.Pas ) 上面的两道例题之中的递推关系比较明显，说它们属于的递推关系类的试题，相信没有人会质疑。 3 5 7 9 11 13 4 6 8 10 12 14 …… …… 图6 1 1 1 1 1 1 1 1 1 1 1 2 3 3 4 6 4 5 10 10 5 n=1 n=2 n=3 n=4 n=5 r=0 r=1 r=2 r=3 r=4 图5 下面再让我们来看另一道题目。 『例3』(1999江苏省组队选拔赛试题第二题)在一个n ×m 的方格中，m 为奇数，放置有n ×m 个数，如图7： 方格中间的下方有一人，此人可按照五个方向前进但不能越出方格。如图8所示： 人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。 解：这题在本质上类似于第一题，都是从一个点可以到达的点计算出可以到达一个点的所有可能点，然后从中发掘它们的关系。我们用坐标(x,y)唯一确定一个点，其中(m,n)表示图的右上角，而人的出发点是??02/，m ，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到点(x,y)的路径中和最大的路径必然要从到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，关系式如下：F x,y = Max{F x+2,y-1 ,F x+1,y-1,F x,y-1,F x-1,y-1,F x-2,y-1}+Num x,y ，其中Num x,y 表示(x,y) 点上的数字。边界条件为：??00,2/=m F ，??)2/1(0,m x m x F x ≠≤≤-∞=且。(附有程序Pro_3.Pas ) 16 4 3 12 6 0 3 4 -5 6 7 0 0 2 6 0 -1 -2 3 6 8 5 3 4 0 0 -2 7 -1 7 4 0 7 -5 6 0 -1 3 4 12 4 2 人 图7 图8 看到上面的题目，肯定有人会说，这不是递推关系的应用，这是动态规划；上面的关 系式也不是递推关系，而是动态转移方程。为 什么呢？因为关系式中有取最大值运算 (Max)，所以它属于动态规划。是吗？递推关系的定义中只要求“用等号(或大于号、小于 号)将H(n)与其前面的某些项H(i)(0≤i 起来”，联系的含义很广，当然也包括用取最 大(小)值运算符联系起来。所以我们认为，上面的题目仍可属于递推关系，当然，同时它也属于动态规划。那么递推关系与动态规划之间到底是什么关系呢？我们不妨画个Venn 图(见图9)。如果用数学式子表示，就是：A={递推关系}B={动态规划}，B ?A 。通常人们理解的递推关系就是一般递推关系，故认为动态规划与递推关系是两个各自独立的个体。下面让我们通过列表来分析一般递推关系与动态规划之间的异同(见表1)。 尽管一般递推关系与动态规划之间存在着这样和那样的区别，但是在实际运用中，人们还是经常把它们混为一谈，而且总是把一般递推关系误认为是动态规划。这是因为从上个世纪五六十年代开始被人们发现的动态规划曾在信息学竞赛中掀起了一阵巨浪，直到今天，它仍是信息学竞赛中的重头戏。但是，递推关系的历史源远流长，虽然一般递推关系在今天不如动态规划那么炙手可热，但是它对人的影响是不可忽视的。在IOI’99的选拔赛中，就出现过一道《01统计》 [4] ，很多人只是先利用公式)! (!! r n r n C r n -= 求组合数，再对组合数求和，来求A 类数的个数，导致程序效率不高，其实，这是一道非常典型的递推关系类题目[5]，由于选手平时对一般递推关系的忽视，导致赛场失利。 还有一类博弈问题也利用了递推关系，让我们来看一道关于这方面的例题。 『例4』(1995《学生计算机世界》)写一个计算机程序，让计算机和人玩纸牌游戏，争取计算机获胜，并显示整个游戏过程。该游戏是：两个选手(计算机一方，人为另一方)比赛：有n 张(3 动态规划 图9 一般递推关系 递推关系 一般递推关系与动态规划之间的异同对照表 比较项目 一般递推关系 动态规划 有无后效性 无 无 边界条件 一般很明显 一般比较隐蔽，容易被忽视 一般形式 H n =a 1?H n-1+a 2?H n-2+…+ a r ?H n-r 数学性较强 H n =Max{…}+a 数学性相对较弱 是否有阶段 一般不划分阶段 一般有较明显的阶段 表1 解：这到题目看上去是一道很明显的动态规划试题，以剩余牌数划分阶段，状态F p,k 表示剩余p 张牌，且第一人最多可以取k 张牌的情况是必败点还是必赢点。 状态转移方程是：F p,k =(p ≤k) or F p,k-1 or not F p-k,2?k (1≤p ≤n ，1≤k 然后我们可以根据求出的各个状态的情况设计一种取牌方案，使计算机稳赢，当然，如果初始牌数是必败点，那么计算机只能认输。 在牌数不太多的情况下，这种方法效率比较高，但是一旦牌数很大(假设n 达到极限)，那么需要的空间是O(105?105)，必然会导致空间不够的问题，这种方法就不可行。 我们不妨把牌数较小的状态画成表来观察(见表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 )。 小结：从上面的例题中可以看出，利用一般递推关系解题有时会比动态规划更简单，在动态规划实现起来比较困难的情况下，一般递推关系可能会产生重要作用，这种作用往往表现在直接求解或简化动态规划过程两方面。 五、 总结 通过上文对递推关系的建立和在信息学竞赛中的应用的具体阐述，可知，递推关系不是一种抽象的概念，它是具体的，是需要针对具体题目而言的，因此，我们无法找出一种方法建立出所有的递推关系，只能根据需要解决的题目的具体条件来分析。虽然递推关系的建立没有一个固定的模式可循，但是从总体上来说，都要先找出题目中的重要条件，在这基础上分析某一项与其前面的若干项的关系，然后找出边界条件。递推关系在竞赛中的应用相当的广泛，它包含了几乎每赛必考的动态规划，所以学好递推关系的建立，无论是对提高我们的数学素质， 1 2 3 4 5 6 7 1 2 × 3 × × 4 √ √ √ 5 × × × × 6 √ √ √ √ √ 7 × √ √ √ √ √ 8 × × × × × × × 注：√表示True, ×表示False 表2 k n 还是今后的竞赛，都大有裨益。因为动态规划更为大家所熟悉，所以本文着重说明了递推关系中的一般递推关系，希望能给选手一定的启发。 【附 录】1 [1] 骨牌覆盖：2×n 的棋盘用1×2的骨牌作完全覆盖，求不同的覆盖方式数C n [2] 优选法：设函数y=f x 在区间(a,b)上有一单峰极值点，假定为极大点。所谓单峰极值，即只有一个极点ξ，而且当x 与ξ偏离越大，偏差|f(x)-f(ξ)|也越大。要求用若干次试验找到ξ点准确到一定的程度。较优的是实验方法有0.618优选法和Fibonacci 优选法。 [3] 组合公式C C C r n r n r n 1 11---+=的证明： ∵ )! ()!1()1()! 1(!)!1(1 11r n r n r n r n C C r n r n ---= ---= ---！ ∴ C C C r n r n r n r n r n r n r r n r n n =-=-?-+-?-= +---)! (!)!(!)!1()()1(1 11！！ 证毕。 [4] 01序列：近来IOI 的专家们在进行一项有关二进制数的研究，研究设计的一 个统计问题令他们大伤脑筋。问题是这样的：对于一个自然数n ，可以把他转换成对应的二进制数011a a a a k k ??-，其中：n=a k ?2k +a k-1?2k-1+……a 1?21+a 0；而且a i =0或1(0≤i [5] 有关于《01统计》的解法可参见徐静同学的解题报告。 [6] 证明：用数学归纳法证明： 1.由表2 可以得知：Fibonacci 数2、3、5、是必败牌数，且在(1,5)之间的其他牌数都是必赢牌数 2.假设Fibonacci 数列F 1,F 2……F i ,F i+1满足在(F 1,F i+1]区间，只有Fibonacci 数才是必败牌数，且其他牌数都是必赢牌数。则我们可证明在(F 1,F i+2]区间的牌数也满足上面的性质。证明如下： 设剩下F i+2张牌，设这一次，计算机取了x 张牌，则剩下牌数为 p=F i+2-x 张 (1) 若x ≥F i ，则p ≤F i+1， ∵F i =F i +F i-1且F i-1≤F i ∴F i+1≤2F i ∴p ≤2x ∴人可以一次将剩下的p 张牌全部取完 1 [3]、[6]的证明是作者自己证明的，若有错误之处，请指正。 ∴计算机一定会输 (2)若1≤x ∵F i+2-F i=F i+1且F i+1是Fibonacci数 ∴计算机无法通过一种取牌方案，使计算机在某一次取过少于 F i+1/2张牌后，剩下F i+1张牌 ∴当剩下F i+1张牌的时候，必然轮到计算机取，且计算机这时不能一次将所有牌取完 ∵F i+1是Fibonacci数 ∴计算机一定会输 又∵p∈(F i+1,F i+2),即剩下p张牌轮到人取的时候，人一定获胜， ∴p是必赢牌数 3.由1、2可得结论成立。证毕。 【参考书目】 1．杨振生编著王树禾审《组合数学及其算法》中国科技大学出版社1997 2．孙淑玲许胤龙《组合数学引论》中国科技大学出版社出版1999 3．卢开澄《组合数学》清华大学出版社1991 4．吴文虎王建德《青少年国际和全国信息学(计算机)奥林匹克竞赛指导——组合数学的算法与程序设计》清华大学出版社1997 5．吴文虎主编《信息学(计算机)奥林匹克》高级本北京大学出版社1992 6．吴文虎主编《信息学(计算机)奥林匹克》中级本北京大学出版社1992 【程序描述】 Pro_1.Pas program Pro_1;{蜂巢问题，最大范围：目标点与出发点之差不超过40000} type Tarr=array[1..10000] of byte; Tnum=array[1..4] of ^Tarr; Tlen=array[1..4] of word; var start,finish:longint; {出发点和目标点} num:Tnum; {num[1]…num[3]分别保存到达相邻三个蜂巢的路径数；num[4]是用于交换的临时变量} len:Tlen; {len[i]表示num[i]的长度} procedure DataInit;{数据初始化} var i:integer; begin for i:=1 to 3 do begin new(num[i]); fillchar(num[i]^,sizeof(num[i]^),0); num[i]^[1]:=1; len[i]:=1; end; end; procedure Add;{高精度加法运算：num[3]=num[1]+num[2]} var i,carry:word;{carry是进位数字} begin carry:=0; for i:=1 to len[2] do begin carry:=carry+num[2]^[i]+num[1]^[i]; num[3]^[i]:=carry mod 10; carry:=carry div 10; end; len[3]:=i; if carry>0 then begin inc(len[3]); num[3]^[i+1]:=carry; end; end; procedure Work;{求从出发点到目标点的路径总数} var i:longint; begin num[1]^[1]:=1; num[2]^[1]:=1; for i:=start+2 to finish do begin Add;{高精度加法运算：num[3]=num[1]+num[2]} num[4]:=num[1]; num[1]:=num[2]; num[2]:=num[3]; num[3]:=num[4]; len[4]:=len[1]; move(len[2],len[1],6); end; end; procedure Out;{输出结果} i:integer; begin for i:=len[2] downto 1 do write(num[2]^[i]); writeln; end; begin DataInit; {数据初始化} write('Input: '); readln(start,finish); Work; {求从出发点到目标点的路径总数} Out; {输出结果} end. Pro_2.Pas program Pro_2;{第二种平面分割问题} var n,p,total,i:longint;{total是区域总数} begin write('n='); readln(n); write('p='); readln(p); total:=p*2; for i:=p+1 to n do inc(total,i); {也可用total:=(p+n+1}*(n-p) div 2} writeln('Total Area:',total); end. Pro_3.Pas program Pro_3;{取数} const Infns='Pro_3.in'; Sign=-10000000;{不可到达的点的标志} type Tarr=array[0..100,1..101] of longint; var num:^Tarr;{保存每个点上的数字} sum:Tarr; {保存到每个点的和最大是多少} n, {方格的高度} m:integer; {方格的宽度} procedure ReadIn;{读入数据并初始化} var ni,mi:integer; assign(Input,Infns); reset(Input); readln(n,m); new(num); for ni:=n downto 1 do for mi:=1 to m do begin read(num^[ni,mi]); end; for mi:=1 to m do sum[0,mi]:=Sign; {置不可到达的点的标志} sum[0,m div 2+1]:=0;{人的出发点} close(Input); end; procedure Work;{找到每个点的和最大的路径的和是多少} var ni,mi,dir:integer; max:longint; begin for ni:=1 to n do for mi:=1 to m do begin max:=sign; for dir:=-2 to 2 do if (mi+dir>0) and (mi+dir<=m) and (sum[ni-1,mi+dir]>max) then max:=sum[ni-1,mi+dir]; if max>sign then sum[ni,mi]:=max+num^[ni,mi] else sum[ni,mi]:=max; end; end; procedure FindMax;{找出和最大的路径的和是多少} var mi:integer; max:longint; begin max:=sign; for mi:=1 to m do if sum[n,mi]>max then max:=sum[n,mi]; writeln('Max=',max) end; ReadIn; {读入数据并初始化} Work; {找到每个点的和最大的路径的和是多少} FindMax; {找出和最大的路径的和是多少} end. Pro_4.Pas program Pro_4;{博弈问题} var Youget, {人取了多少张牌} total:integer; {现在还剩下多少张牌} procedure GetYourAnswer(Iget:integer);{读取人这次取多少张牌} begin repeat write('You: '); readln(Youget); until (Youget>0) and (Youget<=Iget*2); dec(total,Youget); {总牌数相应减少} writeln('Remain: ',total); end; procedure Work(n:integer);{对n张牌设计一种取法使计算机能取到第n张牌} var a1,a2,a3:integer; begin if Youget*2>=n then {是否能够一次取完} begin writeln('I: ',n); dec(total,n); writeln('Remain: ',total); exit; end; a1:=0; a2:=1; a3:=1; while a3 begin a1:=a2; a2:=a3; inc(a3,a1); end; if n=a3 then begin writeln('You can win!'); halt; end;{必败牌数} if ((n-a2)*2>=a2) or (n-a2>Youget*2) then Work(n-a2) else begin writeln('I: ',n-a2); dec(total,n-a2); writeln('Remain: ',total); end; GetYourAnswer(n-a2); {读取人这次取多少张牌} Work(a2-Youget); end; begin {主程序} write('Total card: '); readln(total); Youget:=(total-1) div 2; {通过限定Youget给计算机可以取的最大牌数限界} Work(total); {对total张牌设计一种取法使计算机能取到最后一张牌} writeln('I win!'); end. 1 建设物流实训室的必要性 在社会需求的推动下，20xx年起，全国部分学校开始试办“物流管理”等相关专业，为企业培养和输送物流专业人才。这在一定程度上对物流知识和思想的传播起到了很好的作用，也的确培养了一些物流人才。他们在相关的物流岗位上发挥了作用，有效地促进了企业物流运作的变革和进步。 但是，其中反映出的问题也不少，主要体现在以下几个方面： 1.1 偏重理论培训，缺少实践环节 目前在各种认证体系中，基本上以知识性学习为主，只有少量的实际操作环节。 现代物流业很注重实际操作经验，仅有理论知识难以解决企业的实际业务问题，物流培训也必须以此为重要原则，加强实训功能，注重对实际业务的理解和对实际操作技能的掌握，才能培养出符合企业需求的人才。 1.2 教学手段单一，感性认识与理性认识不能有机结合 目前无论是高校的物流学历教育还是职业培训，普遍存在一个问题，就是教学主要以教师分散授课为主，辅以少量甚至没有参观。学员们无法全面系统地了解物流运作的整个过程，除少量悟性较高的学员外，大多数学员的物流知识结构比较凌乱。 1.3 传统实训方式已不能满足学生和企业的需要 学生实训要求在类似企业实际的环境下，并且实训的设备、软件必须是企业实际应用的，或在企业实际应用基础上改造过来。 随着国内教育教学改革的深入，实训方式创新层出不穷，旧有的实训方式尤其是模拟仿真远远不能满足现有教学的需要。 2 物流实训室设计理念 通过实训室对各节点模拟，从而展现货物的入库、仓储、流通加工、配送、出库等第三方物流企业的供应链流程。在此模拟的供应链上，配备一系列模块化的现代物流设施，如：全自动立体仓库、电子标签辅助拣货系统、电子看板，RF手持设备等，它们各自独立，又互为联系，充分体现了传统的物流运行过程通过信息化实现其战略决策系统化，管理现代化和作业自动化这一现代物流的时代特征，从而在学校实训室内营造了一个类似真实的集物资流和信息流于一体的实训教学环境。 3 实训室方案规划设计 物流实训室平面布局 主要组成部分： 全自动立体仓库及自动分拣：立体货架、全自动堆垛机及输送装置等； 普通仓储货架：重型及轻型货架； 电子标签拣货系统：重力式货架、电子标签分拣系统及拣货台等； 打包封装：多种款式的打包设备； 条码及射频系统：RF手持终端、条码打印机及多种条码阅读设备； 管理岗位：物流软件、PC及桌椅。 4 实训系统功能 之所以要在学校实训室条件下，构建一个类似真实的以第三方物流服务单元为核心的供应链仿真系统，其真实目的是想以此为学校进行现代供应链物流运作管理等相关课程的课堂理论教学提供一个有效的辅助教学手段，并为学生掌握各种现代化，自动化的物流设施设备的操作技能，提供一个实实在在的实训平台。 所以从这个意义上说，我们这套实训系统应具有以下教学实训功能： 4.1 了解和学习物流管理的内容和技术 1、仓储管理系统的操作训练 深入探究多项式乘法的快速算法 焦作市第一中学 闵梓轩 一、 高精度、多项式与生成函数 1.1 高精度 在OI 中我们有时会碰到一些问题的必要数值超出64位整形的范围，这个时候我们就需要用到高精度方式存储。而高精度数的思想是进制思想的一个具体体现，出于正常人类的习惯，我们所使用的高精度数都采用10进制，即每一位都表示十进制上的一个数，从0~9，更进一步，为了优化高精度数运算所花费的时间与空间，我们采用了万进制，即每一位存0~9999的数，这样同时优化了程序效率，同时在输出上也没有什么太大的问题（每一位不足1000补0即可）。 当然，我们也可以用三进制、五进制、450进制，8964进制的高精度数，虽然因为在输出时会变得非常麻烦而没有人去用，但是它们的可行性正对应了进制的一种思想，比如一个十进制数12450，它的算数含义是0123410*010*510*410*210*1++++二进制数10010，它的算数含义是1 42*12*1+（把为0的位忽略），这样形如 ),0(*0N a x a x a i i n i i i ∈<≤∑=的每一位上的数字在数值表示上都乘上了某个数的一个幂的数正是进制思想的基础。在编程实现上这样的一个数我们通常用整形数组来表示，a[i]表示i 次项的系数，如果数组长度为n ，那么学过高精度的人都知道两个数相加的时间复杂度是θ(n)，两个数相乘的时间复杂度是O(n^2)，在信息学竞赛中，这样的时间复杂度足以满足大部分题目的需求，因为一般来说我们的数值都不会达到10^100000次方这么大。 1.2多项式 熟悉数学的我们能够发现上面这样的一个式子，如果忽略了括号中的内容的限制，那么 我们可以发现这样的式子其实就是我们所学的n 次多项式∑∞==0*)(i i i x a x A ， 比如十进制数12450就是05421234++++x x x x 当x=10的时候的数值嘛。所以，当一个值b 代入多项式A(x)时，这个式子也就变成了一个值A(b)。但是要注意的是多项式的系数是没有限制的，所以多项式可以用浮点数组表示，而且我们可以惊奇地发现多项式的加法和乘法在代码上除了不需要进位之外和高精度是一样的。所以说，我们所见的b 进制数值，就是一个当x=b 的多项式的取值而已。但是在多项式中，x 的意义仅仅是一个符号而已，ai*x^i 你可以理解为ai 在数组的第i 个位置。 我们需要注意的是，n 次多项式的数组表示需要用到n+1个数，为什么？因为有n 个含x 的项和一个常数项，所以我们一般把多项式A(x)的最高次项的次数+1称作为这个多项式的次数界（次数界的真正意义是系数不为零的最高次项的次数+1，下文中提到的“次数界“为 遗传算法合集 遗传算法简介 遗传算法是一类模拟生物进化的智能优化算法，它是由J.H.Holland于六十年代提出的。目前，遗传算法已成为进化计算研究的一个重要分支。 与传统优化方法相比，遗传算法的优点是： ·群体搜索 ·不需要目标函数的导数 ·概率转移准则 遗传算法研究热点 ·收敛性证明 ·新型高效的遗传算子设计 ·遗传算法与局部优化算法的结合 ·遗传算法在各领域的应用研究 ·软计算与计算智能中的遗传算法 遗传算法著作 1.陈国良等，遗传算法及其应用，国防出版社 2.J.H.Holland,Adaptation in Natural and Artificial Systems, Ann Arbor: Univ. of Michigan Press, 1975 3.D.E.Goldberg,Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989 4.L.D.Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold 5.Z.Michalewicz, Genetic Algorithms + Data Structures=Evolution Programs, Spinger Press,1996 6.M.Gen,R.Cheng,Genetic Algorithms & Engineering Design, 1997 7.Wiely,Genetic Algorithms in Engineering and Computer Science,1995 8.M.Mitchell,An Introducion to Genetic Algorithms,1996 9.Davis,Genetic Algorithms and Simulated Annealing,1987 10.Davidor,Genetic Algorithms and Robotics,1991 11.Koza,Genetic Programming,1992 12.Bauer,Genetic Algorithms and Investiment Strategies,1994 遗传算法站点 1.The Genetic Algorithms Archive https://www.doczj.com/doc/bc5303738.html,/galist/ 2.Genetic Adaptive Systems LAB (GASLAB) GASLAB is hosted by the Computer Science Department of the University of Nevada-Reno. https://www.doczj.com/doc/bc5303738.html,/~sushil/papers/conference/conf.html https://www.doczj.com/doc/bc5303738.html,/ 3.http://www.mat.sbg.ac.at/~uhl/GA.html 4.https://www.doczj.com/doc/bc5303738.html,/research/gag/ email:kdejong@https://www.doczj.com/doc/bc5303738.html, publications: (downloading website) https://www.doczj.com/doc/bc5303738.html,/research/gas/pubs.html 5.Illinois Genetic Algorithms Laboratory Prof. David E. Goldberg, Director https://www.doczj.com/doc/bc5303738.html,./illigal.home.html 6.Michigan State University Genetic Algorithms Research and Applications Group (GARAGE) Bill Punch (punch@https://www.doczj.com/doc/bc5303738.html,,517-353-3541) Erik Goodman (goodman@https://www.doczj.com/doc/bc5303738.html,,517-355-6453) https://www.doczj.com/doc/bc5303738.html,/ 左偏树的特点及其应用 广东省中山市第一中学黄源河 【摘要】 本文较详细地介绍了左偏树的特点以及它的各种操作。 第一部分提出可并堆的概念，指出二叉堆的不足，并引出左偏树。第二部分主要介绍了左偏树的定义和性质。第三部分详细地介绍了左偏树的各种操作，并给出时间复杂度分析。第四部分通过一道例题，说明左偏树在当今信息学竞赛中的应用。第五部分对各种可并堆作了一番比较。最后总结出左偏树的特点以及应用前景。 【关键字】左偏树可并堆优先队列 【目录】 一、引言 (2) 二、左偏树的定义和性质 (2) 2.1 优先队列，可并堆 (2) 2.1.1 优先队列的定义 (2) 2.1.2 可并堆的定义 (2) 2.2 左偏树的定义 (3) 2.3 左偏树的性质 (4) 三、左偏树的操作 (6) 3.1 左偏树的合并 (6) 3.2 插入新节点 (8) 3.3 删除最小节点 (9) 3.4 左偏树的构建 (9) 3.5 删除任意已知节点 (10) 3.6 小结 (13) 四、左偏树的应用 (15) 4.1 例——数字序列（Baltic 2004） (15) 五、左偏树与各种可并堆的比较 (18) 5.1 左偏树的变种——斜堆 (18) 5.2 左偏树与二叉堆的比较 (19) 5.3 左偏树与其他可并堆的比较 (19) 六、总结 (22) 在线代理|网页代理|代理网页|https://www.doczj.com/doc/bc5303738.html, 【正文】 一、引言 优先队列在信息学竞赛中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，优先队列都有着广泛的应用。二叉堆是一种常用的优先队列，它编程简单，效率高，但如果问题需要对两个优先队列进行合并，二叉堆的效率就无法令人满意了。本文介绍的左偏树，可以很好地解决这类问题。 二、左偏树的定义和性质 在介绍左偏树之前，我们先来明确一下优先队列和可并堆的概念。 2.1优先队列，可并堆 2.1.1优先队列的定义 优先队列(Priority Queue)是一种抽象数据类型(ADT)，它是一种容器，里面有一些元素，这些元素也称为队列中的节点(node)。优先队列的节点至少要包含一种性质：有序性，也就是说任意两个节点可以比较大小。为了具体起见我们假设这些节点中都包含一个键值(key)，节点的大小通过比较它们的键值而定。优先队列有三个基本的操作：插入节点(Insert)，取得最小节点(Minimum) 和删除最小节点(Delete-Min)。 2.1.2可并堆的定义 可并堆(Mergeable Heap)也是一种抽象数据类型，它除了支持优先队列的三个基本操作(Insert, Minimum, Delete-Min)，还支持一个额外的操作——合并操作： H ← Merge(H1,H2) Merge( ) 构造并返回一个包含H1和H2所有元素的新堆H。 前面已经说过，如果我们不需要合并操作，则二叉堆是理想的选择。可惜合并二叉堆的时间复杂度为O(n)，用它来实现可并堆，则合并操作必然成为算法的瓶颈。左偏树(Leftist Tree)、二项堆(Binomial Heap) 和Fibonacci堆(Fibonacci Heap) 都是十分优秀的可并堆。本文讨论的是左偏树，在后面我们将看到各种可并堆的比较。 在线代理|网页代理|代理网页|https://www.doczj.com/doc/bc5303738.html, 设计方案范文合集八篇 设计方案范文合集八篇 为了确保事情或工作有序有力开展，常常需要预先准备方案，方案属于计划类文书的一种。方案应该怎么制定呢？以下是收集整理的设计方案8篇，仅供参考，希望能够帮助到大家。 设计方案篇1 一、活动目的 1、培养学生合作探究的精神与分析问题、解决问题的能力。 2、培养和增强学生的地理学习兴趣，关注身边的地理知识。 3、懂得多渠道收集课外资料。 二、活动时间及地点 三、活动方式 根据课室座位安排情况，以小组为单位，每两排组成一组，共分为四大组。以“野外考察员的困难”为主要内容，展开几个阶段的小组间的地理知识竞赛。 四、参与人员 全体同学 五、活动流程 活动刚开始，教师以一名“地理野外考察员”的身份登场，讲述他一天所遇到的困难。困难一：迷失了方向 1、活动准备 在活动前的地理课，向学生提出“当你迷失野外，你该如何来辨别方向”这一问题，让学生课后根据自己的生活经验或向有经验的长辈请教等各类方式收集有关方法，并以作业形式上交。 2、活动过程 学生以小组为单位，全组成员上交一份解决方法，教师当场逐一宣读，答对1个得1分，答错不得分。 3、活动小结 教师讲解野外辨别方向常用的几种方法。 附： 1）平时参考地图和指南针，同时积极观察周围的地形以及身边的植物来判断正确位置。 2）利用太阳 ①冬季日出位置是东偏南，日落位置是西偏南；夏季日出位置是东偏北，日落位置是西偏北；春分、秋分前后，日出正东，日落正西。 ②只要有太阳，就可以使用手表来辨别方向。按24小时制读出当时的时刻，将小时数除以二，将得到一个小时数。把手表水平放在手上或者地上，让手表的这个时刻对准太阳所在的方位，这时手表表面12点所指的方向是北方，6点所指的方向是南方。 设计方案篇2 1、幼儿园的功能组成 包括幼儿生活用房、服务用房、和供应用房三部分。 2、幼儿园的功能分析 计划方案合集10篇 计划方案合集10篇 为了确保我们的努力取得实效，通常会被要求事先制定方案，方案是在案前得出的方法计划。那么什么样的方案才是好的呢？下面是小编帮大家整理的计划方案10篇，仅供参考，大家一起来看看吧。计划方案篇1 各林场(所)：为进一步深入贯彻《甘肃省自然保护区条例》及《XX市人民政府关于进一步加强封山禁牧工作的通知》和《XX林业总场封山禁牧管理暂行办法》精神，巩固XX林区近年来的封山禁牧成果，加快生态环境建设步伐，现就我场XX年封山禁牧工作安排如下：一、明确指导思想我场的封山禁牧工作，坚持统筹规划，以封为主，禁牧与圈养、恢复生态和保护林农利益相结合的指导思想，按照《森林法》、《森林法实施条例》及市局、总场关于封山禁牧工作的总体部署和要求，坚持把加强封山禁牧工作作为恢复植被、改善生态、提高林木尽快成林的重要措施，作为改善人居环境，促进人与自然和谐相处，构建和谐林区的重要保障。各林场（所）要从促进林区经济社会可持续发展的大局出发，切实增强责任感和紧迫感，采取切实有效的措施，加大工作力度，真正把封山禁牧工作抓紧抓好，确保取得实效。二、细化工作任务一要提高认识，统筹安排，强化责任，分解任务。各林场（所）主要领导要切实提高认识，将封禁工作放在同林业生产同等重要的位置上，同安排同部署，并根据市局、总场封禁工作会议精神，延伸签订封禁工作目标管理责任书，确保封禁工作责任分解到站，细化到人。二要广泛宣传动员，营造良好舆论氛围。各林场（所）要采取召开干部会、群众大会、养殖户专题会、管护人员工作会、发放宣传资料、刷写宣传标语、悬挂横幅、制做固定宣传碑等多种形式，广泛宣传《森林法》、《森林法实施条例》、《XX 市人民政府关于进一步加强封山禁牧工作的通知》《XX、林业总场封山禁牧管理暂行办法》等有关政策法规文件，教育林区群众充分认识封山禁牧的重大意义，明确封山禁牧的范围、措施和责任，引导群众正确处理长远利益与当前利益、整体利益与局部利益、封山禁牧与畜牧养殖的关系，真正把封山禁牧工作变为广大群众的自觉行动，为封山禁牧创造良好的舆论氛围。三要详细调查摸底，掌握 3.3 多项式的乘法 一．选择题（共4小题） 1．已知（x﹣m）（x+n）=x2﹣3x﹣4，则m﹣n的值为（） A．1 B．﹣3 C．﹣2 D．3 2．（x2+ax+8）（x2﹣3x+b）展开式中不含x3和x2项，则a、b的值分别为（）A．a=3，b=1 B．a=﹣3，b=1 C．a=0，b=0 D．a=3，b=8 3．若2x3﹣ax2﹣5x+5=（2x2+ax﹣1）（x﹣b）+3，其中a、b为整数，则a+b之值为何？（）A．﹣4 B．﹣2 C．0 D．4 4．下列计算错误的是（） A．（x+a）（x+b）=x2+（a+b）x+ab B．（x+a）（x﹣b）=x2+（a+b）x+ab C．（x﹣a）（x+b）=x2+（b﹣a）x+（﹣ab） D．（x﹣a）（x﹣b）=x2﹣（a+b）x+ab 二．填空题（共8小题） 5．若（x+1）（x+a）展开是一个二次二项式，则a= 6．定义运算：a⊕b=（a+b）（b﹣2），下面给出这种运算的四个结论：①3⊕4=14；②a⊕b=b⊕a； ③若a⊕b=0，则a+b=0；④若a+b=0，则a⊕b=0．其中正确的结论序号为．（把 所有正确结论的序号都填在横线上） 7．已知m+n=3，mn=﹣6，则（1﹣m）（1﹣n）= ． 8．已知（3x﹣p）（5x+3）=15x2﹣6x+q，则p+q= ． 9．如图，正方形卡片A类、B类和长方形卡片C类各若干张，如果要拼一个长为（a+3b），宽为（2a+b）的长方形，则需要C类卡片张． （第9题图） 10．一个三角形的底边长为（2a+6b），高是（3a﹣5b），则这个三角形的面积是．11．计算下列各式，然后回答问题． （a+4）（a+3）= ；（a+4）（a﹣3）= ； （a﹣4）（a+3）= ；（a﹣4）（a﹣3）= ． 计算智能 习题总集 习题一： 空缺 习题二： 1、在反馈型神经网络中，有些神经元的输出被反馈至神经元的（ ） A ．同层 B ．同层或前层 C ．前层 D ．输出层 2、在神经网络的一个节点中，由激励函数计算得到的数值是该节点的（ ） A ．实际输出 B ．实际输入 C ．期望输出 D ．期望值 3、在神经网络的一个节点中，由激励函数计算得到的数值，是与该节点相连的下一个节点的（ ） A ．实际输出 B ．实际输入 C ．期望输出 D ．期望值 4、下面的学习算法属于有监督学习规则的是（ ） A ．Hebb 学习规则 B ．Delta 学习规则 C ．概率式学习规则 D ．竞争式学习规则 E ．梯度下降学习规则 F ．Kohonen 学习规则 5、BP 算法适用于（ ） A ．前馈型网络 B ．前馈内层互联网络 C ．反馈型网络 D ．全互联网络 6、BP 神经网络采用的学习规则是（ ） A ．联想式Hebb 学习规则 B ．误差传播式Delta 学习规则 C ．概率式学习规则 D ．竞争式学习规则 习题三： 1、设论域U ={u 1, u 2, u 3, u 4, u 5}, 5 432118.06.04.02.0u u u u u A ++++＝， 5 43214.06.016.04.0u u u u u B ++++＝， 求 B A B A , , , 。 2、设X ={1, 5, 9, 13, 20}, Y ={1, 5, 9, 13, 20}, ~ R 是模糊关系“x 比y 大得多”。 隶属度函数： 求模糊关系矩阵~ R 3、 4、Zadeh 教授提出了著名的不相容原理，是指复杂系统的那两种矛盾（ ） A ．精确性和有效性 B ．精确性和模糊性 C ．模糊性和有效性 D ．复杂性和模糊性 5、在模糊推理得到的模糊集合中取一个最能代表这个集合的单值的过程称为（ ） A ．去模糊 B ．模糊化 C ．模糊推理 D ．模糊集运算 6、判断 1．一个模糊集合可以被其隶属度函数唯一定义（ ） 2．隶属度越大表示真的程度越高；隶属度越小表示真的程度越低（ ） 3．当隶属度函数有若干点取值为1，其余点取值为0时，该隶属度函数对应的模糊集 合可以看作一个经典集合（ ） 7、简答题：试述模糊计算的主要模块及其操作内容。 ???????≥-<-<-≤-=101100100 0),(~y x y x y x y x y x R ，，， 精选方案策划合集5篇 方案策划篇1 一、日本寿司店的总体目标 2. 产品定价及收入目标 产品定价寿司：甜鸡蛋寿司 12元加州反卷寿司12元烤鳗鱼寿司 12元樱花反卷寿司12元香辣牛肉寿司12元鱼松蟹棒寿司12元鱼松火腿寿司12元金枪鱼寿司8元球生菜寿司8元紫薯红薯寿司8元鱼松寿司 8元红心蛋黄寿司 8元飞鱼子寿司8元什锦色拉寿司 7元水果寿司 7元果冻寿司 6元火腿寿司 6元手卷：黄瓜手卷 5元／2个鱼松手卷 7元／2个金枪鱼手卷7元／2个色拉手卷 7元／2个烤鳗鱼手卷7元／2个饭团：红心蛋黄饭团 5元／2个紫薯饭团 5元／2个鱼松饭团 7元／2个金枪鱼饭团7元／2个火腿饭团 7元／2个预计每日将会有50份订单，每份订单平均10元，平均每份订单成本3元利润7元。每日将获得利润10x50=500元每日将获纯利润7x50=350元 收入目标 月收入：20190.00元年收入：240000.00元 员工工资以及支出经费：40000.00元年净收入：201900.00元 3. 发展目标 将日本寿司店发展成特色小资情调的店子。主要顾客为情侣、中 高消费水平学生、喜爱日韩的女生等。 本店以优雅的环境，日本特色的风味为主打。在提供就餐的同时能享受到不一样的优质服务。且寿司分为中高档，既能满足高消费水平学生的消费欲望，同时满足一般学生的购买能力。 立志将日本寿司店在我校附近立足，并以优质传统的特色服务收揽各新老顾客。 二、市场状况分析 1. 市场需求 自然生长的稻米和最新鲜的鱼生，用极致简单又饶有趣味的生食方式组合在一起，寿司已经迅速发展成为全世界都无法抗拒的美味新宠。寿司风潮正全面来袭。走进店堂，就可以看到一碟碟的寿司由传送带传送着，从眼前回转而过。自己伸手从传送带上取下自己爱吃的寿司，最后根据所吃的碟数来结账，这就是寿司。因其价格低廉、轻松随意，已经越来越受到普通消费者的欢迎。 作为全世界正越来越风行的日本寿司，正被越来越多追求品位和健康的人所钟爱。纽约、巴黎、伦敦、悉尼、香港，时髦都市中的寿司店，门前永远不缺时髦男女耐心排长队。寿司经营店也在中国不断增长。什么原因呢？它的魅力在于：第一、口味鲜美, 而且丰富多样的品种满足了不同口味、不同喜好的人们。寿司的制作原料可谓包罗万象, 不拘一格，从鱼类、贝类到牛肉、禽蛋甚至蔬菜、瓜果都可以制成风味各异的寿司。 第二、寿司符合人们健康饮食的标准。日本饮食在养生方面具有 多项式的乘法 多项式的乘法的法则： 一般地，多项式与多项式相乘，先用一个多项式的每一项乘以另一个多项式的每一项。然后把所得的积相加。 整式的乘法运算与化简 多项式的乘法 转化为单项式 与多项式相乘 代数式的化简求值 典型例题 一．整式的计算 1.)1-n -m )(n 3m (+ 2.若c bx ax x x ++=+-2 )3)(12(，求c b a ,,的值. 二．确定多项式中字母的值 1.多项式)32)(8x mx -+（中不含有x 的一次项，求m 的值？ 2.若))(23(22q px x x x +++-展开后不含3x 和2x 项，求q p ,的值。 三．与方程相结合 解方程：8)2)(2(32-=-+x x x x 四．化简求值： 化简并求值：)3(2)42)(2(2 2--++-m m m m m ，其中2=m 五．图形应用 1．有若干张如图所示的正方形A 类、B 类卡片和长方形C 类卡片，如果要拼成一个长为（2a +b ），宽为（a +2b ）的大长方形，则需要C 类卡片 张． 2.如图所示的正方形和长方形卡片若干张，拼成一个长为（a+3b ），宽为（2a+b ）的矩形，需要这三类卡片共________ 张． 3．如图，在边长为a 的正方形中挖掉一个边长为b 的小正方形，把余下的部分剪成两个直角梯形后，再拼成一个长方形，通过计算阴影部分的面积，验证了一个等式，这个等式是( ) A ．a 2－b 2＝(a ＋b )(a －b ) B ．(a ＋b )2＝a 2＋2ab ＋b 2 C ．(a －b )2＝a 2－2ab ＋b 2 D ．a 2－ab ＝a (a －b ) 最优控制论文 遗传算法的发展 摘要 最优控制是现代控制理论的核心，它研究的主要问题是：在满足一定约束条件下，寻求最优控制策略，使得性能指标取极大值或极小值。解决最优控制问题 的主要方法有古典变分法、极大值原理和动态规划。 最优控制理论已被应用于综合和设计最速控制系统、最省燃料控制系统、最 小能耗控制系统、线性调节器等。目前研究最优控制理论最活跃的领域有神经网 络优化、模拟退火算法、趋化性算法、遗传算法、鲁棒控制、预测控制、混沌优化 控制以及稳态递阶控制等。 作为一种比较新的一种新的优化算法—遗传算法(Genetic Algorithm, 简称G A ) 正在迅速发展。 遗传算法是一种基于生物自然选择与遗传机理的随机搜索与优化方法。近年来,由于遗传算法求解复杂优化问题的巨大潜力及其在工业工程领域的成功应用,这种算法受到了国内外学者的广泛关注。本文介绍了遗传算法的研究现状,描述了它的主要特点和基本原理,概述了它的理论、技术和应用领域,讨论了混合遗传算法和并行遗传算法,指出了遗传算法的研究方向,并对遗传算法的性能作了分析。 目录 1 前言 (1) 2 遗传算法基本理论..................................................... 1... 2.1 遗传算法的基本步骤.................................................. 1.. 2.2 遗传算法的现状..................................................... 2... 2.3 遗传算法的应用..................................................... 3... 2.3.1 函数优化 ..................................................... 3... 2.3.2 组合优化 ..................................................... 4... 2.3.3 生产调度问题 ................................................. 4... 2.3.4 自动控制 ..................................................... 4... 2.3.5 机器人学 ..................................................... 4... 2.3.6 图像处理 ..................................................... 4... 2.3.7 人工生命 ..................................................... 5... 2.3.8 遗传编程 ..................................................... 5... 2.3.9 机器学习 ..................................................... 5... 2.3.10 数据挖掘.................................................... 5... 3 遗传算法的研究方向................................................... 5... 参考文献............................................................ 7... 【实用】工作计划合集六篇 工作计划篇1 为了贯彻落实“安全第一，预防为主，综合治理”的方针，强化安全生产目标管理。结合工厂实际，特制定20xx年安全生产工作计划，将安全生产工作纳入重要议事日程，警钟长鸣，常抓不懈。 一、下半年目标 实现下半年无死亡、无重伤、无重大生产设备事故，无重大事故隐患，工伤事故发生率低于厂规定指标，综合粉尘浓度合格率达80%以上（如下表）。 二、指导思想 要以公司对20xx年安全生产目标管理责任为指导，以工厂安全工作管理制度为标准，以安全工作总方针“安全第一，预防为主。”为原则，以车间、班组安全管理为基础，以预防重点单位、重点岗位重大事故为重点，以纠正岗位违章指挥，违章操作和员工劳动保护穿戴为突破口，落实各项规章制度，开创安全工作新局面，实现安全生产根本好转。 三、牢固树立“安全第一”的思想意识 各单位部门要高度重视安全生产工作，把安全生产工作作为重要的工作来抓，认真贯彻“安全第一，预防为主”的方针，进一步增强安全生产意识，出实招、使真劲，把“安全第一”的方 针真正落到实处，通过进一步完善安全生产责任制，首先解决领导意识问题，真正把安全生产工作列入重要议事日程，摆到“第一”的位置上，只有从思想上重视安全，责任意识才能到位，才能管到位、抓到位，才能深入落实安全责任，整改事故隐患，严格执行“谁主管，谁负责”和“管生产必须管安全”的原则，力保安全生产。 四、深入开展好安全生产专项整治工作 根据工厂现状，确定出20xx年安全生产工作的重点单位、重点部位，完善各事故处理应急预案，加大重大隐患的监控和整改力度，认真开展厂级月度安全检查和专项安全检查，车间每周进行一次安全检查，班组坚持班中的三次安全检查，并要求生产科、车间领导及管理人员加强日常安全检查，对查出的事故隐患，要按照“三定四不推”原则，及时组织整改，暂不能整改的，要做好安全防范措施，尤其要突出对煤气炉、锅炉、硫酸罐、液氨罐等重要部位的安全防范，做好专项整治工作，加强对易燃易爆、有毒有害等危险化学品的管理工作，要严格按照《安全生产法》、《危险化学品安全管理条例》强化专项整治，加强对岗位现场的安全管理，及时查处违章指挥，违章操作等现象，限度降低各类事故的发生，确保工厂生产工作正常运行。 五、继续加强做好员工安全教育培训和宣传工作 工厂采取办班、班前班后会、墙报、简报等形式，对员工进行安全生产教育，提高员工的安全生产知识和操作技能，定期或 实习报告 一、实习题： 请写出计算两个以单链接表表示的多项式相乘的程序。 1．需求分析和说明 两个多项式相乘，可以利用两个多项式的加法来实现，因为乘法运算可以分 解为一系列的加法运算：C(x)=A(x)*B(x)=A(x)*(b1x+b2x2+…+b n x n)=∑ = n i i i x b x A 1 ) ( 先用其中一个多项式去乘以另一个多项式的每一项，得出的若干个多项式按照一定的顺序相加，即幂不同的按照升幂排列，幂相同的将系数相加。 例如： 对于(X->1+2X->2)*(2X->2+4X->3). X->1*(2X->2+4X->3)=2X->3+4X->4; 2X->2*(2X->2+4X->3)=4X->4+8X->5; 排列结果：2X->3+8X-4+8X->5 2．设计 用两个单链表的存储两个多项式，每个结点包含单项式的系数，幂和指向下一个元素地址的指针。用其中的一个多项式乘以另一个多项式的每一项，随后将所得结果按照升幂顺序排列，最后得到结果。 存储结构： //单项式结构 struct Term { float coef; // 系数。 int exp; // 幂指数。 Term( float c, int e) { coef = c; exp = e;} Term( ) { } friend int operator == (const Term & L, const Term & T ) { return L.exp == T.exp; } friend int operator > (const Term & L, const Term & T ) { return L.exp > T.exp; } friend int operator < (const Term & L, const Term & T ) { return L.exp < T.exp; } friend Term & operator += ( Term & L, const Term & T ) { L.coef += T.coef; return L; } //幂指数相同，则系数相加。 friend Term & operator *=(Term &L, const Term &T){ //实现单项式乘法 L.coef*=T.coef; L.exp+=T.exp; 第二章 遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当x ? S x ∈，(ρi i b a <，i 12）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。 2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。 定义：由问题空间向GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。 1）2）3）它们对1） 2） k =1,2,…,K; l =1,2,…,L; K=2L 其中，个体的向量表示为),,,(21kL k k k a a a a =，其字符串形式为kL k k k a a a s 21=，s k 称为个体a k 对应的位串。表示精度为)12/()(--=?L u v x 。 将个体又位串空间转换到问题空间的译码函数],[}1,0{:v u L →Γ的公式定义为： 对于n 维连续函数),,2,1](,[),,,,(),(21n i v u x x x x x x f i i i n =∈=，各维变量的二进制 【精选】计划方案合集9篇 计划方案合集9篇 为有力保证事情或工作开展的水平质量，时常需要预先制定一份周密的方案，方案是从目的、要求、方式、方法、进度等方面进行安排的书面计划。那么大家知道方案怎么写才规范吗？以下是小编为大家收集的计划方案9篇，仅供参考，大家一起来看看吧。计划方案篇1 一指导思想深入学习《幼儿园教育指导纲要》，深刻把握《纲要》精髓，高举素质教育的旗帜，扮演好教师的多重角色，充分认知和尊重幼儿生命特性，遵循幼儿身心发展规律和学习特点，自觉创造与生命相和谐、与个体生命相一致的教育；在“存精、吸纳、创新”的课程研究总原则下，突显语言特色，坚持课程与课题研究整合相融求效益，不断深化园本课程建设，推动教育科研向纵深发展。 二、工作目标 1、立足实际，深入课改，把《纲要》精神转化为实际的、科学的教育实践能力，促进教师专业化成长。 2、突显我园语言教育特色，向全市展示教育成果。 3、开拓教育资源，在有目的、有准备的生活实践中提高幼儿语言交往能力。三、具体内容及措施（一）立足实际，在课改中促进教师的专业化成长以本园实际为基点的课程改革和课程实施是最具说服力和生命力的，脚踏实地研究课程的过程本身就是一个促进教师专业化成长的过程。 1、咀嚼消化有关理论，厚实实践基础随着终身教育的提出和学习化社会的到来，基础教育的功能正在被重新定义。我们必须根据新的基础教育理念来调整幼儿教育的价值取向，在社会和教育的整体结构中，正确而清醒地把握幼教的实践方向。要求教师根据新的基础教育理念来审视和反思自己的工作，自觉地规范自己的教育行为，理性地构建自己的教育观念。学习重点：《从理念到行为——幼儿园教育指导纲要行动指南》、《儿童的一百种语言解读》、有关幼儿语言教育的最新理论等。学习形式：自学——小组研讨——园部主题性“头脑风暴”——教育实例 2、反思总结，创造性实施课程以主题形式组织、实施课程是课程实践的主要形式。我园一直使用南师大与信谊基金出版社共同出版的《幼儿园活动整合课程》，这一课程是帮助我们更好落实新《纲要》精神、将先进教育观念落实到教育行为中去 #include 龙源期刊网 https://www.doczj.com/doc/bc5303738.html, 基于遗传算法的PID控制概述 作者：张亚飞 来源：《卷宗》2013年第08期 摘要：基于PID控制应用的广泛性，本文简要阐述了遗传算法理论的关键思想及其在PID 控制中的应用策略，并用Matlab软件对一个控制实例进行了仿真研究。 关键词：PID控制；遗传算法；Matlab仿真 0 引言 PID控制作为最早实用化的控制算法已有70多年历史，现在仍然是控制系统中应用最为 普遍的一种控制规律。它所涉及的算法和控制结构简单，实际经验以及理论分析都表明，这种控制规律对许多工业过程进行控制时，一般都能得到较为满意的控制效果。随着控制理论的 发展，尤其是人工智能研究的日趋成熟，许多先进的算法理论逐渐被应用到传统的PID控制中，并取得了更为优越的控制效果。本文就以传统PID控制和遗传算法理论为基础，简述了基于遗传算法整定的PID控制基本理论和方法。 1 PID控制 通过将偏差的比例（Proportional）、积分（Integral）、微分（Derivative）进行线性组合构成控制量，对被控对象进行控制，这种控制方法叫做PID控制。在自动控制发展的历程中，常规PID控制得到了广泛的应用，整个控制系统由常规PID控制器和被控对象组成，根据系统给定值r（t）与实际输出值y（t）存在的控制偏差e（t）=r（t）-y（t）组成控制规律。PID控制器将偏差e（t）的比例-积分-微分通过线性组合构成控制量，对被控对象进行控制。其基本控制规律为 式中，Kp为比例增益，Ti为积分时间常数，Td为微分时间常数，u（t）为控制量，e （t）为偏差。 2 遗传算法基本操作 遗传算法，简称GA（Genetic Algorithms），是由美国Michigan大学的Holland教授于上世纪六十年代率先提出的一种高效并行全局最优搜索方法。遗传算法是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型，它将“优胜劣汰，适者生存”的生物进化理论引入优化参数形成的编码串联群体中，按所选择的适配值函数通过遗传中的复制、交叉和变异对种群个体进行筛选，并保留适配值高的种群个体，组成新的群体。新的群体既继承了上一代的种群信息，又包含有优于上一代的个体信息，这样周而复始，种群中个体的适应度不断提高，直到满足一定的特定条件而停止运算，从而得到最优解。最新设计方案范文合集6篇
深入探究多项式乘法的快速算法
遗传算法合集
算法合集之《左偏树的特点及其应用》
设计方案范文合集八篇
计划方案合集10篇
浙教版七年级数学下册多项式的乘法作业练习
计算智能习题合集
精选方案策划合集5篇
多项式的乘法典型例题(整理)
最优控制-遗传算法综述
【实用】工作计划合集六篇
数据结构 多项式乘法
遗传算法的基本原理
【精选】计划方案合集9篇
多项式算法
基于遗传算法的PID控制概述
相关主题
文本预览