递推法在c语言中的简单应用

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

1、数学的魅力—递推法1236003班李策6120610306递推法（其实就是递归）简介：递推法是一种重要的数学方法，其特点是问题的某种情景与其他情景有确定的关系，即递推式。因此，运用递推法求解问题的关键是确定递推式，而递推分为顺推和逆推（由基线情景决定），但构建递推式的方式相同，即将一种情景等价的用其他情景表示，要求表示方式具有一般性。用例如约瑟夫问题，汉诺塔，卡特兰数等。递推法经典运用之约瑟夫问题：n个人围成一圈，分别编号1、2、3…n,从第一个人开始报数，数到m的人出圈；再由下一个人开始报数，数到m的人出圈；输出最后

2、剩下的人的编号。n,m由键盘输入。为了方便讲解，我们讨论m=3时的情景,称最后剩下的人为“胜利者”。对于n个人报数的情况，记胜利者的编号为an,根据递推法的思维方式，我们只需要将n个人报数的情景转化为n-1个人报数的情景，并找到合适的数学表达式建立二者的对应关系即可。128734465n（1）n个人报数时，编号为3的人不会是胜利者，所以剔除3。（2）根据游戏规则，对剩下的n-1个人重新编号。这样我们便得到了n-1个人的情景。虽然编号改变，但很明显，两种情景胜利者的位置相同，即只需确定两种情况相同位置编号的关系即可。（3

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

4、和数学表达式确定不同情景相同位置的人的编号对应关系。递推法经典运用之汉诺塔记三根柱子分别为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:递推式构建过程与课本模拟移动路线思路相同递推法经典运用之Catalan数（卡特兰数）问题引入：求在圆周上有2n个点,将这些点成对连接起来，使得所得到的n条线段不相交

5、的方法数。（为了方便说明，我们称其为2n元连线）12k将圆周上的2n个点编号1—2n；记圆周上有2n个点时方法数为an；将1与2k链接（k为1到n,若将1与奇数点连接，两段圆弧上点的个数为奇数，不能进行2X元链接）；两端圆弧分别看成两个孤立的2X元链接问题（不孤立则有线与1-2k相交），其方法数分别为ak–1和an–k，由乘法计数原理，该情景方法数为ak–1*an–k；由于k取值为1到n，所以共有n种情景，由加法计数原理将各种情景方法数相加即可。递推式见下页用a(i)代替ai，补充定义a(0)=0;构建递推式如下：a(

6、n)=a(0)*a(n-1)+a(1)*a(n-2)+…+a(k-1)*a(n-k)+…+a(n-2)*a(1)+a(n-1)*a(0)且a(0)=1,a(1)=1其通项公式为：卡特兰数在C中的应用：（1）括号化问题（2）出栈次序问题（3）将多边形划分为三角形问题（4）给定节点的二叉树问题基线情况讨论：对于约瑟夫问题，我们有an=(an-1+3)%n,显然a1=1。（1）a1=1真的可以作为递推的基线情况吗？（2）递推是在n(人数)>m（报到m出列）的情况下推出的，对于n

7、n–1+M*an–2,a1,a2一定是基线情况吗？（4）如果不是，基线情况该怎么确定？确定约瑟夫问题的基线情况：想确定约瑟夫问题的基线情况，只需要证明递推式对于人数n小于出列编号m的情况依然满足即可。132k+1kk-14n-2n-1nm=c*n+k分界处1n-k-2n-kn-k+1n-k-1n-k+2n-k+3n-k+4n-1分界处将图分为两部分，由于两部分编号均递增且增值为1，所以只需证明两部分开头满足递推(1+c*n+k)%n=k+1成立(n-k+1+c*n+k)%n=1成立即a(1)为基线情况用例：有n个标牌成

8、圆排列，编号1,2,3…n,用4种不同的颜色染色，要求相邻两标牌颜色不同，求有多少种染色方法？建立递推：an=2*an–1+3*an–2n个标牌染色方法数为a(n),去掉n号标牌，n-1号标牌有两种情况（与1颜色相同或不同）；若与1号颜色相同，n-2号与1号不同，n号标牌有3种染色方式，去掉n-1号，转化为n-2个标牌的情景，所以