📄 2_2.htm
字号:
<head><link rel="stylesheet" href="../style.css"></head><h1>§2.2 递推关系 </h1></p> <p> 利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下： </p> <p> 例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。 </p> <p> Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。 </p> <p> 算法：N=2时 </p> <p> 最后把B上的圆盘移到C上</p> <p>** </p> <p>到此转移完毕 </p> <p> 假定n-1个盘子的转移算法已经确定。 先把上面的n-1个圆盘经过C转移到B。 第二步把A下面一个圆盘移到C上 最后再把B上的n-1个圆盘经过A转移到C上 </p> <p>**</p> <p> 上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，…以此类推。 </p> <p> 算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 </p> <p> n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有算法复杂度为： </p> <blockquote> <p><img border="0" src="2_2.pic/image002.gif" width="263" height="21"></p> <p><img border="0" src="2_2.pic/image004.gif" width="235" height="24"></p> </blockquote> <p> H(x)是序列h(1)，h(2)，h(3)，…的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式也可以依次求得h(2)，h(3)，…，这样的连锁反应关系，叫做递推关系。 </p> <p> 下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。 </p> <p> <img border="0" src="2_2.pic/image006.gif" width="235" height="24"></p> <p> <img border="0" src="2_2.pic/image008.gif" width="287" height="21"></p> <p> <img border="0" src="2_2.pic/image010.gif" width="303" height="7"></p> <p> <img border="0" src="2_2.pic/image012.gif" width="277" height="51"></p> <p>根据(2-2-1)，</p> <p> <img border="0" src="2_2.pic/image014.gif" width="295" height="21"></p> <p> <img border="0" src="2_2.pic/image016.gif" width="285" height="24"></p> <p>或利用递推关系(2-2-1)有 </p> <p> <img border="0" src="2_2.pic/image018.gif" width="125" height="24"></p> <p> <img border="0" src="2_2.pic/image020.gif" width="127" height="24"></p> <p> +) … … … </p> <p> --------------------------------</p><p> <img border="0" src="2_2.pic/image022.gif" width="221" height="24"></p><p>上式左端为：</p><p> <img border="0" src="2_2.pic/image024.gif" width="300" height="24"></p><p>右端第一项为：</p><p> <img border="0" src="2_2.pic/image026.gif" width="307" height="48"></p><p>右端第二项为：</p><p> <img border="0" src="2_2.pic/image028.gif" width="153" height="24"></p><p>整理得</p><p> <img border="0" src="2_2.pic/image030.gif" width="200" height="44"></p><p>这两种做法得到的结果是一样的。即：</p><p> <img border="0" src="2_2.pic/image032.gif" width="143" height="44"></p><p> 如何从母函数得到序列h(1)，h(2)，h(3)，…？下面介绍一种化为部分分数的算法。</p> <p>令</p> <p> <img border="0" src="2_2.pic/image034.gif" width="277" height="91"></p><p> <img border="0" src="2_2.pic/image036.gif" width="173" height="21"></p><p>由上式可得：</p><p> <img border="0" src="2_2.pic/image038.gif" width="89" height="48"><img border="0" src="2_2.pic/image040.gif" width="20" height="16"><img border="0" src="2_2.pic/image042.gif" width="99" height="21"></p><p>即：</p><p> <img border="0" src="2_2.pic/image044.gif" width="307" height="139"></p><p>因为： </p><p> <img border="0" src="2_2.pic/image046.gif" width="117" height="45"></p><p> 例2. 求n位十进制数中出现偶数个5的数的个数。 </p> <p> 先从分析n位十进制数出现偶数个5的数的结构入手p<sub>1</sub>p<sub>1</sub><sup>...</sup>p<sub>n-1</sub>是n-1位十进制数，若含有偶数个5，则p<sub>n-1</sub>取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若p<sub>1</sub>p<sub>1</sub><sup>...</sup>p<sub>n-1</sub>只有奇数个5，则取p<sub>n</sub>=5，使p<sub>1</sub>p<sub>1</sub><sup>...</sup>p<sub>n-1</sub>p<sub>n</sub>成为出现偶数个5的十进制数。 </p> <p> 解法1： </p> <p> 令a<sub>n</sub>位十进制数中出现5的数的个数，b<sub>n</sub>位十进制数中出现奇数个5的数的个数。 故有： </p> <p> <img border="0" src="2_2.pic/image063.gif" width="305" height="51"></p><p> (2-2-2)式中的a<sub>n</sub>=9a<sub>n</sub>+b<sub>n-1</sub>表达了含有偶数个5的n位十进制数的两个组成部分。9a<sub>n-1</sub>表达由含有偶数个5的n-1位十进制数p<sub>1</sub>p<sub>1</sub><sup>...</sup>p<sub>n-1</sub>，令p<sub>n</sub>取5以外的0，1，2，3，4，6，7，8，9九个数中的一个数构成的。b<sub>n</sub>项表示当p<sub>1</sub>p<sub>1</sub><sup>...</sup>p<sub>n-1</sub>是含有奇数个5的n-1位十进制数，令p<sub>n</sub>=5而得p<sub>1</sub>p<sub>1</sub><sup>...</sup>p<sub>n-1</sub>p<sub>n</sub>是含偶数个5的n位十进制数。 </p> <p> b<sub>n</sub>=9b<sub>n-1</sub>+a<sub>n-1</sub>也有类似解释。 </p> <p> (2-2-2)是关于序列{a<sub>n</sub>}和{b<sub>n</sub>}的连立关系。 </p> <p> 设序列{a<sub>n</sub>}的母函数为A(x)，序列{b<sub>n</sub>}的母函数为B(x)。 即： </p> <p> <img border="0" src="2_2.pic/image093.gif" width="231" height="104"></p><p> <img border="0" src="2_2.pic/image095.gif" width="247" height="7"></p><p> <img border="0" src="2_2.pic/image097.gif" width="156" height="21"></p><p> <img border="0" src="2_2.pic/image099.gif" width="153" height="99"></p><p> <img border="0" src="2_2.pic/image095.gif" width="247" height="7"></p><p> <img border="0" src="2_2.pic/image103.gif" width="168" height="21"></p><p> <img border="0" src="2_2.pic/image105.gif" width="180" height="21"></p><p>又： </p><p> <img border="0" src="2_2.pic/image107.gif" width="225" height="77"></p><p> <img border="0" src="2_2.pic/image095.gif" width="247" height="7"></p><p> <img border="0" src="2_2.pic/image110.gif" width="153" height="21"></p><p>故得关于母函数A(x)和B(x)得连立方程组： </p><p> <img border="0" src="2_2.pic/image112.gif" width="173" height="48"></p><p> <img border="0" src="2_2.pic/image114.gif" width="320" height="72"></p><p> <img border="0" src="2_2.pic/image116.gif" width="328" height="99"></p><p> <img border="0" src="2_2.pic/image118.gif" width="347" height="88"></p><p>解法二： </p><p> n-1位的十进制数的全体共9x10<sup>n-2</sup> 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有： </p> <p> <img border="0" src="2_2.pic/image122.gif" width="236" height="75"></p><p>令 </p><p> <img border="0" src="2_2.pic/image124.gif" width="233" height="51"></p><p> <img border="0" src="2_2.pic/image125.gif" width="247" height="6"></p><p> <img border="0" src="2_2.pic/image127.gif" width="305" height="25"></p><p> <img border="0" src="2_2.pic/image129.gif" width="315" height="204"></p><p> 例三：从n个元素a<sub>1</sub>,a<sub>2</sub>,<sup>...</sup>,a<sub>n</sub>中取r个进行允许重复的组合。假定允许重复的组合数用<u>C</u>(n,r)表示，其结果可能有以下两种情况。 </p> <p> 1）不出现某特定元素设为a<sub>1</sub>，其组合数<u>C</u>(n-1,r)，相当于排除a<sub>1</sub>后从a<sub>2</sub>,<sup>...</sup>,a<sub>n</sub>中取r个做允许重复的组合。 </p> <p> 2）至少出现一个a<sub>1</sub>，取组合数为 相当于从a<sub>1</sub>,a<sub>2</sub>,<sup>...</sup>,a<sub>n</sub>中取r-1个做允许重复的组合，然后再加上一个a<sub>1</sub>得从n个元素中取r个允许重复的组合。 </p> <p> 依据加法原则可得： <u>C</u>(n,r)=<u>C</u>(n,r-1) <u>+ C</u>(n-1,r)</p> <p>因<u>C</u>(n,1)=n,<u>C</u>(n-1,1)=n-1，故令<u>C</u>(n,0)=1递推关系(2-2-3)带有两个参数n和r。 </p> <p> <img border="0" src="2_2.pic/image154.gif" width="313" height="80"></p><p> <img border="0" src="2_2.pic/image155.gif" width="183" height="7"></p><p> <img border="0" src="2_2.pic/image157.gif" width="297" height="24"></p><p></p><p> (2-2-3)式是关于G<sub>n</sub>(x) 的递推关系，但系数(1-x)不是常数。但 </p> <p> <img border="0" src="2_2.pic/image161.gif" width="280" height="163"></p><p></p><p> 由二项式定理 </p> <p> <img border="0" src="2_2.pic/image163.gif" width="325" height="41"></p><p>可得</p><p> <img border="0" src="2_2.pic/image165.gif" width="273" height="69"></p>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -