递推法在C语言中的简单应用.ppt

《递推法在C语言中的简单应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学的魅力—递推法1236003班李策6120610306Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.递推法（其实就是递归）简介：递推法是一种重要的数学方法，其特点是问题的某种情景与其他情景有确定的关系，即递推式。因此，运用递推法求解问题的关键是确定递推式，而递推分为顺推和逆推（由基线情景决定），但构建递推式的方式相同，即将一种情景等价的用其他情景表示，要求表示方式具有一般性。用例如约瑟夫问题，汉诺塔，卡特兰数等。Evaluat

2、iononly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.递推法经典运用之约瑟夫问题：n个人围成一圈，分别编号1、2、3…n,从第一个人开始报数，数到m的人出圈；再由下一个人开始报数，数到m的人出圈；输出最后剩下的人的编号。n,m由键盘输入。为了方便讲解，我们讨论m=3时的情景,称最后剩下的人为“胜利者”。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyri

3、ght2004-2011AsposePtyLtd.对于n个人报数的情况，记胜利者的编号为an,根据递推法的思维方式，我们只需要将n个人报数的情景转化为n-1个人报数的情景，并找到合适的数学表达式建立二者的对应关系即可。128734465n（1）n个人报数时，编号为3的人不会是胜利者，所以剔除3。（2）根据游戏规则，对剩下的n-1个人重新编号。这样我们便得到了n-1个人的情景。虽然编号改变，但很明显，两种情景胜利者的位置相同，即只需确定两种情况相同位置编号的关系即可。（3）由于外圈以内圈4号为起始位置，所以相同位置NUMn=NUMn-1+3，但n-2+3>n、n-1+3>n，所以表达式

4、修正为NUMn=（NUMn-1+3）%n3125n-2n-3n-1注意a=m%n,a的范围是0到n-1,情境中并没有编号为0的人。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.由前面的分析我们找到了两种情景相同位置编号的关系表达式：NUMn=（NUMn-1+3）%n。所以胜利者编号对应关系为an=(an-1+3)%n,显然a1=1(基线情况)。分析过程小结：运用递推法解约瑟夫问题的关键在于正确理解其思维方式，即将不同情景胜利者的位

5、置固定，根据数学模型和数学表达式确定不同情景相同位置的人的编号对应关系。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.递推法经典运用之汉诺塔记三根柱子分别为ABC，将n片黄金片由A移到B或C的操作数为an,下面构建递推式：（1）将前n-1片黄金片移到C柱子上，操作数为an–1;（2）将第n片黄金片移到B柱子上，操作数为1；（3）将前n-1片黄金片移到B柱子上，操作数为an–1;（4）构建递推式：an=2*an–1+1Ps:递推式构

6、建过程与课本模拟移动路线思路相同Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.递推法经典运用之Catalan数（卡特兰数）问题引入：求在圆周上有2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。（为了方便说明，我们称其为2n元连线）12k将圆周上的2n个点编号1—2n；记圆周上有2n个点时方法数为an；将1与2k链接（k为1到n,若将1与奇数点连接，两段圆弧上点的个数为奇数，不能进行2X元链接）；两端圆弧分别看成

7、两个孤立的2X元链接问题（不孤立则有线与1-2k相交），其方法数分别为ak–1和an–k，由乘法计数原理，该情景方法数为ak–1*an–k；由于k取值为1到n，所以共有n种情景，由加法计数原理将各种情景方法数相加即可。递推式见下页Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.用a(i)代替ai，补充定义