归纳法递推法

归纳法

归纳法是由一系列有限的特殊事例得出一般规律的推理方法。

例、求前n个奇数的和。分析：用S(n)表示前n个数的和，则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。现在可以归纳出求前n个奇数的和的一般规律，即S(n)=n2。上面的归纳法是不完全归纳法，因为由它得到的结论不一定对任意的n都成立．要证明对所有的n都成立，就必须使用下面介绍的数学归纳法．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个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求：（1）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺序；任务：设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。【样例1】hanoi.inhanoi.out12【样例2】hanoi.inhanoi.out26【限制】

对于50%的数据，1<=n<=25

对于100%的数据，1<=n<=200【提示】

设法建立An与An-1的递推关系式。

解题思路:数学归纳+高精度

Hanoi单塔的最少移动步数是2n-1，现在有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{循环K次}

forj:=1to100dobegins:=a[j]*2+w;a[j]:=smod10;w:=sdiv10;end;end;例2、乘火车(98年复赛试题)火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有n个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问第x站开出时车上的人数是多少？输入文件chc.in：一行四个整数a，n，m和x（中间用空格隔开）输出文件chc.out：一行一个整数（从x站开出时车上的人数）样例:chc.in46324chc.out18分析:典型的数学题为了找规律，我们建立一个表:站号123456开车时人数num[]aa2a2a+b3a+2b4a+4b上车人数in[]aba+ba+2b2a+3b3a+5b下车人数out[]0bba+ba+2b2a+3b规律出来了，设第k(k>=3)站时上车人数为f[k-2]*a+f[k-1]*b(f[k]={1,1,2,3,5,8,13,21..}为fibonacci数列)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站开车时人数为m,容易求出b,再代入(1)求第x站开车时的人数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、将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到７条折痕，那么对折n次，可得到几条折痕？

第一次对折一条折痕，第二次对折（1+2=3）条折痕，第三次对折（1+2+4=7）条折痕，第四次对折（1+2+4+8=15）条折痕，换种写法是20+21+22+23，所以我们猜想第n次对折后的折痕条数是20+21+22+23+…+2n-1或2n-1．练习2数一数下图中有多少个正方形？如果把正方形各边平均分成n份，那么得到的正方形总数为多少？

52+42+32+22+12=55n2+(n-1)2+(n-2)2+…+22+12=1/6n(n+1)(2n+1)练习3按下图摆放桌子和椅子：一张桌子可坐6人，二张桌子可坐10人，三张桌子可坐14人，…试对任意给出的桌子数n（n>0）,写出可坐人数。4n+2练习4如图,第一次把三角形剪去一个角后,图中最多有四个角,第二次再把新产生的角各剪一刀,…,如此下去,每一次都是把新产生的角各剪一刀,则第n次剪好后,图中最多有多少个角?可知后一次新产生的角的个数是前一次新产生角个数的２倍，再加上２就是后一次产生角的总数．因此，剪n次后，图中最多有角：2+2n递推法常常遇到这样的问题：在一个序列中，下一项的值对其前一项有着某种依赖关系，求某项的值要从第一项起经过逐次推算而得到。例如：数列0，3，6，9，12，15，…该数列的后一项的值是前一项的值加3，欲求第十项，必须先用第一项的值加3，求出第二项，然后求出第三项，第四项，第五项，…，直到第十项，当然必须事先给定第一项的值（称为初始条件）。可以看出，该数列中第n项的值等于第n-1项的值加3。即：an=an-1+3,(n>1)(递推公式)a1=0,(n=1)(初始条件)这种在规定的初始条件下，找出后项对前项的依赖关系的操作，称为递推。表示某项和它前面的若干项的关系式就叫作递推公式。在实际问题中类似的很多，处理这类问题的理想方法是用归纳法求出通项公式。如上例中的通项公式为an=(n-1)*3(n>=1)。但是在许多情况下，要得到数列的通项公式是比较困难的，而通过已知条件归纳出一个递推关系则相对容易。这时就可以采用递推技术，避开求通项公式的麻烦，把一个复杂问题的求解，分解成为若干步重复的简单运算，由边界条件出发进行递推，最后得到最终结果。我们把由已知初始值为Ｆ1，通过递推关系式Ｆn=g(Fn-1)求出其最终结果Fn的递推方式称为顺推法．同理，把已知最终结果为Fn，通过递推关系式Ｆn-1=g(Fn)，求出其初始值Ｆ1的递推方式称之为倒推法．有一对雌雄小兔子，过一个月之后长成为大兔，并且以后每个月都生下一对小兔。而所生的一对小兔也同样到一个月之后长成大兔，到第三个月就可以生下一对小兔，并且以后也每个月都生下一对小兔。假定所有的兔子n个月内均不死亡，问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），求出疲铺法犯总数签的递总推公面式。用F（n）表镇示其遮铺法屈总数肢的递苍推公丝式式为:F（1）=1，F（2）=2，F（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）记鼻录不然同方葱案数帖）：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切一质刀，倚得２高块，爆增加重了一搅块；彩切二嚷刀，举得４促块，货增加黄了２票块；霉切三防刀，密得七耐块，愉增加开了３厕块；躲切四辜刀，护得1点1块甜，增宵加了宾4块挠;…晚;切n刀，盆增加n块.可得魂：F(畜1)汽=2F(蹲n)偏=揪F(才n-主1)汽+n浮(n遇>=趟2)这里市使用栗的是面迭代这法．跃递推纪与迭玩代是各两个孙既有其联系怎又有买区别失的概他念，吧递推桶是指桌从前御面一蝴些量很可以束依次脾推出洁后面牛的量震的算掀法．递推不一羡定采钞用迭代．练习4下图材是居但民小逮区道止路图针，小盖明每苍天由迅家（申Ａ点杂）到楼学校闯（Ｂ史点）均，他闭只沿师道路菜向上驱或向挡右行讽走，彻那么携他最谣多有久（伸）愈天走伏不同穴线路例？ＡＢ４９撒５１１１１１盖１涉１闸１弹１得１桌１县１２花３胆４蝴５棋６蜻７宅８仔９３抢６10152128364541020赌35568412无016恳551535夫7012杀621贯033剥0省4让95练习制5如果攻有n元钱,每天引去购锡买下饮列三催种商梨品之搁一:蔬菜尚要用1元钱,猪肉泡要用2元钱,鸡蛋陡要用迹２元百钱．狗用An表示展把这n元钱尼用完颤的所丸有可丑能的租用法去的总谷数，概请找胖出求An的递森推公吃式．如果芝第一纵天买驳蔬菜感，则挺用去雹１元叹钱，雪还剩n-阿1元钱嫌，等这n-休1元钱塞的用谎法有顿Ａn-释1种；如果教第一鲁天买虚猪肉蝴，则晒用去道２元既钱，驼还剩n-陶２元钱女，里这n-锅２元钱贯的用窝法有柄Ａn-丸2种；如果厅第一尝天买乐鸡蛋妹，则畏用去堡２元族钱，起还剩n-围２元钱印，峰这n-判２元钱似的用达法有牺Ａn-辜2种；所以礼，Ａn=Ａn-当1+2Ａn-说2练习舍６求数留列：a1=12,a2=22,a3=32,…趣,an=n2的递仗推公好式．f(盾n)欢=f蛙(n妨-1待)+地2n霸-1练习河7递推怀的一工种重示要形允式是粉“倒疗推”总。如哗果一队个问赖题有俊唯一备解，画并且绑它们宇的运对算是来可逆胞的，燥就有勾可能滚用倒捕推法奔来解夜，它扁可看侄成递羽推法鹿的特牺例。本题擦可从统最后泰一天恶起逐先次推拣出前杂一天轨的桃奖子数菠，直些到推适出第冲一天真吃桃滋子前家的全族部桃茂子数谈为止像。根据在题意有可得ta笨o(桂i-闸1)艰=2子*(蠢ta傅o(畏i)岂+1晃)这样墙由第捡十天颤的桃岩子数荒是１怕，可镇推出运第一道天的太桃子望数是暮15买34澡.有一说天，勇小猴宇子摘箱下了仆若干鲁桃子窄，当秒即吃纵了一尿半，乞觉得聋不过穷瘾，像又吃上了一烘个，姿第二昨天猴懂子接诵着吃竞了一兴半，姜觉得股不过垄瘾，晓又吃棍了一神个，增以后遍每天验都是添吃了税一半优，觉翼得不训瘾，器又吃抗了一嚷个，矛到了图第十幕天，槐只剩爱下一刃个桃摔子了拔，问优小猴畏子第尘一天院摘下欠了多岔少个垃桃子圣？（参考怪程序）练习舞8四个轮人做唯火柴轿游戏演,每断一局衫三个刻人赢宴,一纤个人框输,抗输者己要按躺赢者脂手中瓜赢得攀火柴宿根数遵赔偿怒,即酒赢者症手中麦有多碑少根尼火柴园,输傲者就棒赔他丑多少仓?4除次之庙后,至每人遮恰好猎输过丹一次径而且展手中锦都恰弹好有序16帝根?矛求四猫人原锤有火野柴数歇?把第视一局导输的补人记匀为Ａ碌，把份第二麦局输饮的人漠记为袖Ｂ，鹊把第叮三局择输的隐人记拿为Ｃ宏，把漂第四惰局输伙的人居记为院Ｄ，蝇用倒谊退法庆可知夺：ＡＢＣＤ４１６１６１６１６３８８８４０２４４３６２０１２３４１８１０开始３３１７９５例1、国等王与染麦子问题乘描述予：传说歇古代鼻印度炮有个薄喜欢礼下棋喉的国让王叫书舍罕纪，而昆宰相吩达依态尔是杨个聪更明的寨大臣磨，他册发明倚了国毁际象忠棋。品国王艘玩得佛爱不孟惜手圣，决策定奖猎赏宰诞相。弹达依送尔说粮：陛唉下，死我别坑无他乐求，佳请你霜在这栋张棋京盘的劫第一偿个格时子里泪赏我悬一粒形麦子鹅；在阀第２丧个格饲子里饮赏我2粒麦虏子；礼在第毁３个院格子于里赏描我４容粒麦惩子；妻在第真４个楚格子哄里赏饲我８震粒麦概子……依此和类推纠直到64个格予子，亲按这量张棋村盘上编各格均应赏缸的麦树子全俱赏给耕我吧追。国王泄听了劈燕，觉奥得达奸依尔环的要喘求并骑不高孙，说锦道：激你能缠如愿修以偿堡的。你能免帮助绣国王辣算算锁第n个格澡子的弹麦子寇数量呼吗？输入醉文件ma娇iz哥i.讲in只有洗一行奇，一撇个正搁整数n（n<赌=1拔00）。输出瞒文件ma投iz林i.担ou怎t只有满一行柴，一削个正奶整数菊，表长示第n个格虚子的螺麦子盾数量值。输入隶样例窃：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犬ai竹zi洪.o少ut')赚;re怀wr辈it碍e(狐ou筝tp德ut);re乱ad仇(n);朽{读入粱格子侄数}a[届1,管1]涂:=秆1;票{第一乎格的写麦子撑数为1}fo粮r拳i:承=2维t昨o壶n里do盼{递推押求每唤个格疫子中庄的麦浸子数}be况gi卡nt:秃=0网;{进位他初始净化}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现it等e(悉a[封n,雹j])毕;cl关os则e(座in士pu卧t);cl跨os尽e(吸ou唤tp态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,产y2搭);fi事ll输ch怠ar化(a携,s霸iz姻eo株f(府a)惭,0米);fo手r应i:柔=1宾t柴o芝m衬do银a费[1悉,i枣,1递]:奋=1扫;映f谋or播i塌:=款1堆to仆n冻d只o情a[发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节j:果=y付1抽to冰y组2拣do梢b概[i劝,j师]:睡=f份al歪se移;{设置钢障碍放区域}fo倦r朝i:扯=2低t帅o捧n谁do土{从第禾二列唇推到狭第n列}fo军r倘j:怜=2权t昆o活m许do堂{计算索从i列的火第二但行到匙第m行顶酷点的虚路径拴总数}if允b迹[i沈,j伞]再th睁en毕b推eg嗽in律{高精迈度加疫法}k:艺=0汉;fo污r谅L:贸=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点。炕卒行震走规惜则：正可以雾向下苗、或米者向镜右。察同时夫在棋辨盘上建的任砖一点砖有一益个对通方的睛马（劝如上按图的C点）屯，该菜马所昏在的骗点和练所有峰跳跃栏一步迫可达间的点聋称为鄙对方搬马的义控制载点。偿例如跟上图C点上愿的马御可以惰控制9个点敬（图牌中的P1进，P霜2乔…红P8和C）。卒不维能通偿过对监方马升的控柱制点场。棋秧盘用即坐标梁表示惧，A点（0，统0）、B点（n,棚m）(n,疏m为不局超过20的整醋数)，同摧样马怎的位体置坐挖标是暂需要士给出坡的（京约定:C<较>A，同时C<任>B）。现在谢要求郊你计客算出腰卒从A点能饿够到歼达B点的只路径骨的条诵数。输入怖文件5.in，只有患一行乎，共4个正喊整数英，前2个数证表示B点的药坐标齿，后2个数羡表示割对方酱马的丈坐标孕。输出奸文件5.ou己t，只有授一行饱，一种个整魔数（卸表示上路径本的条窑数）室。样例:输入6迹6描3伴2输出17分析涉:要考到达班棋盘雪上的龙一个屯点，预只能及从左孕边过演来或凯是从敏上面凤下来遍，所敢以根小据加疾法原输理，合到达喂某一麦点的贸路径奖数目求，等腥于到础达其划相邻芬上、感左两魔点的届路径驴数目抬之和削，因跃此我锹们可获以使装用逐送列（摆或逐歇行）避递推齿的方书法来央求出海从起掀始顶翅点到紫终点设的路恒径数妨目，反如果掘有障泰碍，此只要罢将到范达该短点的响路径腾数目带设置虫为０矛即可迹。co痒ns乓tL=莲30光;x1六:a旱rr示ay监[1插..呜8]客of艳i需nt围eg困er鉴=(奶2,邀2,枣1,永-1转,-焰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,侧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数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乡丰eg楚inif附n晴ot仿(b售[0飘,i稳])说t察he时n以br繁ea拨k;o[泼0,顷i,偷1]慢:=滔1;｛置边探界｝en灶d;(2箭,1播)(2讯,-钓1)(1既,-内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]避);｛输出幅高精久度数掠｝en询d.例3趋、Ha旅no淋i双塔猾问题属（07年复殿赛题）给定A、稻B、斜C三根们足够获长的粒细柱治，在A柱上阵放有2n个中峡间有巡寿孔的辞圆盘称，共教有n个不讨同的匆尺寸切，每膊个尺润寸都腔有两恨个相号同的叮圆盘凳，注裕意这筐两个仓圆盘垫是不昏加区恐分的吗（下蜡图为n=3的情仿形）立。现丹要将句这些末圆盘督移到C柱上涛，在遣移动示过程衣中可碧放在B柱上拣暂存严。要柴求：（1）每演次只企能移淘动一铸个圆阻盘；（2）A、循B、昂C三根炒细柱种上的艳圆盘概都要阀保持诵上小历下大躲的顺托序；任务须：设An为2n个圆裁盘完姻成上甚述任积务所纤需的糖最少昏移动秤次数席，对崭于输迎入的n，输出An。输入粗文件ha凭no同i.究in为一劳个正敞整数n，表示在A柱上猛放有2n个圆称盘。输出蔑文件ha筛no骡i.脂ou肢t仅一礼行，泉包含柱一个采正整拼数，为完岂成上缠述任嚷务所策需的劳最少忧移动组次数An。【样例1】hanoi.inhanoi.out12【样例2】hanoi.inhanoi.out26【限制】对于50%的数习据，1<邀=n<=蜂25对于10其0%的数男据，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凶;{存放裤大数}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);汤{层数}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狐]>业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.问题鄙描述痰：我们灶要求剃找出戒具有蜓下列宇性质练数的药个数(包含锯输入扩的自烦然数n)轿:先输上