歸納法遞推法

歸納法

歸納法是由一系列有限的特殊事例得出一般規(guī)律的推理方法。

例、求前n個奇數(shù)的和。分析：用S(n)表示前n個數(shù)的和，則S(1)=1,S(2)=1+3=4,S(3)=1+3+5=9,S(4)=1+3+5+7=16,S(5)=1+3+5+7+9=25。可以看出，當1，2，3，4，5時，S(n)=n2。現(xiàn)在可以歸納出求前n個奇數(shù)的和的一般規(guī)律，即S(n)=n2。上面的歸納法是不完全歸納法，因為由它得到的結論不一定對任意的n都成立．要證明對所有的n都成立，就必須使用下面介紹的數(shù)學歸納法．1、證明當n取第一個值n0時結論正確。2、假設當n=k時結論成立，證明當n=k+1時結論也成立。證明：１、當n=１時，左邊＝１，右邊＝１，等式成立。２、假設當n=k時等式成立，即１＋３＋５＋…＋（２k-1)=k2，那么１＋３＋５＋…＋（２k-1）+[2(k+1)-1]=k2+2(k+1)-1=k2+2k+1=(k+1)2例1、Hanoi雙塔問題

07年復賽試題

給定A、B、C三根足夠長的細柱，在A柱上放有2n個中間有孔的圓盤，共有n個不同的尺寸，每個尺寸都有兩個相同的圓盤，注意這兩個圓盤是不加區(qū)分的（下圖為n=3的情形）?，F(xiàn)要將這些圓盤移到C柱上，在移動過程中可放在B柱上暫存。要求：（1）每次只能移動一個圓盤；（2）A、B、C三根細柱上的圓盤都要保持上小下大的順序；任務：設An為2n個圓盤完成上述任務所需的最少移動次數(shù)，對于輸入的n，輸出An。輸入文件hanoi.in為一個正整數(shù)n，表示在A柱上放有2n個圓盤。輸出文件hanoi.out僅一行，包含一個正整數(shù)，為完成上述任務所需的最少移動次數(shù)An?！緲永?】hanoi.inhanoi.out12【樣例2】hanoi.inhanoi.out26【限制】

對于50%的數(shù)據(jù)，1<=n<=25

對于100%的數(shù)據(jù)，1<=n<=200【提示】

設法建立An與An-1的遞推關系式。

解題思路:數(shù)學歸納+高精度

Hanoi單塔的最少移動步數(shù)是2n-1，現(xiàn)在有2層，可以將2層看作1層，便回到了單塔的問題上，每移動想象中的“單個”盤子需要兩步，故Hanoi雙塔=Hanoi單塔*2可得公式：f(n)=2n+1-2高精度只要編個乘法就可以了，不要忘記最后-2beginassign(input,'hanoi.in');assign(output,'hanoi.out');reset(input);rewrite(output);readln(n);ppp(n+1);

ifa[1]>=2thena[1]:=a[1]-2elsebegina[1]:=a[1]+8;a[2]:=a[2]-1;end;i:=100;whilea[i]=0doi:=i-1;forj:=idownto1dowrite(a[j]);close(input);close(output);end.varn,i,j:integer;a:array[1..100]of0..9;procedureppp(k:integer);vari,j,w,s:integer;begina[1]:=1;w:=0;fori:=1tokdo{循環(huán)K次}

forj:=1to100dobegins:=a[j]*2+w;a[j]:=smod10;w:=sdiv10;end;end;例2、乘火車(98年復賽試題)火車從始發(fā)站（稱為第1站）開出，在始發(fā)站上車的人數(shù)為a，然后到達第2站，在第2站有人上、下車，但上、下車的人數(shù)相同，因此在第2站開出時（即在到達第3站之前）車上的人數(shù)保持為a人。從第3站起（包括第3站）上、下車的人數(shù)有一定規(guī)律：上車的人數(shù)都是前兩站上車人數(shù)之和，而下車人數(shù)等于上一站上車人數(shù)，一直到終點站的前一站（第n-1站），都滿足此規(guī)律?，F(xiàn)給出的條件是：共有n個車站，始發(fā)站上車的人數(shù)為a，最后一站下車的人數(shù)是m（全部下車）。試問第x站開出時車上的人數(shù)是多少？輸入文件chc.in：一行四個整數(shù)a，n，m和x（中間用空格隔開）輸出文件chc.out：一行一個整數(shù)（從x站開出時車上的人數(shù)）樣例:chc.in46324chc.out18分析:典型的數(shù)學題為了找規(guī)律，我們建立一個表:站號123456開車時人數(shù)num[]aa2a2a+b3a+2b4a+4b上車人數(shù)in[]aba+ba+2b2a+3b3a+5b下車人數(shù)out[]0bba+ba+2b2a+3b規(guī)律出來了，設第k(k>=3)站時上車人數(shù)為f[k-2]*a+f[k-1]*b(f[k]={1,1,2,3,5,8,13,21..}為fibonacci數(shù)列)num[k]=a+in[2]-out[2]+in[3]-out[3]...+in[k]-out[k]而in[2]=out[3],in[3]=out[4]...故num[k]=a-out[2]+in[k]=a-b+f[k-2]a+f[k-1]b=(f[k-2]+1)a+(f[k-1]-1)b(1)因為知道第n-1站開車時人數(shù)為m,容易求出b,再代入(1)求第x站開車時的人數(shù)p。即：m=(f[n-3]+1)a+(f[n-2]-1)b(2)p=(f[x-2]+1)a+(f[x-1]-1)b(3)從(2)解得b,代入(3)計算知p=(f[x-2]+1)*a+(f[x-1]-1)*(m-(f[n-3]+1)*a)div(f[n-2]-1);}varf:array[1..23]ofinteger;i,a,n,m,x:integer;beginf[1]:=1;f[2]:=1;fori:=3to23dof[i]:=f[i-1]+f[i-2];readln(a,n,m,x);writeln((f[x-2]+1)*a+(f[x-1]-1)*(m-(f[n-3]+1)*a)div(f[n-2]-1));end.練習1、將一張長方形的紙對折，可得到一條折痕，繼續(xù)對折，對折時每次折痕與上次的折痕保持平行，連續(xù)對折三次后，可得到７條折痕，那么對折n次，可得到幾條折痕？

第一次對折一條折痕，第二次對折（1+2=3）條折痕，第三次對折（1+2+4=7）條折痕，第四次對折（1+2+4+8=15）條折痕，換種寫法是20+21+22+23，所以我們猜想第n次對折后的折痕條數(shù)是20+21+22+23+…+2n-1或2n-1．練習2數(shù)一數(shù)下圖中有多少個正方形？如果把正方形各邊平均分成n份，那么得到的正方形總數(shù)為多少？

52+42+32+22+12=55n2+(n-1)2+(n-2)2+…+22+12=1/6n(n+1)(2n+1)練習3按下圖擺放桌子和椅子：一張桌子可坐6人，二張桌子可坐10人，三張桌子可坐14人，…試對任意給出的桌子數(shù)n（n>0）,寫出可坐人數(shù)。4n+2練習4如圖,第一次把三角形剪去一個角后,圖中最多有四個角,第二次再把新產(chǎn)生的角各剪一刀,…,如此下去,每一次都是把新產(chǎn)生的角各剪一刀,則第n次剪好后,圖中最多有多少個角?可知后一次新產(chǎn)生的角的個數(shù)是前一次新產(chǎn)生角個數(shù)的２倍，再加上２就是后一次產(chǎn)生角的總數(shù)．因此，剪n次后，圖中最多有角：2+2n遞推法常常遇到這樣的問題：在一個序列中，下一項的值對其前一項有著某種依賴關系，求某項的值要從第一項起經(jīng)過逐次推算而得到。例如：數(shù)列0，3，6，9，12，15，…該數(shù)列的后一項的值是前一項的值加3，欲求第十項，必須先用第一項的值加3，求出第二項，然后求出第三項，第四項，第五項，…，直到第十項，當然必須事先給定第一項的值（稱為初始條件）。可以看出，該數(shù)列中第n項的值等于第n-1項的值加3。即：an=an-1+3,(n>1)(遞推公式)a1=0,(n=1)(初始條件)這種在規(guī)定的初始條件下，找出后項對前項的依賴關系的操作，稱為遞推。表示某項和它前面的若干項的關系式就叫作遞推公式。在實際問題中類似的很多，處理這類問題的理想方法是用歸納法求出通項公式。如上例中的通項公式為an=(n-1)*3(n>=1)。但是在許多情況下，要得到數(shù)列的通項公式是比較困難的，而通過已知條件歸納出一個遞推關系則相對容易。這時就可以采用遞推技術，避開求通項公式的麻煩，把一個復雜問題的求解，分解成為若干步重復的簡單運算，由邊界條件出發(fā)進行遞推，最后得到最終結果。我們把由已知初始值為Ｆ1，通過遞推關系式Ｆn=g(Fn-1)求出其最終結果Fn的遞推方式稱為順推法．同理，把已知最終結果為Fn，通過遞推關系式Ｆn-1=g(Fn)，求出其初始值Ｆ1的遞推方式稱之為倒推法．有一對雌雄小兔子，過一個月之后長成為大兔，并且以后每個月都生下一對小兔。而所生的一對小兔也同樣到一個月之后長成大兔，到第三個月就可以生下一對小兔，并且以后也每個月都生下一對小兔。假定所有的兔子n個月內(nèi)均不死亡，問n個月后共有多少對兔子？

123456789101112小111235813213455中1112358132134大11235813213455總1123581321345589144f(1)=1(n=1)f(2)=1(n=2)f(n)=f(n-1)+f(n-2)(n>2)如何通過已知條件歸納出一個遞推公式?參考程序１參考程序２練習1（20浴00年初尖賽試退題）有2×n的一浩個長魔方形涂方格反，用劇一種1×2的骨法牌鋪況滿方閉格。例如n=候3時，抓為2×3的方格抗，有如下輪３種異鋪法：此時粥用一上個1×2的骨會牌鋪寫滿方從格，旁共有3種鋪伴法：試對近給出竿的任別意一宿個n（n>茅0），求出疲鋪法犯總數(shù)簽的遞總推公面式。用F（n）表鎮(zhèn)示其遮鋪法屈總數(shù)肢的遞蒼推公絲式式為:F（1）=1，F(xiàn)（2）=2，F(xiàn)（n）=F（n-第2）+F（n-陳1）（n≥3）練習2（20子00年初艇賽試證題）設有濕一個勁共有n級的崇樓梯霸，某牌人每疊步可乘走1級，賓也可滾走2級，循也可千走3級，暫用遞離推公綠式給尸出某治人從翅底層籌開始銳走完懲全部斧樓梯僚的走沃法。你例如糕：當n=窗3時，六共有4種走沸法，辜即1+稼1+與1,堆1+壘2,更2+乎1,誕3。用遞炭推公吊式給繁出的廁某人核從底寒層開儀始走乞完全俊部樓保梯的圓走法粒為（用F（n）記鼻錄不然同方蔥案數(shù)帖）：F（1）＝1F（2）＝2F（3）＝4F(缸n)＝F（n－3）＋F（n－2）＋F（n－1）（n>音=4）練習3一張陡圓薄敏餅，敞切10錫0刀，炎最多考能切偷成多孟少塊可？a10念0=a99+1濱00=a98+9汪9+1稅00=a97+9塑8+9侵9+墨10泛0=…=a1+2+3客+…娛+9這8+催99陸+1行00=2征+辮2+揮3+筋…+羅98壟+9何9+蹤蝶10俘0=5界05章1切一質(zhì)刀，倚得２高塊，爆增加重了一攪塊；彩切二嚷刀，舉得４促塊，貨增加黃了２票塊；霉切三防刀，密得七耐塊，愉增加開了３廁塊；躲切四辜刀，護得1點1塊甜，增宵加了賓4塊撓;…晚;切n刀，盆增加n塊.可得魂：F(畜1)汽=2F(蹲n)偏=揪F(才n-主1)汽+n浮(n遇>=趟2)這里市使用栗的是面迭代這法．躍遞推紀與迭玩代是各兩個孫既有其聯(lián)系怎又有買區(qū)別失的概他念，吧遞推桶是指桌從前御面一蝴些量很可以束依次脾推出潔后面牛的量震的算掀法．遞推不一羨定采鈔用迭代．練習4下圖材是居但民小逮區(qū)道止路圖針，小蓋明每蒼天由迅家（申Ａ點雜）到樓學校闖（Ｂ史點）均，他閉只沿師道路菜向上驅(qū)或向擋右行諷走，徹那么攜他最謠多有久（伸）愈天走伏不同穴線路例？ＡＢ４９撒５１１１１１蓋１涉１閘１彈１得１桌１縣１２花３膽４蝴５棋６蜻７宅８仔９３搶６10152128364541020賭35568412無016懇551535夫7012殺621貫033剝0省4讓95練習制5如果攻有n元錢,每天引去購錫買下飲列三催種商梨品之擱一:蔬菜尚要用1元錢,豬肉泡要用2元錢,雞蛋陡要用跡２元百錢．狗用An表示展把這n元錢尼用完顫的所丸有可丑能的租用法去的總谷數(shù)，概請找胖出求An的遞森推公吃式．如果芝第一縱天買駁蔬菜感，則挺用去雹１元嘆錢，雪還剩n-阿1元錢嫌，等這n-休1元錢塞的用謊法有頓Ａn-釋1種；如果教第一魯天買虛豬肉蝴，則曬用去道２元既錢，駝還剩n-陶２元錢女，里這n-鍋２元錢貫的用窩法有柄Ａn-丸2種；如果廳第一嘗天買樂雞蛋妹，則畏用去堡２元族錢，起還剩n-圍２元錢印，峰這n-判２元錢似的用達法有犧Ａn-辜2種；所以禮，Ａn=Ａn-當1+2Ａn-說2練習舍６求數(shù)留列：a1=12,a2=22,a3=32,…趣,an=n2的遞仗推公好式．f(盾n)歡=f蛙(n妨-1待)+地2n霸-1練習河7遞推懷的一工種重示要形允式是粉“倒療推”總。如嘩果一隊個問賴題有俊唯一備解，畫并且綁它們宇的運對算是來可逆胞的，燥就有勾可能滾用倒捕推法奔來解夜，它扁可看侄成遞羽推法鹿的特犧例。本題擦可從統(tǒng)最后泰一天惡起逐先次推揀出前雜一天軌的桃獎子數(shù)菠，直些到推適出第沖一天真吃桃滋子前家的全族部桃茂子數(shù)談為止像。根據(jù)在題意有可得ta笨o(桂i-閘1)艱=2子*(蠢ta傅o(畏i)豈+1晃)這樣墻由第撿十天顫的桃?guī)r子數(shù)荒是１怕，可鎮(zhèn)推出運第一道天的太桃子望數(shù)是暮15買34澡.有一說天，勇小猴宇子摘箱下了仆若干魯桃子窄，當秒即吃縱了一尿半，乞覺得聾不過窮癮，像又吃上了一烘?zhèn)€，姿第二昨天猴懂子接誦著吃競了一興半，姜覺得股不過壟癮，曉又吃棍了一神個，增以后遍每天驗都是添吃了稅一半優(yōu)，覺翼得不訓癮，器又吃抗了一嚷個，矛到了圖第十幕天，槐只剩愛下一刃個桃摔子了拔，問優(yōu)小猴畏子第塵一天院摘下欠了多岔少個垃桃子圣？（參考怪程序）練習舞8四個輪人做唯火柴轎游戲演,每斷一局衫三個刻人贏宴,一纖個人框輸,抗輸者己要按躺贏者脂手中瓜贏得攀火柴宿根數(shù)遵賠償怒,即酒贏者癥手中麥有多碑少根尼火柴園,輸傲者就棒賠他丑多少倉?4除次之廟后,至每人遮恰好獵輸過丹一次徑而且展手中錦都恰彈好有序16帝根?矛求四貓人原錘有火野柴數(shù)歇?把第視一局導輸?shù)难a人記勻為Ａ碌，把份第二麥局輸飲的人漠記為袖Ｂ，鵲把第叮三局擇輸?shù)碾[人記拿為Ｃ宏，把漂第四惰局輸伙的人居記為院Ｄ，蠅用倒誼退法慶可知奪：ＡＢＣＤ４１６１６１６１６３８８８４０２４４３６２０１２３４１８１０開始３３１７９５例1、國等王與染麥子問題乘描述予：傳說歇古代鼻印度炮有個薄喜歡禮下棋喉的國讓王叫書舍罕紀，而昆宰相吩達依態(tài)爾是楊個聰更明的寨大臣磨，他冊發(fā)明倚了國毀際象忠棋。品國王艘玩得佛愛不孟惜手圣，決策定獎獵賞宰誕相。彈達依送爾說糧：陛唉下，死我別坑無他樂求，佳請你霜在這棟張棋京盤的劫第一償個格時子里淚賞我懸一粒形麥子鵝；在閥第２喪個格飼子里飲賞我2粒麥虜子；禮在第毀３個院格子于里賞描我４容粒麥懲子；妻在第真４個楚格子哄里賞飼我８震粒麥概子……依此和類推糾直到64個格予子，親按這量張棋村盤上編各格均應賞缸的麥樹子全俱賞給耕我吧追。國王泄聽了劈燕，覺奧得達奸依爾環(huán)的要喘求并騎不高孫，說錦道：激你能纏如愿修以償堡的。你能免幫助繡國王辣算算鎖第n個格澡子的彈麥子寇數(shù)量呼嗎？輸入醉文件ma嬌iz哥i.講in只有洗一行奇，一撇個正擱整數(shù)n（n<賭=1拔00）。輸出瞞文件ma投iz林i.擔ou怎t只有滿一行柴，一削個正奶整數(shù)菊，表長示第n個格虛子的螺麥子盾數(shù)量值。輸入隸樣例竊：5輸出雅樣例掩：16va威ra:憐ar儀ra辮y[勻1.滴.1石00周,1愿..侍10筍0]虜o肺f比in縮慧te棟ge以r;n,蘇i,枯j,罷t:才lo銜ng粉in體t;be苗gi傷nas螺si類gn把(i應np溜ut譽,'篩ma抓iz泥i.禽in')對;re志se蟲t(膊in茅pu盡t);as顏si嚼gn憤(o腹ut珠pu艘t,褲'm犬a(chǎn)i竹zi洪.o少ut')賺;re懷wr輩it礙e(狐ou箏tp德ut);re亂ad仇(n);朽{讀入粱格子侄數(shù)}a[屆1,管1]涂:=稈1;票{第一乎格的寫麥子撐數(shù)為1}fo糧r拳i:承=2維t昨o壺n里do盼{遞推押求每喚個格疫子中莊的麥浸子數(shù)}be況gi卡nt:禿=0網(wǎng);{進位他初始凈化}fo扶r緞j:賠=1腎t羊o旱10威0昆dobe倉gi排na[憂i,尾j]:斥=a晌[i胡-1而,j鐘]*遺2+徑t;t:槍=a[栽i,債j]仆di向v艙10襪;a[丹i,江j]:槽=a[芝i,禿j]報mo西d暖10摩;en干d;en酬d;i:丹=1酸00黑;wh陽il播ea[吐n,地i]=附0竄do厲i意:=搖i-嶼1;腎{去掉貫高位策多余干的0}fo斯r岔j:蒙=ido汪wn阻to1鞠dowr現(xiàn)it等e(悉a[封n,雹j])畢;cl關os則e(座in士pu臥t);cl跨os盡e(吸ou喚tp態(tài)ut);en懸d.co榮ns是tle離n=3刑0;va爺rn,格m,領i,覆j,為L,土k,怪x1覽,x況2,滅y1糕,y政2,伯x:抱lo嬸ng棵in敵t;a:丘ar屆ra己y[象1.賠.5遮0,辣1.疤.5笨0,剃1.慘.l池en陽]器oflo珠ng篇in枕t;b:撫ar腰ra汗y[獅1.悟.5絡0,待1.常.5囑0]闖o景fbo恨ol召ea飛n;be曉gi西nre貌ad蔬ln階(n翅,m);廉re念ad宇ln坦(x嘩1,瀉y1巾,x祖2,產(chǎn)y2搭);fi事ll輸ch怠ar化(a攜,s霸iz姻eo株f(府a(chǎn))慚,0米);fo手r應i:柔=1賓t柴o芝m襯do銀a費[1悉,i棗,1遞]:奮=1掃;映f謀or播i塌:=款1堆to仆n凍d只o情a[發(fā)i,考1,坦1]薦:=諸1;抵{邊界}fi掘ll窩ch謝ar集(b房誠,s儉iz別eo顆f(萄b)殊,t呆ru萌e);fo淺r蹈i:幕=x駝1絡to批x腹2換dofo捷r節(jié)j:果=y付1抽to冰y組2揀do梢b概[i勸,j師]:睡=f份al歪se移;{設置鋼障礙放區(qū)域}fo倦r朝i:扯=2低t帥o捧n誰do土{從第禾二列唇推到狹第n列}fo軍r倘j:憐=2權t昆o活m許do堂{計算索從i列的火第二但行到匙第m行頂酷點的虛路徑拴總數(shù)}if允b跡[i沈,j傘]再th睜en畢b推eg嗽in律{高精邁度加疫法}k:藝=0漢;fo污r諒L:貿(mào)=1家t導ole僻ndobe巨gi光nx:朋=a模[i鳥-1繼,覽j夏,武L裙]+雀a[面i翼,黃j-陳1魯,濃L]杠+k敬;a[繼i,捷j,乓L]鞋:=以x貫mo那d沃10速;k:購=x酸d述iv恢1殊0;en澡d;en甘d;k:掛=le磁n;wh破il蝕e貼a[退n,莫m,斧k]影=0拿d集o熄k:河=k饅-1常;fo栽r口i:五=kdo拆wn臣to1戚do軍w竿ri法te斯(a熔[n還,m盾,i裹])掏;en卸d.例2含、過菌河卒如圖蛙，A點有綿一個域過河伏卒，免需要葛走到藍目標B點。炕卒行震走規(guī)惜則：正可以霧向下苗、或米者向鏡右。察同時夫在棋辨盤上建的任磚一點磚有一益?zhèn)€對通方的睛馬（勸如上按圖的C點）屯，該菜馬所昏在的騙點和練所有峰跳躍欄一步迫可達間的點聾稱為鄙對方搬馬的義控制載點。償例如跟上圖C點上愿的馬御可以惰控制9個點敬（圖牌中的P1進，P霜2喬…紅P8和C）。卒不維能通償過對監(jiān)方馬升的控柱制點場。棋秧盤用即坐標梁表示懼，A點（0，統(tǒng)0）、B點（n,棚m）(n,疏m為不局超過20的整醋數(shù))，同摧樣馬怎的位體置坐挖標是暫需要士給出坡的（京約定:C<較>A，同時C<任>B）?，F(xiàn)在謝要求郊你計客算出腰卒從A點能餓夠到殲達B點的只路徑骨的條誦數(shù)。輸入怖文件5.in，只有患一行乎，共4個正喊整數(shù)英，前2個數(shù)證表示B點的藥坐標齒，后2個數(shù)羨表示割對方醬馬的丈坐標孕。輸出奸文件5.ou己t，只有授一行飽，一種個整魔數(shù)（卸表示上路徑本的條窯數(shù)）室。樣例:輸入6跡6描3伴2輸出17分析涉:要考到達班棋盤雪上的龍一個屯點，預只能及從左孕邊過演來或凱是從敏上面鳳下來遍，所敢以根小據(jù)加疾法原輸理，合到達喂某一麥點的貿(mào)路徑獎數(shù)目求，等腥于到礎達其劃相鄰芬上、感左兩魔點的屆路徑驢數(shù)目抬之和削，因躍此我鍬們可獲以使裝用逐送列（擺或逐歇行）避遞推齒的方書法來央求出海從起掀始頂翅點到紫終點設的路恒徑數(shù)妨目，反如果掘有障泰礙，此只要罷將到范達該短點的響路徑騰數(shù)目帶設置蟲為０矛即可跡。co癢ns乓tL=蓮30光;x1六:a旱rr示ay監(jiān)[1插..嗚8]客of艷i需nt圍eg困er鑒=(奶2,邀2,棗1,永-1轉(zhuǎn),-焰2,貓-2乎,-己1,斬1)趁;y1瞇:a哄rr訪ay夾[1底..父8]親of員i托nt淘eg瓜er釘=(食1,赴-1潑,-它2,儉-2達,-帖1,芳1,擾2,著2)零;va已rb:評ar廈ra濕y[手0.錘.2潤0,朱0.做.2黎0]駛o員fbo胳ol且ea拖n;i,踢j,落x,儀y,側(cè)k,憂p,聚n,輝m:包in鏈te府ge輸r;o:愚ar益ra轟y[燈0.嫂.2穗0,撕0.譯.2烏0,去1.閱.L凍]粱of擦i逼nt撇eg駱er事;be務gi蠟nre耐ad糟ln(n村,m袍,x烈,y廳);fi臉ll葬ch爹ar(b馳,si種ze筍of(b于),奶tr抹ue樣);fi育ll辜ch膨ar(o欄,si勤ze障of(o萌),賀0)引;b[射x,擁y]輛:=韻fa默ls語e;｛置控尾制點鈔｝fo倦r須i:烏=1登t賤o劈燕8虜doif蔽(喊x+棒x1坊[i女]>眠=0句)a倚nd劉(x秋+x劣1[貼i]鋸<=肆n)妹an策d(獎y+圣y1扮[i撇]>邀=0項)a乓nd藥(y翁+y渠1[薄i]芝<=專m)th遺en第b佩[x奴+x替1[蔥i]感,y牛+y藏1[殃i]啟]:閃=f斧al晃se鴨;｛置控欲制點鏟｝fo德r竟i:鉆=0袋t早o厭n逗do數(shù)b萍eg傾inif筒n框ot框(b雷[i邊,0浴])鈴t費he寶n田br蘭ea孔k;o[郊i,器0,秩1]仇:=繞1;｛置邊沙界｝en敵d;fo拍r憐i:目=0許t我o閃m皺do錯b鄉(xiāng)豐eg楚inif附n晴ot仿(b售[0飄,i穩(wěn)])說t察he時n以br繁ea撥k;o[潑0,頃i,偷1]慢:=滔1;｛置邊探界｝en灶d;(2箭,1播)(2訊,-釣1)(1既,-內(nèi)2)(-掘1,鍵-2隆)(-芽2,倦-1偶)(-糊2,性1)(-遇1,根2)(1技,2白)fo蹈ri:困=1粒t民o怒n恭dofo訪rj:毫=1析t勺o月m登dobe夫gi幫nk:包=0;誦{進位鋤初始義化}ifb[遙i,陪j]喜th抽enfo缺r輩p:渣=1觸t銀o課L斜do踐{逐位璃相加}be脂gi塞no[家i,圖j,性p]:靜=o勒[i禾-1蔥,j鼠,p個]+霸o[小i,沉j-卡1,跨p]站+k趁;k:燥=o[誤i,艙j,椒p]妖di劍v蚊10屢;o[爬i,跌j,緒p]:培=o[憲i,嗽j,越p]碌mo令d憤10偵;en鈔d;en芳d;j:義=L攀;冷{找出汗最高繼位}wh名il雜e佳(o[升n,就m,晃j]=決0)an嬸d(吼j>1住)期do瘦j妙:=燦j-婦1;fo茂r羨i:兩=jdo銹wn些to1榆dowr軋it栽e(班o[延n,葬m,耳i]避);｛輸出幅高精久度數(shù)掠｝en詢d.例3趨、Ha旅no淋i雙塔猾問題屬（07年復殿賽題）給定A、稻B、斜C三根們足夠獲長的粒細柱治，在A柱上陣放有2n個中峽間有巡壽孔的辭圓盤稱，共教有n個不討同的匆尺寸切，每膊個尺潤寸都腔有兩恨個相號同的叮圓盤凳，注裕意這筐兩個倉圓盤墊是不昏加區(qū)恐分的嗎（下蠟圖為n=3的情仿形）立?，F(xiàn)丹要將句這些末圓盤督移到C柱上濤，在遣移動示過程衣中可碧放在B柱上揀暫存嚴。要柴求：（1）每演次只企能移淘動一鑄個圓阻盤；（2）A、循B、昂C三根炒細柱種上的艷圓盤概都要閥保持誦上小歷下大躲的順托序；任務須：設An為2n個圓裁盤完姻成上甚述任積務所纖需的糖最少昏移動秤次數(shù)席，對嶄于輸迎入的n，輸出An。輸入粗文件ha憑no同i.究in為一勞個正敞整數(shù)n，表示在A柱上猛放有2n個圓稱盤。輸出蔑文件ha篩no騾i.脂ou肢t僅一禮行，泉包含柱一個采正整拼數(shù)，為完豈成上纏述任嚷務所策需的勞最少憂移動組次數(shù)An?！緲永?】hanoi.inhanoi.out12【樣例2】hanoi.inhanoi.out26【限制】對于50%的數(shù)習據(jù)，1<邀=n<=蜂25對于10其0%的數(shù)男據(jù)，1<暈=n<=曾20擦0【提示】設法刪建立An與An-1的遞膊推關播系式槽。解題廢思路:遞推+高精足度1.假設殊當前容要移撲動A軸的N層，辮即2N個盤岡子，恭則需柏要將N-話1層的2N-樣2個盤癥子移腦動到B軸(輔助救軸)上，替再將蔬第N層的2個盤希子移解動到C軸上鐵（目酬標軸紡），迫然后灣再將術那N-通1層的2N-隔2個盤凍子移塑動到柴目標設軸，邁共需純要2f(稍n-赴1)童+2次。2.遞推族關系碌式是擋：f(嶺n)跌:=便2*救f(哀n-幟1)扇+2f(侄0)挪:=持0va疑ra:居ar烘ra低y[湊1.災.6凡2]汪of鞭i偵nt喚eg菌er兇;{存放褲大數(shù)}i,形j,繳n:倒in赴te撒ge叫r;f:致bo跟ol亂ea怖n;be枝gi那nas積si賭gn劇(i呼np美ut諒,'梢ha點no黑i.平in')墾;as但si純gn菊(o級ut給pu和t,短'h美an嘩oi器.o他ut')默;re播se促t(廊in渾pu密t)舉;意re慶wr挪it鏈e(吳ou促tp粒ut侵);re燙ad加ln然(n);湯{層數(shù)}fo纏r包i:患=1奴t蠅o像62瞧d獄o改a[丟i]鋪:=僻0;識{初值}fo陡r鋸i:曲=1蠟t謠o釀n躬do谷{遞推n次}be膽gi刻nfo哲r并j:震=1窯t攤o款62店d姐o耀a[勉j]岔:=傘a[饑j]塵*2黃;掉{先乘2}a[壘1]仗:=冒a[晌1]濁+2添;槽{再在閉個位舅上加2}fo搭r席j:努=1壺t矩o叮62鉗d喇oif疼a名[j狐]>業(yè)9修th典en踩b可eg昏in托{及時狗處理慎進位}a[做j+找1]秋:=灰a[獵j+熱1]土+1她;貴a[務j]雹:=懷a[讓j]故m劇od瓣1吳0;en鍋d;en頂d;f:真=f祥al婆se谷;fo受r見i:港=6幣2do此wn誰to1漠dobe哥gi悼nif呢a倘[i美]<梅>0訴t攀he烈n僅f:點=t竿ru死e;if球f嗚t腹he隊n謎wr喚it懸e(即a[席i]府);en蒼d;cl弄os描e(算in棄pu增t)孝;夸cl沖os住e(停ou腐tp餅ut推);en敗d.問題鄙描述痰：我們灶要求剃找出戒具有蜓下列宇性質(zhì)練數(shù)的藥個數(shù)(包含鋸輸入擴的自煩然數(shù)n)轎:先輸上