?? 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 + -