求解递推数列第n项的MATLAB实现

数学与统计学院课程设计（实习）报告第1页求解递推数列第n项的MATLAB实现1绪论1.1MATLAB简介随着计算机技术的不断发展，计算机已成为应用数学工作者解决数学问题的主要运算工具，数学运算软件如：MATLAB，Mathematica，Maple等，已经被广泛使用。MATLAB是面对科学计算、可视化以及交互式程序设计的高科技计算环境。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须要进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言的的编辑模式。MATLAB可以进行矩阵运算、绘制函数和数学、实现算法、创建用户界面、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域。1.2课题的背景在生活中，很多计数问题到最后都归结为一些递推公式，如果单依赖数学的方法，有些递推公式按照如今的数学发展水平是很难找出通项公式的，在解决实际问题中，不免涉及到求解第n项的值，如果n比较大，手算的话得从第一项一直计算到第n项，也许算到其中的某一项突然算错了，最后得到的值和预估的值不一样，又得从头算起，这样费时费力。数学软件的形成为这一计算提供了很大的方便，只需要根据递推关系编一个程序，很快就能得出计算结果。本文选了特殊的并且很有代表性的四个递推数列，给出求解其第n项的算法，解决和递推数列相关的应用型问题。1.3MATLAB相比于其他程序设计语言的优点MATLAB作为一个数学运算工具，它将矩阵作为基本的存储单元。矩阵运算很快，代码复杂度小。它定义数据时无需声明数据类型，各种函数的运算可以直接进行符号运算，更加的面向于用户。MATLAB的工具箱也很丰富，在图像处理、信号处理、仿真等方面的工具箱里的工具、示例非常多，功能非常强大。2用MATLAB求解递推数列第n项数学与统计学院课程设计（实习）报告第2页数列是按一定次序排列的一列数。数列中的每一个数都叫做这个数列的项。排在第一位的数称为这个数列的第1项，排在第二位的数称为这个数列的第2项……排在第n位的数称为这个数列的第n项。如果数列{[]}an的第n项与它前一项或几项的关系可以用一个式子来表示，那么这个公式叫做这个数列的递推公式。而用递推公式表示的数列就叫做递推数列。不是所有的递推数列在至今的数学发展的水平下都能求得通项公式，对于这些数列，可以用MATLAB编程求解第n项，如此既方便了很多实际问题，也便于数列通项公式的研究。2.1Fibonacci数列2.1.1Fibonacci数列简介Fibonacci数列，又称黄金分割数列、小兔子数列，因数学家斐波那契以兔子繁殖为例而引入。在现代物理、化学、准晶体等领域，Fibonacci数列都有直接应用。数学上，Fibonacci被递归的方法定义为：()(1)(2),2,(0)1,(1)1fnfnfnnnffFibonacci数列有很多漂亮的数学性质，比如:从第二项开始，每个奇数项的平方都比前后两项之积少1，每个偶数项的平方都比前后两项之积多1；第2n项代表了集合{1,2,,}n中所有不包含相邻正整数的子集个数。Fibonacci数列中的Fibonacci数经常出现在我们的生活中，比如松果、凤梨、树叶的排列、某些花朵的花瓣数，超越数e，黄金矩阵、黄金分割、等螺旋线、杨辉三角等。2.1.2求解Fibonacci数列第n项算法1．递归算法%建立M函数文件functionf=fib(n)ifn==0||n==1f=1;%特殊情况，递归结束的标志else数学与统计学院课程设计（实习）报告第3页f=fib(n-1)+fib(n-2);%递归调用fib函数endend2．循环算法%建立M函数文件functionf=fib(n)a=1;b=1;ifn==0||n==1f=1;%前两项为特殊情况elseforx=2:2:n%两个项一循环a=a+b;%奇数项把前面最近的偶数项和奇数项加起来b=a+b;%偶数项把前面最近的奇数项和偶数项加起来endifmod(n,2)f=b;%奇数时函数返回belsef=a;%偶数时函数返回aendendend3．矩阵计算原理：Fibonacci数列的递推公式可以转换为：(1)11()()10(2)fnfnfnfn数学与统计学院课程设计（实习）报告第4页)0()1(0111)1()(1ffnfnfn%建立M函数文件functionf=fib(n)a=[1110];b=a^(n-1)*[1;1];f=b(1);end2.1.3Fibonacci数应用问：把一对兔子（雌、雄各一只）在某年的开始放到围栏中，每个月这对兔子都生出一对新兔，其中雌、雄各一只。由第二个月开始，每对新兔每个月也生出一对新兔，也是雌、雄各一只，问一年后围栏中有多少对兔子？解：对于1,2,,n令)(nf表示第n个月开始时围栏中的兔子对数，显然有1)1(f，2)2(f。在第n个月的开始，那些第1n个月初已经在围栏中的兔子仍然存在，而且每对在第2n个月初就存在的兔子将在第1n个月生出一对新兔来，再令1)0(f有：()(1)(2),2,(0)1,(1)1fnfnfnnnff用MATLAB求解，在控制台下输入代码fib(12)得ans=233用MATLAB画出小兔子数列的增长曲线，在M文件里输入代码forn=1:12A(1,n)=fib(n);%循环得出第n月的小兔子个数endplot(1:12,A)%以横坐标为月份，纵坐标为小兔子个数作图数学与统计学院课程设计（实习）报告第5页得出的figure如下图：图2.1小兔子数列增长曲线2.2Catalan数列2.2.1Catalan数列简介Catalan数是组合数学中常出现在各种计算问题中的数列，前几项为：1，1，2，5，14，132，429，1430，…Catalan数满足递推式：()(0)(1)(1)(2)(1)(0),2,(0)1,(1)1hnhhnhhnhnhnnhh目前发现的Catalan数的应用已有上百种，比如：括号化乘积表达式的方案数；一个栈的进栈序列为1,2,3,…,n,的出栈序列；凸多边形的三角划分；给定N个节点组成二叉树的种数，非降路径不穿过对角线的路径的方法数。2.2.2求解Catalan数列第n项算法%建立M函数文件functionc=catalan(n)ifn==0||n==1c=1;%特殊情况，递归结束的标志else数学与统计学院课程设计（实习）报告第6页c=0;forx=0:(n-1)c=c+catalan(x)*catalan(n-1-x);%递归调用catalan函数endendend2.2.3Catalan数列应用给定一个平面点集K，如果对K中任意两点p和q，连接p和q的线段上的所有的点都在K中，则称点集是凸的。问：设R是一个6条边的凸多边形区域，用3条不在内部相交的对角线把R分成4个三角形。求有多少种不同的分法？解：令nh表示分一个1n条边的凸多边形为三角形的方法数。定义11h.当2n时，1n边形就是三角形，所以12h.当3n时，考虑一个有41n条边的凸多边形区域R。任取多边形的一条边a，a的两个端点记作1A，1nA。以a为一条边，以多边形的任一端点)1,,2,1(1nkAk与1A，1nA的连线为两条边构成三角形T。T把R分割成1R和2R两部分。1R为1k边形，2R为1kn边形，因此1R可以用kh种方法来划分，2R可以用knh种方法来划分。这就得到了下面的递推方程：12,111hnhhhnkknkn)1(nhhn等价于第1n项catalan数用MATLAB求解，在控制台下输入代码catalan(5)得ans=422.3第二类Stirling数2.3.1第二类Stirling数简介Stirling数出现在许多组合枚举问题中。把n个不同的球放到r个相同的盒子里，假数学与统计学院课程设计（实习）报告第7页设没有空盒，则放球方案数记作rn，称为第二类Stirling数。例如，把dcba,,,四个球放到两个盒子里，不允许有空盒，则放球的方法数有以下7种：|,|,|,|,|,|,|abcdbacdcabddabcabcdacbdadbc.所以472第二类Stirling数具有的性质:1．初始条件：10,1,1,,1012122nnnnnnnnn2．满足下面的递推方程：11,11nnnrnrrrr证明：要把n个不同的球恰好放入r个盒子，先取一个球，比如是na，然后把所有的放法分成两类：na单独放在一个盒子里，放法为11rn不是单独放在一个盒子里，可以先把其余的1n个球放到r个盒子里，有rn1种放法。对于其中的任何一种放法，加入na的方法有r种，由乘法法则，放球的方法数是1nrr根据加法法则，等式成立。2.3.2求解第二类Stirling数rn项算法%建立M函数文件数学与统计学院课程设计（实习）报告第8页functions=striling(n,r)ifn==r||r==1s=1;%特殊情况，递归结束的标志elseifr==0||nrs=0;elses=r*striling(n-1,r)+striling(n-1,r-1);%递归调用striling函数endend2.4杨辉三角2.4.1杨辉三角简介杨辉三角，又称贾宪三角，帕斯卡三角形，是二项式系数在三角形中的一种几何排列。杨辉三角有多种重要的性质。前提：端点的数为1。1.每个数等于它上方两数之和。2.每行数字左右对称，由1开始逐渐变大。3.第n行的数字有n项。4.第n行数字和为12n。5.第n行的个数可表示为m，)1,1(mnC即为从1n个不同元素中取1m个元素的组合数。6.第n行的第m个数和第1mn个数相等。7.nba)(的展开式中各项系数依次对应杨辉三角的第)1(n行中的每一项。8.将第12n行第1个数，跟第22n行第3个数，第32n行第5个数……连成一线，这些数的和是第14n个斐波那契数；将第n2行第2个数)1(n，跟第12n行第4个数，第22n行第6个数……这些数之和是第24n个斐波那契数。数学与统计学院课程设计（实习）报告第9页1234567891011121314151611112113311464115101051161520156117213535217118285670562881193684126126843691110451202102522101204510111155165330462462330165551111126622049579292479249522066121...图2.2杨辉三角2.4.2求解杨辉三角),(yx位置算法functionyh=YH(x,y)ifx==1||y==x+1yh=1;%特殊情况，递归结束的标志elseyh=YH(x-1,y-1)+YH(x-1,y);%递归调用YH函数end结论对于递推数列的求第n项值的问题，本文给出了在MATLAB下求解的过程，虽然只选择了四个代表性的递推公式，但是这一过程适用于所有的递推公式求解的应用型问题。通过这次课程设计，我初步了解了如何用MATLAB进行编程，对递归算法也有了较深的理解，接触到了这四种特殊的递推数列在实际中的应用。由于本人的编程能力不高，所以有些递归算法无法转换为循环算法，建立递归工作数学与统计学院课程设计（实习）报告第10页栈，甚至队列来实现。从而增