归纳法、递推法-36页PPT课件.ppt

1、归纳法归纳法 归纳法是由一系列有限的特殊事例得出一般规律的推理方法。归纳法是由一系列有限的特殊事例得出一般规律的推理方法。例、求前例、求前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。上面的归纳法是不完全归纳法，因为由它得到的结论不一定对上面的归纳法是不完

2、全归纳法，因为由它得到的结论不一定对任意的任意的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双

3、塔问题双塔问题07年复赛试题年复赛试题 给定给定A、B、C三根足够长的细柱，在三根足够长的细柱，在A柱上放有柱上放有2n个中个中 间有孔的圆盘，共有间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情的情形）。现要将这些圆盘移到形）。现要将这些圆盘移到C柱上，在移动过程中可放在柱上，在移动过程中可放在B柱柱上暂存。要求：上暂存。要求：（1）每次只能移动一个圆盘；）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺三根细柱上的圆盘都要保持上小下

4、大的顺序；序；任务：设任务：设An为为2n个圆盘完成上述任务所需的最少移动次个圆盘完成上述任务所需的最少移动次数，对于输入的数，对于输入的n，输出，输出An。输入文件输入文件hanoi.in为一个正整数为一个正整数n，表示在，表示在A柱上放有柱上放有2n个圆盘。个圆盘。输出文件输出文件hanoi.out仅一行，包含一个正整数仅一行，包含一个正整数，为完成上为完成上述任务所需的最少移动次数述任务所需的最少移动次数An。【样例【样例1】hanoi.inhanoi.out12【样例【样例2】hanoi.inhanoi.out26【限制】【限制】对于对于50%的数据，的数据，1=n=25 对于对于10

5、0%的数据，的数据，1=n=2 then a1:=a1-2 else begin a1:=a1+8;a2:=a2-1;end;i:=100;while ai=0 do i:=i-1;for j:=i downto 1 do write(aj);close(input);close(output);end.var n,i,j:integer;a:array1.100 of 0.9;procedure ppp(k:integer);var i,j,w,s:integer;begin a1:=1;w:=0;for i:=1 to k do循环循环K次次 for j:=1 to 100 do begi

6、n s:=aj*2+w;aj:=s mod 10;w:=s div 10;end;end;例例2、乘火车、乘火车(98年复赛试题年复赛试题)火车从始发站（称为第火车从始发站（称为第1站）开出，在始发站上车的人数为站）开出，在始发站上车的人数为a，然后到达第然后到达第2站，在第站，在第2站有人上、下车，但上、下车的人数相同，站有人上、下车，但上、下车的人数相同，因此在第因此在第2站开出时（即在到达第站开出时（即在到达第3站之前）车上的人数保持为站之前）车上的人数保持为a人。人。从第从第3站起（包括第站起（包括第3站）上、下车的人数有一定规律：上车的人数站）上、下车的人数有一定规律：上车的人数都是

7、前两站上车人数之和，而下车人数等于上一站上车人数，一直都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：站），都满足此规律。现给出的条件是：共有共有n个车站，始发站上车的人数为个车站，始发站上车的人数为a，最后一站下车的人数是，最后一站下车的人数是m（全部下车）。试问第（全部下车）。试问第x站开出时车上的人数是多少？站开出时车上的人数是多少？输入文件输入文件chc.in：一行四个整数：一行四个整数a，n，m和和x（中间用空格隔开）（中间用空格隔开）输出文件输出文件chc.out：一行一个整数（从：一行一个

8、整数（从x站开出时车上的人数）站开出时车上的人数）样例样例:chc.in4 6 32 4chc.out18分析分析:典型的数学题典型的数学题为了找规律，我们建立一个表为了找规律，我们建立一个表:站号站号 1 2 3 4 5 6开车时人数开车时人数num a a 2a 2a+b 3a+2b 4a+4b上车人数上车人数in a b a+b a+2b 2a+3b 3a+5b下车人数下车人数out 0 b b a+b a+2b 2a+3b规律出来了，设第规律出来了，设第k(k=3)站时站时上车人数为上车人数为fk-2*a+fk-1*b(fk=1,1,2,3,5,8,13,21.为为fibonacci数

9、列数列)numk=a+in2-out2+in3-out3.+ink-outk而而in2=out3,in3=out4.故故numk=a-out2+ink=a-b+fk-2a+fk-1b=(fk-2+1)a+(fk-1-1)b (1)因为知道第因为知道第n-1站开车时人数为站开车时人数为m,容易求出容易求出b,再代入再代入(1)求第求第x站开车时的人数站开车时的人数p。即：即：m=(fn-3+1)a+(fn-2-1)b(2)p=(fx-2+1)a+(fx-1-1)b(3)从从(2)解得解得b,代入代入(3)计算知计算知p=(fx-2+1)*a+(fx-1-1)*(m-(fn-3+1)*a)div(

10、fn-2-1);var f:array1.23 of integer;i,a,n,m,x:integer;begin f1:=1;f2:=1;for i:=3 to 23 do fi:=fi-1+fi-2;readln(a,n,m,x);writeln(fx-2+1)*a+(fx-1-1)*(m-(fn-3+1)*a)div(fn-2-1);end.练习练习1、将一张长方形的纸对折，可得到一条折痕，继续对将一张长方形的纸对折，可得到一条折痕，继续对折，对折时每次折痕与上次的折痕保持平行，连续对折折，对折时每次折痕与上次的折痕保持平行，连续对折三次后，可得到条折痕，那么对折三次后，可得到条折痕，

11、那么对折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份，那么得到的正方形总数为多少？份，那么得到的正方形总数为多

12、少？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（n0）,写出可坐人数。写出可坐人数。4n+2练习练习4 如图如图,第一次把三角形剪去一个角后第一次把三角形剪去一个角后,图中最多有四个角图中最多有四个角,第二次再把新产生的角各剪一刀第二次再把新产生的角各剪一刀,如此下去如此下去,每一次都是把每一次都是把新产生的角各剪一刀新产生的角

13、各剪一刀,则第则第n次剪好后次剪好后,图中最多有多少个角图中最多有多少个角?可知后一次新产生的角的个数是前一次新产生角个数可知后一次新产生的角的个数是前一次新产生角个数的倍，再加上就是后一次产生角的总数因此，的倍，再加上就是后一次产生角的总数因此，剪剪n次后，图中最多有角：次后，图中最多有角：2+2n递推法递推法常常遇到这样的问题：在一个序列中，下一项的值对其前一项有着某种依赖常常遇到这样的问题：在一个序列中，下一项的值对其前一项有着某种依赖 关系，求某项的值要从第一项起经过逐次推算而得到。关系，求某项的值要从第一项起经过逐次推算而得到。例如：数列例如：数列0，3，6，9，12，15，该数列的

14、后一项的值是前一项的值加该数列的后一项的值是前一项的值加3，欲求第十项，必须先用第一项的值加，欲求第十项，必须先用第一项的值加3，求出第二项，然后求出第三项，第四项，第五项，求出第二项，然后求出第三项，第四项，第五项，直到第十项，当然必须，直到第十项，当然必须事先给定第一项的值（称为初始条件）。事先给定第一项的值（称为初始条件）。可以看出，该数列中第可以看出，该数列中第n项的值等于第项的值等于第n-1项的值加项的值加3。即：。即：an=an-1+3,(n1)(递推公式递推公式)a1=0,(n=1)(初始条件初始条件)这种在规定的初始条件下，找出后项对前项的依赖关系的操作，称为这种在规定的初始条

15、件下，找出后项对前项的依赖关系的操作，称为递推递推。表示某项和它前面的若干项的关系式就叫作表示某项和它前面的若干项的关系式就叫作递推公式递推公式。在实际问题中类似的很多，处理这类问题的理想方法是用归纳法求出通项公在实际问题中类似的很多，处理这类问题的理想方法是用归纳法求出通项公式。如上例中的通项公式为式。如上例中的通项公式为an=(n-1)*3 (n=1)。但是在许多情况下，要得到数列的通项公式是比较困难的，而通过已知条件但是在许多情况下，要得到数列的通项公式是比较困难的，而通过已知条件归纳出一个递推关系则相对容易。这时就可以采用递推技术，避开求通项公式的归纳出一个递推关系则相对容易。这时就可

16、以采用递推技术，避开求通项公式的麻烦，把一个复杂问题的求解，分解成为若干步重复的简单运算，由边界条件出麻烦，把一个复杂问题的求解，分解成为若干步重复的简单运算，由边界条件出发进行递推，最后得到最终结果。发进行递推，最后得到最终结果。我们把由已知初始值为我们把由已知初始值为1，通过递推关系式，通过递推关系式n=g(Fn-1)求出其最终结求出其最终结果果Fn的递推方式称为顺推法同理，把已知最终结果为的递推方式称为顺推法同理，把已知最终结果为Fn，通过递推关系，通过递推关系式式n-1=g(Fn)，求出其初始值，求出其初始值1的递推方式称之为倒推法的递推方式称之为倒推法 有一对雌雄小兔子，过一个月之后

17、长成为大兔，并且以后每个月都生下有一对雌雄小兔子，过一个月之后长成为大兔，并且以后每个月都生下一对小兔。而所生的一对小兔也同样到一个月之后长成大兔，到第三个月就一对小兔。而所生的一对小兔也同样到一个月之后长成大兔，到第三个月就可以生下一对小兔，并且以后也每个月都生下一对小兔。假定所有的兔子可以生下一对小兔，并且以后也每个月都生下一对小兔。假定所有的兔子n n个月内均不死亡，问个月内均不死亡，问n个月后共有多少对兔子？个月后共有多少对兔子？12345678910 11 12小111235813 21 34 55中111235813 21 34大11235813 21 34 55总11235813

18、 21 34 55 89144f(1)=1 (n=1)f(2)=1 (n=2)f(n)=f(n-1)+f(n-2)(n2)如何通过已知条件归纳出一个递推公式如何通过已知条件归纳出一个递推公式?参考程序参考程序参考程序参考程序练习练习1（2000年初赛试题年初赛试题）有有2n的一个长方形方格，用一种的一个长方形方格，用一种12的骨牌铺满方格。的骨牌铺满方格。例如例如n=3时，为时，为23的的方格，有方格，有如下种铺如下种铺法：法：此时用一个此时用一个12的骨牌铺满方格，共有的骨牌铺满方格，共有3种铺法：种铺法：试对给出的任意一个试对给出的任意一个n（n0），求出铺法总数的递推公式。），求出铺法总

19、数的递推公式。用用F（n）表示其铺法总数的递推公式为）表示其铺法总数的递推公式为:F（1）=1，F（2）=2，F（n）=F（n-2）+F（n-1）（）（n3）练习练习2（2000年初赛试题年初赛试题）设有一个共有设有一个共有n级的楼梯，某人每步可走级的楼梯，某人每步可走1级，也可走级，也可走2级，也可走级，也可走3级，用递推公式给出某人从底层开始走完全部级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当楼梯的走法。例如：当n=3时，共有时，共有4种走法，即种走法，即1+1+1,1+2,2+1,3。用递推公式给出的某人从底层开始走完全部楼梯的走法为用递推公式给出的某人从底层开始走完全部

20、楼梯的走法为（用（用F（n）记录不同方案数）：）记录不同方案数）：F（1）1 F（2）2 F（3）4F(n)F（n3）F（n2）F（n1）（）（n=4）练习练习3一张圆薄饼，切一张圆薄饼，切100刀，最多能切成多少块？刀，最多能切成多少块？a100=a99+100 =a98+99+100 =a97+98+99+100 =a1+2+3+98+99+100 =2+2+3+98+99+100 =5051切一刀，得块，增加了一块；切二刀，得块，增加了块；切一刀，得块，增加了一块；切二刀，得块，增加了块；切三刀，得七块，增加了块；切四刀，得切三刀，得七块，增加了块；切四刀，得11块，增加了块，增加了4块

21、块;切切n刀，增加刀，增加n块块.可得：可得：F(1)=2 F(n)=F(n-1)+n(n=2)这里使用的是迭代法递这里使用的是迭代法递推与迭代是两个既有联系推与迭代是两个既有联系又有区别的概念，递推是又有区别的概念，递推是指从前面一些量可以依次指从前面一些量可以依次推出后面的量的算法递推出后面的量的算法递推不一定采用迭代推不一定采用迭代练习练习4下图是居民小区道路图，小明每天由家（点）到学校（点），下图是居民小区道路图，小明每天由家（点）到学校（点），他只沿道路向上或向右行走，那么他最多有（）天走不同线路？他只沿道路向上或向右行走，那么他最多有（）天走不同线路？1015212836 454

22、1020 355684120 1655 1535 70126 210 330 495练习练习5 如果有如果有n元钱元钱,每天去购买下列三种商品之一每天去购买下列三种商品之一:蔬菜要蔬菜要用用1元钱元钱,猪肉要用猪肉要用2元钱元钱,鸡蛋要用元钱用鸡蛋要用元钱用An表示把表示把这这n元钱用完的所有可能的用法的总数，请找出求元钱用完的所有可能的用法的总数，请找出求An的的递推公式递推公式如果第一天买蔬菜，则用去元钱，还剩如果第一天买蔬菜，则用去元钱，还剩n-1元钱，元钱，这这n-1元钱的用法有元钱的用法有n-1种；种；如果第一天买猪肉，则用去元钱，还剩如果第一天买猪肉，则用去元钱，还剩n-元钱，元钱

23、，这这n-元钱的用法有元钱的用法有n-2种；种；如果第一天买鸡蛋，则用去元钱，还剩如果第一天买鸡蛋，则用去元钱，还剩n-元钱，元钱，这这n-元钱的用法有元钱的用法有n-2种；种；所以，所以，n=n-1+2n-2练习练习求数列：求数列：a1=12,a2=22,a3=32,an=n2的递推公式的递推公式f(n)=f(n-1)+2n-1练习练习7 递推的一种重要形式是递推的一种重要形式是“倒推倒推”。如果一个问题有唯一解，并且。如果一个问题有唯一解，并且它们的运算是可逆的，就有可能用倒推法来解，它可看成递推法的特它们的运算是可逆的，就有可能用倒推法来解，它可看成递推法的特例。例。本题可从最后一天起逐

24、次推出前一天的桃子数，直到推出第一天本题可从最后一天起逐次推出前一天的桃子数，直到推出第一天吃桃子前的全部桃子数为止。吃桃子前的全部桃子数为止。根据题意可得根据题意可得tao(i-1)=2*(tao(i)+1)这样由第十天的桃子数是，可推出第一天的桃子数是这样由第十天的桃子数是，可推出第一天的桃子数是1534.有一天，小猴子摘下了若干桃子，当即吃了一半，觉得有一天，小猴子摘下了若干桃子，当即吃了一半，觉得不过瘾，又吃了一个，第二天猴子接着吃了一半，觉得不过不过瘾，又吃了一个，第二天猴子接着吃了一半，觉得不过瘾，又吃了一个，以后每天都是吃了一半，觉得不瘾，又吃瘾，又吃了一个，以后每天都是吃了一半

25、，觉得不瘾，又吃了一个，到了第十天，只剩下一个桃子了，问小猴子第一天了一个，到了第十天，只剩下一个桃子了，问小猴子第一天摘下了多少个桃子？（参考程序）摘下了多少个桃子？（参考程序）练习练习8 四个人做火柴游戏四个人做火柴游戏,每一局三个人赢每一局三个人赢,一个人输一个人输,输者要按输者要按赢者手中赢得火柴根数赔偿赢者手中赢得火柴根数赔偿,即赢者手中有多少根火柴即赢者手中有多少根火柴,输者就输者就赔他多少赔他多少?4次之后次之后,每人恰好输过一次而且手中都恰好有每人恰好输过一次而且手中都恰好有16根根?求四人原有火柴数求四人原有火柴数?把第一局输的人记为，把第二局输的人记为，把第三把第一局输的人

26、记为，把第二局输的人记为，把第三局输的人记为，把第四局输的人记为，用倒退法可知：局输的人记为，把第四局输的人记为，用倒退法可知：开始例例1、国王与麦子、国王与麦子 问题描述：问题描述：传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的大臣，他发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：大臣，他发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第个格子里赏我个格子里赏我2粒麦子；在

27、第个格子里赏我粒麦子；在第个格子里粒麦子；在第个格子里赏我粒麦子；在第个格子里赏我粒麦子赏我粒麦子依此类推直到依此类推直到64个格子，按这张棋盘上各格应赏的麦子个格子，按这张棋盘上各格应赏的麦子全赏给我吧。全赏给我吧。国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。你能帮助国王算算第你能帮助国王算算第n个格子的麦子数量吗？个格子的麦子数量吗？输入文件输入文件maizi.in只有一行，一个正整数只有一行，一个正整数n（n=100）。）。输出文件输出文件maizi.out只有一行，一个正整数，表示第只有一行，一个正整数，表示第n个格子

28、的麦子数个格子的麦子数量。量。输入样例：输入样例：5 输出样例：输出样例：16 var a:array1.100,1.100 of integer;n,i,j,t:longint;begin assign(input,maizi.in);reset(input);assign(output,maizi.out);rewrite(output);read(n);读入格子数读入格子数 a1,1:=1;第一格的麦子数为第一格的麦子数为1 for i:=2 to n do递推求每个格子中的麦子数递推求每个格子中的麦子数 begin t:=0;进位初始化进位初始化 for j:=1 to 100 do

29、begin ai,j:=ai-1,j*2+t;t:=ai,j div 10;ai,j:=ai,j mod 10;end;end;i:=100;while an,i=0 do i:=i-1;去掉高位多余的去掉高位多余的0 for j:=i downto 1 do write(an,j);close(input);close(output);end.const len=30;var n,m,i,j,L,k,x1,x2,y1,y2,x:longint;a:array1.50,1.50,1.len of longint;b:array1.50,1.50 of boolean;begin readln(

30、n,m);readln(x1,y1,x2,y2);fillchar(a,sizeof(a),0);for i:=1 to m do a1,i,1:=1;for i:=1 to n do ai,1,1:=1;边界边界 fillchar(b,sizeof(b),true);for i:=x1 to x2 do for j:=y1 to y2 do bi,j:=false;设置障碍区域设置障碍区域 for i:=2 to n do从第二列推到第从第二列推到第n列列 for j:=2 to m do计算从计算从i列的第二行到第列的第二行到第m行顶点的路径总数行顶点的路径总数 if bi,j then

31、begin 高精度加法高精度加法 k:=0;for L:=1 to len do begin x:=ai-1,j,L+ai,j-1,L+k;ai,j,L:=x mod 10;k:=x div 10;end;end;k:=len;while an,m,k=0 do k:=k-1;for i:=k downto 1 do write(an,m,i);end.例例2、过河卒、过河卒 如图，如图，A A 点有一个过河卒，需要走到目标点有一个过河卒，需要走到目标 B B 点。卒行走规则：可以向点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的下、或者向右。同时在棋盘上的任一

32、点有一个对方的马（如上图的C C点），点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图 C C 点上的马可以控制点上的马可以控制 9 9 个点（图中的个点（图中的P1P1，P2 P8 P2 P8 和和 C C）。卒不能通过对方）。卒不能通过对方马的控制点。棋盘用坐标表示，马的控制点。棋盘用坐标表示，A A 点（点（0 0，0 0）、）、B B 点（点（n,mn,m）(n,mn,m为不超过为不超过 2020的整数的整数)，同样马的位置坐标是需要给出的（约定，同样马的位置坐标是需要给出的（约定:CA:CA，同时，同时

33、CBCB）。）。现在要求你计算出卒从现在要求你计算出卒从 A A 点能够到达点能够到达 B B 点的路径的条数。点的路径的条数。输入文件输入文件5.in5.in，只有一行，共，只有一行，共4 4个正整数，前个正整数，前2 2个数表示个数表示B B点的坐标，后点的坐标，后2 2个数表示对方马的坐标。个数表示对方马的坐标。输出文件输出文件5.out5.out，只有一行，一个整数（表示路径的条数）。，只有一行，一个整数（表示路径的条数）。样例样例:输入输入 6 6 3 2 6 6 3 2 输出输出 1717分析分析:要到达棋盘上的一个点，只能从左边过来或是从上面要到达棋盘上的一个点，只能从左边过来或

34、是从上面下来，所以根据加法原理，到达某一点的路径数目，等于下来，所以根据加法原理，到达某一点的路径数目，等于到达其相邻上、左两点的路径数目之和，因此我们可以使到达其相邻上、左两点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起始顶点到终点的用逐列（或逐行）递推的方法来求出从起始顶点到终点的路径数目，如果有障碍，只要将到达该点的路径数目设置路径数目，如果有障碍，只要将到达该点的路径数目设置为即可。为即可。const L=30;x1:array1.8of integer=(2,2,1,-1,-2,-2,-1,1);y1:array1.8of integer=(1,-1,-2,-2

35、,-1,1,2,2);var b:array0.20,0.20 of boolean;i,j,x,y,k,p,n,m:integer;o:array0.20,0.20,1.L of integer;beginreadln(n,m,x,y);fillchar(b,sizeof(b),true);fillchar(o,sizeof(o),0);bx,y:=false;置控制点置控制点for i:=1 to 8 do if(x+x1i=0)and(x+x1i=0)and(y+y1i1)do j:=j-1;for i:=j downto 1 do write(on,m,i);输出高精度数输出高精度数

36、end.例例3、Hanoi双塔问题双塔问题 （07年复赛题年复赛题）给定给定A、B、C三根足够长的细柱，在三根足够长的细柱，在A柱上放有柱上放有2n个中个中 间有孔的圆盘，共有间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情的情形）。现要将这些圆盘移到形）。现要将这些圆盘移到C柱上，在移动过程中可放在柱上，在移动过程中可放在B柱柱上暂存。要求：上暂存。要求：（1）每次只能移动一个圆盘；）每次只能移动一个圆盘；（2）A、B、C三根细柱上的圆盘都要保持上小下大的顺三

37、根细柱上的圆盘都要保持上小下大的顺序；序；任务：设任务：设An为为2n个圆盘完成上述任务所需的最少移动次个圆盘完成上述任务所需的最少移动次数，对于输入的数，对于输入的n，输出，输出An。输入文件输入文件hanoi.in为一个正整数为一个正整数n，表示在，表示在A柱上放有柱上放有2n个圆盘。个圆盘。输出文件输出文件hanoi.out仅一行，包含一个正整数仅一行，包含一个正整数，为完成上为完成上述任务所需的最少移动次数述任务所需的最少移动次数An。【样例【样例1】hanoi.inhanoi.out12【样例【样例2】hanoi.inhanoi.out26【限制】【限制】对于对于50%的数据，的数据

38、，1=n=25 对于对于100%的数据，的数据，1=n9 then begin 及时处理进位及时处理进位 aj+1:=aj+1+1;aj:=aj mod 10;end;end;f:=false;for i:=62 downto 1 do begin if ai0 then f:=true;if f then write(ai);end;close(input);close(output);end.问题描述：问题描述：我们要求找出具有下列性质数的个数我们要求找出具有下列性质数的个数(包含输入的自然数包含输入的自然数n):先输入一个自然数先输入一个自然数n（n1000）,然后对此自然数按照如下方法

39、进行然后对此自然数按照如下方法进行处理。处理。1不作任何处理；不作任何处理；2在它的左边加上一个自然数，但该自然数不能超过原数的一半；在它的左边加上一个自然数，但该自然数不能超过原数的一半；3加上数后，加上数后，继续按此规则进行处理，直到不能再加自然数为止继续按此规则进行处理，直到不能再加自然数为止。样例样例:输入：输入：6 满足条件的数为满足条件的数为 6 (此部分不必输出此部分不必输出)16 26 126 36 136 输出：输出：6例例4、数的计数、数的计数(01年复赛年复赛)分析分析1：用：用f(n)表示自然数表示自然数n所能扩展的数据总个数，则所能扩展的数据总个数，则f(1)=1，f

40、(2)=2，f(3)=2，f(4)=4，f(5)=4，f(6)=6，f(7)=6，f(8)=10，f(9)=10。可得递推公式：可得递推公式：f(n)=1+f(1)+f(2)+f(n div 2)。var s:array1.1000 of longint;i,j,n:integer;begin readln(n);for i:=1 to n do si:=1;设初始值为设初始值为1,其本身算一种其本身算一种 for i:=2 to n do for j:=1 to i div 2 do si:=si+sj;i左边分别加上左边分别加上1至至i div 2 按规则扩展出的自然数按规则扩展出的自然数

41、 writeln(sn);end.分析分析2：用：用f(n)表示自然数表示自然数n所能扩展的数据总个数，则所能扩展的数据总个数，则f(1)=1，f(2)=2，f(3)=2，f(4)=4，f(5)=4，f(6)=6，f(7)=6，f(8)=10，f(9)=10。可得递推公式如下：可得递推公式如下：当当i为奇数时，为奇数时，f(i)=f(i-1)当当i为偶数时，为偶数时，f(i)=f(i-1)f(i/2)var f:array0.1000 of longint;i,j,n:integer;begin readln(n);f1:=1;for i:=2 to n do begin fi:=fi-1;if i mod 2=0 then fi:=fi-1+fi div 2;end;writeln(fn);end.