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

数学的魅力递推法,1236003班李策6120610306,递推法（其实就是递归）简介：递推法是一种重要的数学方法，其特点是问题的某种情景与其他情景有确定的关系，即递推式。因此，运用递推法求解问题的关键是确定递推式，而递推分为顺推和逆推（由基线情景决定），但构建递推式的方式相同，即将一种情景等价的用其他情景表示，要求表示方式具有一般性。用例如约瑟夫问题，汉诺塔，卡特兰数等。,递推法经典运用之约瑟夫问题：n个人围成一圈，分别编号1、2、3n,从第一个人开始报数，数到m的人出圈；再由下一个人开始报数，数到m的人出圈；输出最后剩下的人的编号。n,m由键盘输入。为了方便讲解，我们讨论m=3时的情景,称最后剩下的人为“胜利者”。,对于n个人报数的情况，记胜利者的编号为an,根据递推法的思维方式，我们只需要将n个人报数的情景转化为n-1个人报数的情景，并找到合适的数学表达式建立二者的对应关系即可。,1,2,8,7,3,4,4,6,5,n,（1）n个人报数时，编号为3的人不会是胜利者，所以剔除3。（2）根据游戏规则，对剩下的n-1个人重新编号。这样我们便得到了n-1个人的情景。虽然编号改变，但很明显，两种情景胜利者的位置相同，即只需确定两种情况相同位置编号的关系即可。（3）由于外圈以内圈4号为起始位置，所以相同位置NUMn=NUMn-1+3，但n-2+3n、n-1+3n，所以表达式修正为NUMn=（NUMn-1+3）%n,3,1,2,5,n-2,n-3,n-1,注意a=m%n,a的范围是0到n-1,情境中并没有编号为0的人。,由前面的分析我们找到了两种情景相同位置编号的关系表达式：NUMn=（NUMn-1+3）%n。所以胜利者编号对应关系为an=(an-1+3)%n,显然a1=1(基线情况)。分析过程小结：运用递推法解约瑟夫问题的关键在于正确理解其思维方式，即将不同情景胜利者的位置固定，根据数学模型和数学表达式确定不同情景相同位置的人的编号对应关系。,递推法经典运用之汉诺塔记三根柱子分别为ABC，将n片黄金片由A移到B或C的操作数为an,下面构建递推式：（1）将前n-1片黄金片移到C柱子上，操作数为an1;（2）将第n片黄金片移到B柱子上，操作数为1；（3）将前n-1片黄金片移到B柱子上，操作数为an1;（4）构建递推式：an=2*an1+1Ps:递推式构建过程与课本模拟移动路线思路相同,递推法经典运用之Catalan数（卡特兰数）问题引入：求在圆周上有2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数。（为了方便说明，我们称其为2n元连线）,1,2k,将圆周上的2n个点编号12n；记圆周上有2n个点时方法数为an；将1与2k链接（k为1到n,若将1与奇数点连接，两段圆弧上点的个数为奇数，不能进行2X元链接）；两端圆弧分别看成两个孤立的2X元链接问题（不孤立则有线与1-2k相交），其方法数分别为ak1和ank，由乘法计数原理，该情景方法数为ak1*ank；由于k取值为1到n，所以共有n种情景，由加法计数原理将各种情景方法数相加即可。递推式见下页,用a(i)代替ai，补充定义a(0)=0;构建递推式如下：a(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出列）的情况下推出的，对于nm成立吗？（3）对于所有的递推，如an=K*an1+M*an2,a1,a2一定是基线情况吗？（4）如果不是，基线情况该怎么确定？,确定约瑟夫问题的基线情况：想确定约瑟夫问题的基线情况，只需要证明递推式对于人数n小于出列编号m的情况依然满足即可。,1,3,2,k+1,k,k-1,4,n-2,n-1,n,m=c*n+k,分界处,1,n-k-2,n-k,n-k+1,n-k-1,n-k+2,n-k+3,n-k+4,n-1,分界处,将图分为两部分，由于两部分编号均递增且增值为1，所以只需证明两部分开头满足递推,(1+c*n+k)%n=k+1成立(n-k+1+c*n+k)%n=1成立即a(1)为基线情况,用例：有n个标牌成圆排列，编号1,2,3n,用4种不同的颜色染色，要求相邻两标牌颜色不同，求有多少种染色方法？建立递推：an=2*an1+3*an2n个标牌染色方法数为a(n),去掉n号标牌，n-1号标牌有两种情况（与1颜色相同或不同）；若与1号颜色相同，n-2号与1号不同，n号标牌有3种染色方式，去掉n-1号，转化为n-2个标牌的情景，所以方法数为3*a(n-2);若与1号颜色不同，n有2种染色方式，去掉n转化为n-1个标牌的情况，方法数为2*a(n-1);由加法计数原理可构建上述递推式。a(1)=4;a(2)=3*4=12;a(3)=24;a(4)=84;a(5)=240很明显a(3)2*a(2)+3*a(1),结论：一般情况下，我们要计算出多组简单情景的结果，对于第一组满足递推式的结果可以作为基线情况，其后的结果可以用递推法解得，而对于基线情况之前的结果要单独说明。,如何对数学定位？（1）最大公约数*最小公倍数=两个数的乘积（2）3000以上没有数满足类似水仙花数的性质可见，数学技巧的应用可以起到锦上添花的作用，但是数学只能解决一部分问题数学只是一门工具学科，所以我们要应用数学而不是依赖数学。数学绝对可以帮助优化程序，学好编程，但是不会让你学会编程。学好是建立在学会的基础上。所以，希望同学们在有意积累数学知识