從漢諾塔問題看遞推關(guān)系在實際問題中的應(yīng)用

從漢諾塔問題看遞推關(guān)系在實際問題中的應(yīng)用姓名:孫瑞 學(xué)號:200640501218 指導(dǎo)老師:馬玉田摘要：本文主要介紹了遞推關(guān)系在實際中的應(yīng)用，對幾個實際問題的分析，讓我們清楚的看到遞推關(guān)系在解決實際問的強大作用．關(guān)鍵詞：數(shù)列遞推關(guān)系漢諾塔九連環(huán)蛛網(wǎng)模型引言:遞推關(guān)系在實際問題中有著廣泛的應(yīng)用.由連續(xù)變量可以建立微分方程模型,離散變量可以建立遞推關(guān)系模型.經(jīng)過分析可知，常、偏微分方程除非在極其特殊的情況下，否則一般不存在解析解，所以討論起來非常麻煩，比如最基本的平衡點的穩(wěn)定性，往往只能得到局部穩(wěn)定性，全局穩(wěn)定性很難得到，而遞推關(guān)系模型可以達(dá)到全局的效果，另外，由遞推關(guān)系獲得的結(jié)果又可以進(jìn)一步進(jìn)行優(yōu)化分析、滿意度分析、分類分析、相關(guān)分析等等。而在實際中，連續(xù)變量可以用離散變量來近似和逼近，從而微分方程模型就可以近似于某個遞推關(guān)系模型。遞推關(guān)系模型有著非常廣泛的實際應(yīng)用背景,我們的前人建立了許多著名的模型,如生態(tài)模型,傳染病模型,經(jīng)濟(jì)模型（如蛛網(wǎng)模型）,人口控制模型（如著名的馬爾薩斯人口控制模型）等等.定義:設(shè)a,a,a,?-a，…是一個數(shù)列，把該數(shù)列中a與它的前面幾個012nna（0<i<n-1）關(guān)聯(lián)起來構(gòu)成的方程，稱為一個遞推關(guān)系，即a二f（…。,…a,…）i n jk（0<j,k<n-1）.下面讓我們看看遞推關(guān)系在漢諾塔問題中的應(yīng)用.引例:漢諾塔（又稱河內(nèi)塔）問題是印度的一個古老的傳說。開天辟地的神勃拉瑪在一個廟里留下了三根金剛石的棒，第一根上面套著64個圓的金片，最大的一個在底下，其余一個比一個小，依次疊上去，廟里的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個，而且大的不能放在小的上面。面對龐大的數(shù)字（移動圓片的次數(shù)）18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動漢諾塔問題:它是由三根固定的柱子ABC和不同尺寸的n個圓盤組成.開始時,這些個大小不同的圓盤依其半徑大小依次套在A柱上，使大圓盤在底下?游戲的規(guī)則是:每次的圓盤從一根柱子移到另一根柱子上，但是不允許這個圓盤放在比它小的圓盤上面.游戲的目標(biāo)是把所有的圓盤從按照大小的次序從A柱都移到C根柱子上，可以利用中間的B柱子，在移動過程中藥始終將最大的圓盤放在最下面.令H表示解n個圓盤的漢諾塔游戲所需要的移動次數(shù)，建立關(guān)于序列｛H｝遞推關(guān)系nn解開始時n個圓盤在A柱上，按照游戲規(guī)則用H次移動將上面的n-1個圓盤移到Cn-1柱子上，在這些移動中最大圓盤不動?然后，用1次移動將最大圓盤移到B柱子上?再用Hn-1次移動將C柱子上的n-1個圓盤移到B柱子上并且放到最大圓盤上面，于是，得到所求遞推關(guān)系.H=2H+1TOC\o"1-5"\h\zn n-1和初始條件是H二1.因為根據(jù)游戲規(guī)則,一個圓盤可用1次移動從A柱子放到B柱子上.1為求解上述遞推關(guān)系，對該問題首先用構(gòu)造方法導(dǎo)出其解公式如下:\o"CurrentDocument"H=2H +1n n-1=2(2H +1)+1=22(2H +1)2+1=23H+2+2+1\o"CurrentDocument"n-2 n-3 n-3=2n-1H+2n一2+2n—3+…?+2+11=2n-1+2n-2+■??+2+1=2n—1其中H=1，H=2n-1確是遞推關(guān)系H=2H +1的解.1 n n n-1現(xiàn)在我們再回頭看看古印度的那個問題，勃拉瑪要求移動64個圓盤，帶入我們所求的關(guān)系式即是H=264一1=18446744073709551615，面對這個天文數(shù)字，廟中僧侶要想移動64這64個圓盤幾乎是不可能的.從漢諾塔問題我們看到遞推關(guān)系在解決實際問題中的巨大作用，，它在眾多領(lǐng)域里有著廣泛的應(yīng)用,由此我們看看由漢諾塔問題所引出的一些實際問題.九連環(huán)方程問題九連環(huán)是中國古代在民間流傳的一種玩具,它是由9個環(huán),9個直桿,一個條形框柄和一個平板組成,.每一個環(huán)都有一根桿相連,又順序穿入后一個環(huán),再連在條形橫板上,從而構(gòu)成一個整體,與其相適應(yīng),大小相當(dāng)?shù)囊粋€條形框柄,可以將9個環(huán)穿套在上下框柄.只有它前面的換單獨在框柄上面.只是穿套不可能一次性完成,有著嚴(yán)格的規(guī)律性和特別的要求.第一個環(huán)可以獨立,自由地上或下條形框柄,而其后的各環(huán)要上或下框柄都受其前面的連桿和環(huán)的限制,任何一個環(huán)要獨立,自由地上下框柄只要它前面的換單獨在框柄上就能做到.現(xiàn)在可以假設(shè)前n個環(huán)已經(jīng)全部上到框柄上,需要移動環(huán)的次數(shù)為S(n=1,2,???9).這樣，將前nn-1個環(huán)都上到框柄上時，需要移動S次，反之將前n-2個環(huán)下到框柄下.移動次數(shù)和之n-1前的情形一樣為s ，此時只有第n-1個環(huán)單獨在框柄上,可將第n個環(huán)上到框柄上，移動n-2一次,再將前n-2環(huán)上到框柄上，移動次數(shù)為S ，至此，前面n個環(huán)都上到框柄上,總的移n-2動次數(shù)為s+s+1+s=s+2S+1，按假設(shè),它等于s，所以有TOC\o"1-5"\h\zn-1 n-2 n-2 n-1 n-2 ns=s+2s +1，補充定義s=0顯然s=1(n=1,2,…①)這就是九連環(huán)的基本方程.\o"CurrentDocument"n n-1 n-2 0 1利用它可以計算出s=2，并遞推地求出s?直接求解可將兩邊都加上和減去S+1，得:2 n n-1S+S+1=2(S +S+1)=2n和S-S—1=2S\o"CurrentDocument"n n-1 n-1 nn-1 n-2n-2求平均得：S=S+2n-1,n n-2遞推下去，有\(zhòng)o"CurrentDocument"S=S+2n-3+…+s=S+2i+1n-2 n-4 i+2 i遞推下去，有累加得s=s+三(2n+1ni3-2累加得s=s+三(2n+1ni3為求S和2i+i,可設(shè)uS+v=cos加,則有iiu+v=-12u+v=1，解方程組，得u=2,v=3，所以S=1(3+cosn兀)TOC\o"1-5"\h\z14p+q二—1 1設(shè)p-2;+i+q二cosn兀，則有｛ [，解方程組得p= ,q=—3?所以有[8p+q二1 22；+1-2(3+cos“兀)帶入解表達(dá)式S=S+-(2n+1—2：+i),有ni3S=丄(3+cosn兀)+】[2n+1—2(3+cosn兀)],n2 3整理，得S=1x2n+1—1—[cos加，這即是九連環(huán)方程的解.n3 26如果令S+S二H表示第n個環(huán)單獨在框柄上要移動環(huán)的次數(shù)，代人基本方程，消去nn—1 nS有H二2H +1，這可以視為九連環(huán)第二方程，也就是我們前面所提及的漢諾塔方程n n—1遞推關(guān)系在幾何上的應(yīng)用例1一個人從坐標(biāo)原點A(0,0)出發(fā),通過點(1,0)，A(1,1)然后再以折線通過整數(shù)坐標(biāo)01的點B(—1,1),C(2,—1),D(2,—1),A(2,2),B(—2,2),C(—2,—2),D(2,—3),A(3,3)試TOC\o"1-5"\h\z1 1 1 2 2 2 2 3求此人沿著折線到點(m,n)時所走的路程(m>n>0).解:用a表示這個人由原點A(0,0)走到A(1,1)的路程，a表示此人由點A(k,k)走到點0 0 1 k kA(k+1,k+1)的路程，則當(dāng)k>2時，由A(k—1,k—1)走到A(k,k)時經(jīng)過的路程是k+1 k—1 kA(k—1,k—1)TB(—k+1,k—1)TC(—k+1,—k+1)k—1 k—1 k—1TD(k,—k+1)TA(k,k).k—1 k所以，得

a=|ABI+|B CI+|CDI+IdAIk-1 k-1k-1 k-1k-1 k-1k-1 k-1k=(2k—2)+(2k—2)+(2k—1)+(2k—1)=8k一6因為此公式當(dāng)k因為此公式當(dāng)k=1時得a0｛爲(wèi)｝的通項公式ak-1(k二1,2,3,…).當(dāng)此人從A(0,0)到A(m,m)時，走的路程是曠a，即0 m kk=0P藝a0 kP藝a0 k-1=込(8k-6)=8込k-6mm(m+1)2k=1-6m=4m2-2m由點(m,n)到點A(m,n)的路程為(m—n)，故此人由原點A(0,0)走到點(m,n)的m0路程是4m2一2m一(m一n)=4m2一3m+n.在求圖形中的無限個圖形的面積或無限條線段長的和時，首先要確定這些面積或線段長所組成的數(shù)列.為此，要求出第一個圖形的面積或第一條線段的長度，以及前后兩個圖形面積或線段之間的遞推關(guān)系，然后再用有關(guān)的公式求和.例2如圖所示,在直角AABC中，ZABC=90。,ZA=9.自B點出發(fā)，作BD丄AC1于D，作DD丄AB于D，作DD丄AC于D，…依此做下去，得到無窮數(shù)列1 12 2 23 3CB,BD,DD,DD,…

(1)求證：CB+BD+DD+DD+—>AB+AC.11223(2)求證：CB2+BD2+DD2+DD2+???=AC2.11223⑶為使AABD,AADD,AADD，…的面積之和不大于AABC的面積，求9的取值范11223圍.解(1)由已知條件可得BD=BC-cos9,1DD=BD-cos9=BC-cos29,12在RtADDD中可知：DD=DDcos9(n=l,2,3,…).nn+1n+2 n+1n+2nn+1由上式聯(lián)立可知，數(shù)列CB,BD,DD,DD,…是首項為CB，公比為cos9的等比數(shù)列，又ll2 23因而它又是無窮遞縮等比數(shù)列，故CB,BD,DD,DD,???=—ll2 23l-cos9CB (1+cos9)-CBTOC\o"1-5"\h\zAB+AC=CBctg9+ -= 9\o"CurrentDocument"sin9 sin9從而CB (1+cos9)-CBsin9(1-sin9)— = ?CB1-cos9 sin9 (1-cos9)sin99是銳角,故上式的值為正值,因此CB+BD+DD+DD+…>AB+AC1 12 23⑵顯然，數(shù)列CB2,BD2,DD2,DD2…是首項為CB2，公比為cos29的無窮遞縮等比1 12 23數(shù)列,因此,CB2+BD2CB2+BD2+DD2+DD2+…1 1 2 2 3CB21-cos92CB2sin92\2=AC2丿

S=1BD-AD=1BD-(BD-ctgO)△ABD] 2 1 1 2 1 1=—BD2-ctg0=—(BC-cos0)2ctg0212BC2COS302sin9 '乂AABDsAADD，于是112SAABDSAABDs1AAD1D2—1__=cos29BD2 'S△ABDS△ABD1(CoS29)AABD2因為AADD與AADD相似，于是nn+1 n+1n+2SAADn+1Dn+2SAADDn+1DDn+1 n+2~SAADn+1Dn+2SAADDn+1DDn+1 n+2~DD2

nn+1=(DD—n+1 n+^)2=cos29,DDnn+1S△ADD

n+1n+2(cos29)2SAADnDn+1由上式可知,數(shù)列S,S△ABD1,SAAD1D2AAD2D3…是首項為BCC0嚴(yán)，公比為cos29的無窮遞2Sin9縮等比數(shù)列,故BC2CoS39△ABD1+S+SAAD1△ABD1+S+SAAD1D2AAD2D3+?…2sin91-cos29BC2cos39BC2=^s^=〒(ctg9)3,又S =]AB-BC=AABC2]BC2ctg92，TOC\o"1-5"\h\zBC2 BC2依題意令一亍(ctg9)3< 2ctg9，得tg2921.\o"CurrentDocument"兀 兀 兀于是在0<9<-的條件下，得-<9<-,兀c兀因此，當(dāng)丁<9<時，AABD,AADD,AADD,…的面積之和不大于AABC的面積.4 2 1 12 23遞推關(guān)系在概率論中的應(yīng)用隨著科學(xué)技術(shù)的發(fā)展，遞推關(guān)系在各個領(lǐng)域得到越來越多的應(yīng)用，本文將介紹遞推關(guān)系

的一個簡單的應(yīng)用，即利用遞推關(guān)系求概率問題.全概率公式是概率中一個最基本、最常用、最重要的公式.利用全概率公式列出遞推關(guān)系，然后通過解遞推關(guān)系求得概率，從而簡化了應(yīng)用全概率公式求解某些問題的復(fù)雜繁瑣性.下面讓我們看兩個具體實例:例1投擲硬幣n次，第一次出現(xiàn)正面的概率為c,第二次后每次出現(xiàn)與前一次相同的表面的概率為P，求第n次出現(xiàn)正面的概率.解設(shè)A=｛第n次出現(xiàn)正面｝,則由全概率公式可得：nP(A)=P(A)P(An)+P(n)P(An+J)

n+1 n /A ■/nn=P.p+(1-P)pnn即P=(2p-1)P+(1-p)n+1 n由上述遞推關(guān)系及初始條件p二.+c(2p-1)n-1當(dāng)p豐1時，有p=[1-(2p+c(2p-1)n-1n=1-(2p-1"1+c(2p-1)n-1=(c-2)(2p-i)n-1+2,當(dāng)p=1時，有P三cn例2在每一次試驗中，事件A出現(xiàn)的概率p，試問n次獨立試驗中A出現(xiàn)偶次的概率多少?解設(shè)P表示n次獨立實驗中A出現(xiàn)偶次的概率，則根據(jù)題意可列出關(guān)系式nP=p+(1-2p)P,TOC\o"1-5"\h\zn n-1用迭代法將其展開可得(1-2p)P=p(1-2p)+(1-2p)2P,n-1 n-2(1-2p)2P =p(1-2p)2+(1-2p)3P,\o"CurrentDocument"n-2 n-3(1-2p)n-2P=p(1-2p)n-2+(1-2p)n-1P,21(1-2p)n-1P=p(1-2p)n-1+(1-2p)nP.10其中，P=1，且上述表示對原方程組進(jìn)行遞推連鎖變換，同乘以1-2p，然后將上述n個方0程兩邊相加，約去含P至P的各項，則1 n-1P=p+(1—2p)+p(1—2p)2+?…+p(1—2p)n—i+p(l—2p)nn=p[1-(1-2p)：]2p+(1-2p)n_1+(1—2p)n=2'遞推關(guān)系在物理學(xué)中的應(yīng)用遞推關(guān)系在工程技術(shù)領(lǐng)域的某些方面有重要應(yīng)用.原因在于遞推關(guān)系方程滿足許多領(lǐng)域的方程形式，而解法又滿足n階常系數(shù)方程的形式.所以物理領(lǐng)域中的問題只要條件滿足遞推關(guān)系方程，一般都可以方便解之.下面以二階齊次遞推關(guān)系方程為例，略述其在物理方面的一些應(yīng)用.例如圖1所示系統(tǒng)，點P0保持對地面的恒定電位^，試求§P2,仆…「1各點的電位.分析：根據(jù)Kirchhoff定律:流入電路中任何節(jié)點的電流之和等于流出該節(jié)點的電流之和TOC\o"1-5"\h\z因此在一般點P(圖2),可得i_i+1 ,x+1 x x+1 x+1打+1由i_VR，可得：V—V V—V Vx x+1— x+1 x+2 x+1,rr 2rTOC\o"1-5"\h\z整理得V—V+V_0 (1)x+2 2x+1 x式⑴在x_2'3‘…,(n-2)時成立，就是說在點P與Pn—1之外的所有點上成立，在點P與

P,式(1)化為相應(yīng)條件n-1TOC\o"1-5"\h\z—V+5V=V(V為已知) (2)22100-5V+V=0(V二0) (3)2n-2 n-2 n方程(1)滿足遞推關(guān)系(E2-5Ei+Eo)V=02x的形式,故可采用遞推關(guān)系方程求解,式(1)特征方程為M2-5M+1=02解得M=三,M=2122其全解為xx其全解為xx將其帶入式(2)和(3)得A 5A-+4B)+-(-^+2B)=V-5(△+B2n-1)+(—22n-1 2n-2求方程得A=求方程得A=22nkV0，122n—122兀 1所以電壓的通解V=(-2x) V.x2x 22n-10可以驗之,在x=0和x=n點均滿足上式.市場經(jīng)濟(jì)中的蛛網(wǎng)模型經(jīng)濟(jì)背景與問題：在自由競爭的市場經(jīng)濟(jì)中，商品的價格是由市場上該商品的供應(yīng)量決定的，供應(yīng)量越大，價格就越低。另一方面，生產(chǎn)者提供的商品數(shù)量又是由該商品的價格決定的價格上升將刺激生產(chǎn)者的生產(chǎn)積極性，導(dǎo)致商品生產(chǎn)量增加；反之，價格降低會影響生產(chǎn)者的積極性，導(dǎo)致商品生產(chǎn)量下降。經(jīng)營者要取得良好的經(jīng)濟(jì)效益，就必須把握好這兩個因素規(guī)律，避免市場供求出現(xiàn)混亂。模型假設(shè)與模型建立：將市場演變模式劃分為若干銷售時段，用自然數(shù)n來表示；設(shè)第n個時段商品的數(shù)量為x,價格為y，n=1,2,；nn價格與產(chǎn)量的關(guān)系為：y二f(x)；nn假設(shè)下一時段的產(chǎn)量x是決策者根據(jù)這期的價格決定的，設(shè)x二h(y)，從而TOC\o"1-5"\h\zn+1 n+1 ny—g(x)，由此建立遞推關(guān)系：n n+1X二h[f(x)],y二f[h(y)].n+1 n n+1 n模型的幾何分析：兩個變量x和x的變化過程，可以借助已有的函數(shù)f和g用幾何方nn式表現(xiàn)出來。把點列(x,y)和(x,y)在坐標(biāo)系中描繪出來，nn n+1n(x,y)二(x,f(x)),(x,y)二(x,g(x))將點列TOC\o"1-5"\h\znn n n n+1n n+1 n+1P(x,y),p(x,y),p(x,y),p(x,y)，…連接起來，就會形成象蛛網(wǎng)一樣的折線。這11 12 21 333 44 3易見：如果點列P(x,y),p(x,y),p(x,y),p(x,y),…最后收斂于點p(x,y)，則111221333443000xTx,yTy，且p就是兩條曲線的交點，從而達(dá)到穩(wěn)定狀態(tài)，反之是不穩(wěn)定的。n 0n 0 0幾何上的進(jìn)一步分析表明，如果曲線y=f(x)和y=g(x)在交點p處切線的斜率記為k，0fk，則可知g當(dāng)匕<叮時，p0是穩(wěn)定的；當(dāng)I?>lkI時，p0是不穩(wěn)定的。

模型的遞推關(guān)系方程分析：設(shè)點p(X,y)滿足：y二f(y),x二h(y)，在p點附近取函數(shù)f(x),h(x)的近似:00000000y二y_a(x-x),a>0,n0n0x二x+卩(y—y),卩>0.TOC\o"1-5"\h\zn+1 0 n0合并兩式可得：x=_aBx+(1+aR)x,n—1,2,?…n+1 n 0其中―為f在p點處的切線斜率；|為g(x)在點po處切線的斜率。由方程x 卜(1+aR)x,n—1,2,…，遞推可得x—(—aB)nx+[l_(_aB)n]x.n+1 n 0 n+1 1 0所以，P所以，Po點穩(wěn)定的充要條件是：|a0|<1，即a<—卩.蛛網(wǎng)模型的推廣:如果決策時考慮到x與y，y都有關(guān)系，則可假設(shè)TOC\o"1-5"\h\zn+1 n n+