it技術(shù)《南開大學acm暑期集訓之組合數(shù)學》-文庫吧
2025-04-26 16:19 本頁面
【正文】 ?? ?? A B C ?? 遞推關(guān)系 上述算法是遞歸的運用。 n=2時已給出算法； n=3時，第一步便利用算法把上面兩個盤移到 B上，第二步再把第三個圓盤轉(zhuǎn)移到柱 C上；最后把柱 B上兩個圓盤轉(zhuǎn)移到柱 C上。 N=4， 5， … 以此類推。 遞推關(guān)系 算法分析： 令 h(n)表示 n個圓盤所需要的轉(zhuǎn)移盤次。根據(jù)算法先把前面 n1個盤子轉(zhuǎn)移到 B上；然后把第 n個盤子轉(zhuǎn)到 C上；最后再一次將 B上的 n1個盤子轉(zhuǎn)移到 C上。 n=2時，算法是對的，因此， n=3是算法是對的。以此類推。于是有 遞推關(guān)系 算法復(fù)雜度為： 1)2(2 1)1( ,1)1(2)( ???? hnhnh,)3()2()1()( 32 ????? xhxhxhxH H(x)是序列 的母函數(shù)。給定了序列，對應(yīng)的母函數(shù)也確定了。反過來也一樣，求得了母函數(shù)，對應(yīng)的序列也就可得而知了。當然，利用遞推關(guān)系 (221)式也可以依次求得 ，這樣的連鎖反應(yīng)關(guān)系，叫做遞推關(guān)系。 ?),3(),2(),1( hhh?),3(),2( hh遞推關(guān)系 下面介紹如何從 (221)式求得母函數(shù)H(x)的一種形式算法。所謂形式算法說的是假定這些冪級數(shù)在作四則運算時，一如有限項的代數(shù)式一樣。 ,)3()2()1()( 32 ????? xhxhxhxH,)2(2)1(2 )(2 ) ?????? xhxhxxH_ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _????????32)]2(2)3([ )]1(2)2([)1()()21(xhhxhhxhxHx遞推關(guān)系 根據(jù) (221)， ?? ,1)2(2)3(,1)1(2)2(,1)1( ????? hhhhh)1/()()21( 32 xxxxxxHx ???????? ? 或利用遞推關(guān)系 (221)有 1)1(2)2(:2 ?? hhx1)2(2)3(:3 ?? hhx???? )? _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ __ _ _ _ _ _ _ _ _ _)1/()(2)( 2 xxxxHxxH ?????1)2(2 1)1( ,1)1(2)( ???? hnhnh遞推關(guān)系 上式左端為： xxHxhxHxhxh ?????? )()1()()3()2( 32 ? 右端第一項為： )(2x ])2()1([2)2(2)1(2 232xHxhxhxxhxh?????? ?? 右端第二項為： )1/(232 xxxx ???? ?遞推關(guān)系 整理得 xxxxxxHx??????11)()21(2)21)(1()(xxxxH??? 這兩種做法得到的結(jié)果是一樣的。即： 遞推關(guān)系 令 )21)(1(2 )21(1()1()21(211)(xxB ) xAB ) ((AxxxBxAxBxAxH???????????????xxBABA ????? )2()( 如何從母函數(shù)得到序列 ？下面介紹一種化為部分分數(shù)的算法。 ?),2(),1( hh遞推關(guān)系 由上式可得： .1 ,1 ??? BA 即： 12 ??? BA{0?? BA??????????????????????????123322)12( )12()12()12( )1()2221( 11211)(kkkxxxxxxxxxxxxH???遞推關(guān)系 因為： ????1)()(kkxkhxH12)( ??? kkh遞推關(guān)系 例 2. 求 n位十進制數(shù)中出現(xiàn)偶數(shù)個 5的數(shù)的個數(shù)。 先從分析 n位十進制數(shù)出現(xiàn)偶數(shù)個 5的數(shù)的結(jié)構(gòu)入手 是 n1位十進制數(shù)，若含有偶數(shù)個 5，則 取 5以外的 0， 1， 2， 3， 4，6， 7， 8， 9九個數(shù)中的一個，若 只有奇數(shù)個 5，則取 ，使 成為出現(xiàn)偶數(shù)個 5的十進制數(shù)。 121 ?nppp ?1?np121 ?nppp ?5?np nn pppp 121 ??遞推關(guān)系 解法 1： 令 位十進制數(shù)中出現(xiàn)偶數(shù)個 5的數(shù)的個數(shù)， 位十進制數(shù)中出現(xiàn)奇數(shù)個 5的數(shù) 的個數(shù)。 na n ?nb n ? 故有： 119 ?? ?? nnn baa
教學課件相關(guān)推薦
鄂ICP備17016276號-1