归纳法、递推法-36页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。上面的归纳法是不完全归纳法，因为由它得到的结论不一定对任意的n都 成立要证明对所有的n都成立，就必须使用下面介绍的数学归纳法1、证明当n取第一个值n0时结论正确。2、假设当n=k时结论成立，证明当n=k+1时结论也成立。证

2、明：、当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个圆盘完成上述任务所需的最少移动次数，

3、对于输入的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=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(inpu

4、t); 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 begin s:=aj*2+w; aj:=s mod 10; w:=s div 10; end;end;例2、乘火车(98年复赛试题) 火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时

5、（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。现给出的条件是：共有n个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。试问第x站开出时车上的人数是多少？输入文件chc.in：一行四个整数a，n，m和x（中间用空格隔开）输出文件chc.out：一行一个整数（从x站开出时车上的人数）样例 : chc.in4 6 32 4chc.out18分析:典型的数学题为了找规律，我们建立一个表:站号 1 2 3 4 5 6开车时人数n

6、um 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数列)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站开

7、车时的人数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 (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

8、) );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+

9、1)(2n+1)练习3按下图摆放桌子和椅子：一张桌子可坐6人，二张桌子可坐10人，三张桌子可坐14人，试对任意给出的桌子数n（n0）,写出可坐人数。4n+2练习4 如图,第一次把三角形剪去一个角后,图中最多有四个角,第二次再把新产生的角各剪一刀,如此下去,每一次都是把新产生的角各剪一刀,则第n次剪好后,图中最多有多少个角?可知后一次新产生的角的个数是前一次新产生角个数的倍，再加上就是后一次产生角的总数因此，剪n次后，图中最多有角：2+2n递推法常常遇到这样的问题：在一个序列中，下一项的值对其前一项有着某种依赖 关系，求某项的值要从第一项起经过逐次推算而得到。例如：数列0，3，6，9，12，15

10、，该数列的后一项的值是前一项的值加3，欲求第十项，必须先用第一项的值加3，求出第二项，然后求出第三项，第四项，第五项，直到第十项，当然必须事先给定第一项的值（称为初始条件）。可以看出，该数列中第n项的值等于第n-1项的值加3。即：an=an-1+3, (n1) (递推公式)a1=0, (n=1) (初始条件)这种在规定的初始条件下，找出后项对前项的依赖关系的操作，称为递推。表示某项和它前面的若干项的关系式就叫作递推公式。 在实际问题中类似的很多，处理这类问题的理想方法是用归纳法求出通项公式。如上例中的通项公式为an=(n-1)*3 (n=1)。但是在许多情况下，要得到数列的通项公式是比较困难的

11、，而通过已知条件归纳出一个递推关系则相对容易。这时就可以采用递推技术，避开求通项公式的麻烦，把一个复杂问题的求解，分解成为若干步重复的简单运算，由边界条件出发进行递推，最后得到最终结果。 我们把由已知初始值为1，通过递推关系式n=g(Fn-1)求出其最终结果Fn的递推方式称为顺推法同理，把已知最终结果为Fn，通过递推关系式n-1=g(Fn)，求出其初始值1的递推方式称之为倒推法 有一对雌雄小兔子，过一个月之后长成为大兔，并且以后每个月都生下一对小兔。而所生的一对小兔也同样到一个月之后长成大兔，到第三个月就可以生下一对小兔，并且以后也每个月都生下一对小兔。假定所有的兔子n个月内均不死亡，问n个月

12、后共有多少对兔子？ 123456789101112小111235813213455中1112358132134大11235813213455总1123581321345589144f(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），求出铺法总数的递推公式。用F（n）表示其铺法总数的递推公式为:F（1）

13、=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。 用递推公式给出的某人从底层开始走完全部楼梯的走法为（用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+

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

15、5 如果有n元钱,每天去购买下列三种商品之一:蔬菜要用1元钱,猪肉要用2元钱,鸡蛋要用元钱用An表示把这n元钱用完的所有可能的用法的总数，请找出求An的递推公式如果第一天买蔬菜，则用去元钱，还剩n-1元钱， 这n-1元钱的用法有n-1种；如果第一天买猪肉，则用去元钱，还剩n-元钱， 这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 递推的一种重要形式是“倒推”。如果一个问题有唯一解，并且它们的运算是可逆的，

16、就有可能用倒推法来解，它可看成递推法的特例。本题可从最后一天起逐次推出前一天的桃子数，直到推出第一天吃桃子前的全部桃子数为止。根据题意可得tao(i-1)=2*(tao(i)+1) 这样由第十天的桃子数是，可推出第一天的桃子数是1534.有一天，小猴子摘下了若干桃子，当即吃了一半，觉得不过瘾，又吃了一个，第二天猴子接着吃了一半，觉得不过瘾，又吃了一个，以后每天都是吃了一半，觉得不瘾，又吃了一个，到了第十天，只剩下一个桃子了，问小猴子第一天摘下了多少个桃子？（参考程序）练习8 四个人做火柴游戏,每一局三个人赢,一个人输,输者要按赢者手中赢得火柴根数赔偿,即赢者手中有多少根火柴,输者就赔他多少?4

17、次之后,每人恰好输过一次而且手中都恰好有16根?求四人原有火柴数?把第一局输的人记为，把第二局输的人记为，把第三局输的人记为，把第四局输的人记为，用倒退法可知：开始例1、国王与麦子 问题描述： 传说古代印度有个喜欢下棋的国王叫舍罕，而宰相达依尔是个聪明的大臣，他发明了国际象棋。国王玩得爱不惜手，决定奖赏宰相。达依尔说：陛下，我别无他求，请你在这张棋盘的第一个格子里赏我一粒麦子；在第个格子里赏我2粒麦子；在第个格子里赏我粒麦子；在第个格子里赏我粒麦子依此类推直到64个格子，按这张棋盘上各格应赏的麦子全赏给我吧。 国王听了，觉得达依尔的要求并不高，说道：你能如愿以偿的。 你能帮助国王算算第n个格子

18、的麦子数量吗？ 输入文件maizi.in只有一行，一个正整数n（n=100）。 输出文件maizi.out只有一行，一个正整数，表示第n个格子的麦子数量。 输入样例： 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

19、 t:=0;进位初始化 for j:=1 to 100 do 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:arra

20、y1.50,1.50 of boolean;begin readln(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

21、 then 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 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点。例如上图

22、C 点上的马可以控制 9 个点（图中的P1，P2 P8 和 C）。卒不能通过对方马的控制点。棋盘用坐标表示，A 点（0，0）、B 点（n,m）( n,m为不超过 20的整数)，同样马的位置坐标是需要给出的（约定: CA，同时CB）。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 输入文件5.in，只有一行，共4个正整数，前2个数表示B点的坐标，后2个数表示对方马的坐标。 输出文件5.out，只有一行，一个整数（表示路径的条数）。 样例: 输入 6 6 3 2 输出 17分析:要到达棋盘上的一个点，只能从左边过来或是从上面下来，所以根据加法原理，到达某一点的路径数目，等于到达其相邻上

23、、左两点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来求出从起始顶点到终点的路径数目，如果有障碍，只要将到达该点的路径数目设置为即可。const L=30; x1:array1.8of integer=(2,2,1,-1,-2,-2,-1,1); y1:array1.8of integer=(1,-1,-2,-2,-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,siz

24、eof(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);输出高精度数 end.例3、 Hanoi双塔问题 （07年复赛题） 给定A、B、C三根足够长的细柱，在A柱上放有2n个中 间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求

25、： （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=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(o